一、位图
1.1 位图概念
位图就是用每一位来存放某种状态，适用于海量数据且数据无重复的场景。通常是用来判断某个数据是否存在的。
1.2 位图的实现
位图的底层结构依然是连续的线性空间，这里我们使用vector容器作为其底层结构。
#include <iostream> #include <vector> using std::vector; using std::cout; using std::endl; namespace bjy { template<size_t N> class bitset { public: bitset() { if (N % 8 == 0) _bits.resize(N / 8, 0); else _bits.resize(N / 8 + 1, 0); } void set(size_t which){//将某个位设置为1 size_t i = which / 8, j = which % 8; _bits[i] |= (1 << j); } void reset(size_t which) {//将某个位设置为0 size_t i = which / 8, j = which % 8; _bits[i] &= ~(1 << j); } bool test(size_t which)const { size_t i = which / 8, j = which % 8; return _bits[i] & (1 << j); } private: vector<char> _bits; };
1.3 位图的特点
1. 速度快且节省时间。
2. 采用直接定址法，不存在哈希冲突。
3. 相对局限，只能处理整型数据。
4. STL中实现的bitset容器存在一定不足，其底层使用静态数组实现。其开辟在栈区会导致在处理海量数据时极易发生StackOverflow。(使用时应特别注意)
二、布隆过滤器
2.1 布隆过滤器的提出
当使用新闻客户端看新闻时，其会不停地推荐新的内容，每次推荐时要去重。但新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何实现的呢？
方案一: 使用哈希表存储用户记录，但空间消耗过大。
方案二: 使用位图记录用户信息，明显不可取(位图只能处理整型数据)
方案三: 将位图与哈希进行结合，即布隆过滤器
2.2 概念
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询。可以用来告诉你 "某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
Bloom Filters (jasondavies.com)
https://www.jasondavies.com/bloomfilter/
2.3 实现原理
布隆过滤器是一个 bit 向量或者说 bit 数组
若要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置进行set操作。例如针对key "百度" 用三个不同的哈希函数分别生成了哈希值 0、3、6，则上图转变为：
再存一个值 "腾讯"，若哈希函数返回 2、3、7 的话，图继续变为：
3 这个bit位由于两个key的哈希函数都返回了3，因此它被覆盖了。
现在若想查询 "b站" 这个key是否存在，哈希函数返回了 0、4、7三个值，结果我们发现 4 这个 bit 位上的值为 0，说明没有任何一个key映射到这个 bit 位上，因此我们可以很确定地说 "b站"这个key不存在。而当我们需要查询 "百度" 这个值是否存在的话，那么哈希函数必然会返回 0、3、6，然后我们检查发现这三个 bit 位上的值均为 1，那么说明"baidu"可能存在。
为什么不是一定存在呢？因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个key即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他key置为了 1 ，那么程序还是会判断这个key存在。
2.4 哈希函数个数和布隆过滤器长度的选择
在使用布隆过滤器时，哈希函数的个数和布隆过滤长度的设定都是我们需要考虑的问题。
1. 哈希函数个数越多则布隆过滤器bit位被置为1的速度越快，且会效率下降。但是若哈希函数过少则会导致误报率较高。
2. 布隆过滤器的长度会直接影响误报率，布隆过滤器长度越长则误报率越低。但若是过长了则失去布隆过滤器原有的优势(占用空间小)，反而还不如选择哈希表。
直接根据下图中的公式选择即可
2.5 布隆过滤器的删除
布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计
数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储
空间的代价来增加删除操作。
缺陷：
1. 无法确认元素是否真正在布隆过滤器中
2. 存在计数回绕
2.6 特点
2.6.1 优点
1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定误判的情况下，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
2.6.2 缺点
1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再
建立一个白名单，存储可能会误判的数据)
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素
4. 如果采用计数方式删除，可能会存在计数回绕问题
2.7 完整代码实现
#include <iostream> #include <vector> #include <string> #include <bitset> using namespace std; namespace bjy { struct HashBKDR { size_t operator()(const string& key) { size_t sum = 0; for (auto& e : key) { sum = sum * 131 + e; } return sum; } }; struct HashAP { size_t operator()(const string& key) { size_t hash = 0; for (size_t i = 0; i < key.size(); i++) { if ((i & 1) == 0) { hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5))); } } return hash; } }; struct HashDJB { size_t operator()(const string& key) { size_t hash = 5381; for (auto ch : key) { hash += (hash << 5) + ch; } return hash; } }; template<size_t N, class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB> class Bloon_filter { public: void set(const K& key) { size_t pos1 = Hash1()(key) % (_ratio * N); size_t pos2 = Hash2()(key) % (_ratio * N); size_t pos3 = Hash3()(key) % (_ratio * N); _bits->set(pos1); _bits->set(pos2); _bits->set(pos3); } bool test(const K& key) { size_t pos1 = Hash1()(key) % (_ratio * N); size_t pos2 = Hash2()(key) % (_ratio * N); size_t pos3 = Hash3()(key) % (_ratio * N); if (_bits->test(pos1) && _bits->test(pos2) && _bits->test(pos3)) return true; else return false; } private: const static size_t _ratio = 5; bitset<_ratio* N>* _bits = new bitset<_ratio* N>;//库中bitset使用静态数组，开辟在栈上，容易导致栈溢出 }; }
三、海量数据处理常见面试题
1. 给定100亿个整数，设计算法找到只出现一次的整数
利用两个位图完成该问题的实现。采用KV的统计次数的模型，两个位图中各有一个bit位表示同一个整型。00表示该整型出现次数为0，01表示该整型出现次数为1，10表示该整型出现次数为2次,11表示该整型出现3次及以上。
template<size_t N> class twobitset { public: void set(size_t x) { bool inset1 = _bs1.test(x); bool inset2 = _bs2.test(x); if (inset1 == false && inset2 == false)//00 { _bs2.set(x);// -> 01 } else if (inset1 == false && inset2 == true)//01 { _bs1.set(x); _bs2.reset(x);// ->10 } else if (inset1 == true && inset2 == false)//10 { // ->11 _bs1.set(x); _bs2.set(x); } } void print_once_num(){ for (size_t i = 0; i < N; ++i){ if (_bs1.test(i) == false && _bs2.test(i) == true){ cout << i << endl; } } } private: bitset<N> _bs1; bitset<N> _bs2; };
2. 两个文件分别有100亿个整数，只有1G内存，找到两个文件交集
将文件A中的数据映射到位图A中，将文件B中的数据映射到位图B中，位图A和位图B对应且都为1的位所代表的key的集合即是两个文件的交集。
3. 给两个文件，分别有100亿个query，只有1G内存，找到两个文件交集。分别给出精确算法和近似算法
该问题不可使用bitset解决，其只适用于整型数据。query为字符串，应使用哈希切割思想或者布隆过滤器完成问题。
近似算法:
使用两个布隆过滤器分别处理两个文件，若两个布隆过滤器set(key)都为1，即这个key在两个文件中都可能存在，近似看做交集中的元素。
精确算法:
假设1个query为30Byte,100亿个query则大概需要300G以上的内存空间。我们的电脑肯定没有这么大的空间，所以这里需要使用哈希切割的思想。
若是处理完后某个小文件过大，可以换一个哈希函数对小文件再次进行哈希切割。
4. 给一个超过100G大小的log file, log中存着IP地址。(1)设计算法找到出现次数最多的IP地址。(2)找到top-K的IP。
问题一:
使用哈希切割，将一个大的log file分成500个小log file,相同的IP一定进入同一个小log file。再用map<string,int> 或者unordered_map<string,int>对每个小log file进行次数统计,找出出现次数最多的IP地址。
问题二:
建立一个K个<IP,count>元素的小堆(优先级队列)
