位图

位图的概念 

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

直接来看问题：

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在
这40亿个数中。

思路：解决问题的方法，可以使用位图来解决。把这40亿个数据映射在位图上，将位图上对应的比特位置为1。然后拿着需要判断的数在位图上看看其对应的比特位是否为1，如果是则存在，否则为0。

具体做法：

使用直接定址法，这40亿个数据的值是几，就把第几个比特位标记为1。因为40亿个整数，大概需要16G内存，而使用比特位，我们只需使用char作为存储在vector上的类型，每一个都是1bit大，因此在vector上开辟2^32大小的空间，表示数据大小范围，一共512M。

 开辟好空间后，开始将每一个数据映射到位图上。每一个char对象为8bit，于是让每一个值先确定自己在哪个char对象上，然后确定映射在哪个比特位上。

x映射的值，在第 x/8 个char对象上。

x映射的值，在第 x%8 个比特位上。

所以，我们可以根据上面的理论，用代码简单实现位图

使用非模板参数N，作为数据的个数。

开辟空间：空间开辟的大小为N /8 +1，因为N个数据，每8个为一组，多开辟一组，避免N不是8的整除。然后初始化为0。即位图上的比特位一开始全是0.

		//初始化空间，初始值为0bitset(){_bits.resize((N >> 3) + 1, 0);}

数据映射位图上的比特位：先计算好数据所在的组别和比特位的位置，然后将其置为1。置为1的操作是让这一个char对象组别的比特位与这个数据的比特位进行或运算。

		void set(size_t x){size_t i = x >> 3;//位于哪一个char对象上size_t j = x % 8;//位于这个char对象上的哪个比特位上_bits[i] |= (1 << j);//通过或运算，将x对应的比特位变为1}

将某个数据映射的比特位从1变回0：同样的找到这个位置后，然后这一组别的比特位与这个数据的比特取反后进行与运算。

		void reset(size_t x){size_t i = x >> 3;size_t j = x % 8;_bits[i] & = (~(1 << j));//通过与运算，让x对应的比特位变为0}

判断一共数据是是否存在：同样，先计算出这个数据映射的位置。然后返回这一组别跟这个数据的比特，然后进行与运算，注意不是与等，是不能改变原本位图的比特位的。

		//判断x是否存在，如果存在返回truebool test(size_t x){size_t i = x >> 3;size_t j = x % 8;return _bits[i] & (1 << j);}

完整代码如下：

namespace my_BitSet
{templateclass bitset{public://初始化空间，初始值为0bitset(){_bits.resize((N >> 3) + 1, 0);}void set(size_t x){size_t i = x >> 3;//位于哪一个char对象上size_t j = x % 8;//位于这个char对象上的哪个比特位上_bits[i] |= (1 << j);//通过或运算，将x对应的比特位变为1}void reset(size_t x){size_t i = x >> 3;size_t j = x % 8;_bits[i] & = (~(1 << j));//通过与运算，让x对应的比特位变为0}//判断x是否存在，如果存在返回truebool test(size_t x){size_t i = x >> 3;size_t j = x % 8;return _bits[i] & (1 << j);}private:vector _bits;};
}

布隆过滤器

位图对于判断大量数据中是否存在某一个数据的情况固然是好，其优点是节省空间和判断速度块。但其缺点是一般要求范围相对集中，如果范围特别分散，那么空间消耗就大了，而且是只针对整型。因此，布隆过滤器降临！

布隆过滤器的概念

布隆过滤器是一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中，因为布隆过滤器是哈希+位图的结合。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

一般的位图下，每一个数据只跟位图产生一个映射点，而且只能用于整型。但布隆过滤器是每一个数据可以有N个映射点，N个映射点对应于N个哈希函数，这个是我们自己定义的。用哈希函数将非整型转化成整型。

 布隆过滤器的长度的计算方式：

使用公式：

 K为哈希函数的个数，m为布隆过滤器长度，n为数据的个数。假设K为3，而ln2约等于0.7，因此m==4.2n。

布隆过滤器的功能支持：

布隆过滤器支持set和test方法，最好不要有将1变回0的操作。因为这样会导致其它数据的判断的误差。如果真的要支持，就用计数的方法，但这种方法不推荐。

简单实现代码如下

这里使用3个哈希函数，分别为：BKDRHash、APHash和DJBHash。使用string为类型。

set方法：

		void set(const K& key){//通过不同的哈希函数，让同一个数据可以计算出三个不同的位置size_t hash1 = HashFunc1()(key) % (N * X);size_t hash2 = HashFunc2()(key) % (N * X);size_t hash3 = HashFunc3()(key) % (N * X);//计算出位置后，使用位图的set方法将位图上对应的比特位进行0变1_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}

test方法：

		bool test(cost K& key){//先逐个位置判断，如果它是0，直接返回falsesize_t hash1 = HashFunc1()(key) % (N * X);if (!_bs.test(hash1)){return false;}size_t hash2 = HashFunc2()(key) % (N * X);if (!_bs.test(hash2)){return false;}size_t hash3 = HashFunc3()(key) % (N * X);if (!_bs.test(hash3)){return false;}//直到最后，说明该数据是存在的，返回truereturn true;}

整体代码如下：

namespace my_BloomFilter
{struct BKDRHash{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}};struct APHash{size_t operator()(const string& key){unsigned int hash = 0;int i = 0;for (auto ch : key){if ((i & 1) == 0){hash ^= ((hash << 7) ^ (ch) ^ (hash >> 3));}else{hash ^= (~((hash << 11) ^ (ch) ^ (hash >> 5)));}++i;}return hash;}};struct DJBHash{size_t operator()(const string& key){unsigned int hash = 5381;for (auto ch : key){hash += (hash << 5) + ch;}return hash;}};templateclass BloomFilter{public:void set(const K& key){//通过不同的哈希函数，让同一个数据可以计算出三个不同的位置size_t hash1 = HashFunc1()(key) % (N * X);size_t hash2 = HashFunc2()(key) % (N * X);size_t hash3 = HashFunc3()(key) % (N * X);//计算出位置后，使用位图的set方法将位图上对应的比特位进行0变1_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}bool test(cost K& key){//先逐个位置判断，如果它是0，直接返回falsesize_t hash1 = HashFunc1()(key) % (N * X);if (!_bs.test(hash1)){return false;}size_t hash2 = HashFunc2()(key) % (N * X);if (!_bs.test(hash2)){return false;}size_t hash3 = HashFunc3()(key) % (N * X);if (!_bs.test(hash3)){return false;}//直到最后，说明该数据是存在的，返回truereturn true;}private:std::bitset _bs;};
}

海量数据处理问题

哈希切割

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

超过100G大小的文件，肯定不能直接放到内存中，而是通过将它切割，分成很多份。那么如何去切割呢？是平均分成100份，每一份1G这样吗？

如果平均切割，那么会导致的问题是：如果文件中有好几个相同的值，且分布不集中，此时平均切割就很可能使一个IP有很多份在很多小文件中。

因此不能平均切割，需要的是哈希切割。哈希切割就是通过取模，让取模结果相同的数据放到同一份小文件里面。

哈希切割后，通过map来对每一个小文件进行统计。

小问题如果超过1G的问题：

①不重复的IP有很多个，map就需要很多节点，因此map是统计不下来的。

②重复的IP有很多个，map可以统计下来，因为节点不多。

解决方法：

先不看什么情况，直接用map统计，如果是第二种情况的话就直接统计下来了。但是第一种情况，会在insert的时候失败，因此可以在失败的时候捕捉异常，接着换哈希函数递归切分再统计即可。

位图的应用 

1.给定100亿个整数，设计算法找到只出现一次的整数？

只出现一次，那就说明，它在位图中比特位是：01。如果找到该位置发现是00或11或者其它的情况，那就不是。

但一个一般的位图只会出现单个比特，即要么是0，要么是1，不会出现两个比特。这里的方法使用两个位图的结构。即定义两个位图，然后用同一个数据计算出来的同一个位置，分别在这个两个位图上进行0和1的操作。

简单的代码实现：

	templateclass twobitset{public:void set(size_t x){//初次映射：两个位图对应的比特位都为0，即00if (!_bs1.test(x) && !_bs2.test(x)//  00{_bs2.set(x);//  01}else if (!_bs1.test(x) && _bs2.test(x) //  01{//第二次遇到这个数字后，此时是01的，要变成10_bs1.set(x); //11_bs2.reset(x); // 10}//如果第三次遇到，也不用管了，第二次遇到的时候就已经不是它了//10//11}void PrintOnce(){for (size_t i = 0; i < N; ++i){if (!_bs1.test(i) && _bs2.test(i))  // 01 出现一次{cout << i << endl;}}cout << endl;}private:bitset _bs1;bitset _bs2;};
}

 2.给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

这里提供两种思路：

思路1：先将一个文件的数据映射到位图中，然后用另外一个文件的数据去遍历，得到交集，需要注意去重。

思路2：分布将两文件映射到两个位图，然后通过两位图的与运算判断是否有交集。

3.位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。

这道问题跟第一个问题基本一样，就是让“01”和"10"为需要找到的整数。如果出现"11"以上，那么就不行。

布隆过滤器的应用

1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法。

query是一般为一个查询指令，可能是一个网络请求的指令，也可能是一个数据库sql语句。

精确算法找文件交集的思路是：分别给两个文件创建布隆过滤器，然后让它们进行哈希切割，分成一个个小文件。最后通过编号相同的小文件中查找交集。

近似算法的思路是：将一个文件的数据映射到一个布隆过滤器中，然后另外一个文件去查找有没有相同的，有就是交集。这种算法会造成误判。