2.1 布隆过滤器的概念
布隆过滤器的底层数据结构与位图相同，且具备一系列哈希函数，可以做到快速查询一个元素是否在集合中，同时节省内存空间。
它的缺点是 存在误判（原本不存在，判断为存在） 和 不便删除 。
可以把布隆过滤器想象成一个集合，Set() 插入元素，Test() 元素是否存在。
- Set("Tencent") ——> 经过一系列哈希函数的映射，对布隆过滤器底层数据结构上 pos1、pos2、... 等位置进行标记；
- Test("Tencent") ——> 判断
Tencent经这一系列哈希函数映射的、对应底层数据结构的位置，是否都被标记，得出结论。
- 存在误判：若插入一系列元素，经一系列哈希函数映射，分别标记
Tencent所对应的 pos1、pos2、... ，那么即便没有插入 “Tencent” ，Test(Tencent）的结果仍然为 True ；可以通过 扩大底层空间 和 增加哈希函数个数 减小误判率。- 不便删除：删除 “Tencent”是否意味着要将其映射的位置重新标记成 0 ？假设 “Tencent” 与 “Baidu” 映射到同一 pos2 ，删除 “Tencent” ，将无法再查询到 “Baidu”。
2.2 性能优秀的字符串哈希算法
详细：
[各种字符串 Hash 函数] https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html
struct HashFuncBKDR { // BKDR size_t operator()(const string& s) { size_t hash = 0; for (auto ch : s) { hash *= 131; hash += ch; } return hash; } }; struct HashFuncAP { // AP size_t operator()(const string& s) { size_t hash = 0; for (size_t i = 0; i < s.size(); i++) { if ((i & 1) == 0) // 偶数位字符 { hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3)); } else // 奇数位字符 { hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5))); } } return hash; } }; struct HashFuncDJB { // DJB size_t operator()(const string& s) { size_t hash = 5381; for (auto ch : s) { hash = hash * 33 ^ ch; } return hash; } };
2.3 BloomFilter 实现
template<size_t N, class K = string class Hash1 = HashFuncBKDR, class Hash2 = HashFuncAP, class Hash3 = HashFuncDJB> class BloomFilter { private: static const size_t M = 5 * N; // 静态成员常量，用于给底层开更大的空间 // 2 种创建底层的写法 bitset<M> _bs; // 1 bitset<M>* _bs = new bitset<M>; // 2 };
经过实测，std::bitset 是在栈区开空间，当数据量很大时会导致栈溢出，因此选择第二种写法 —— 在堆区开空间：
bitset<M>* _bs = new bitset<M>;
不需要为 BloomFilter 写构造函数， bitset 会调用自己的构造函数。
class BloomFilter { public: void Set(const K& key) { size_t Hashi1 = Hash1()(key) % M; // 仿函数；% M 防止越界访问 size_t Hashi2 = Hash2()(key) % M; size_t Hashi3 = Hash3()(key) % M; _bs->set(Hashi1); _bs->set(Hashi2); _bs->set(Hashi3); } bool Test(const K& key) { size_t Hashi1 = Hash1()(key) % M; if (_bs->test(Hashi1) == false) return false; size_t Hashi2 = Hash2()(key) % M; if (_bs->test(Hashi2) == false) return false; size_t Hashi3 = Hash3()(key) % M; if (_bs->test(Hashi3) == false) return false; return true; } };
2.4 切分思想
- 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
- 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？
处理这类大量数据的问题，通用的解法就是：把大文件按照某种规律分为若干个小文件存进硬盘中，如： Hash(IP) % 1000 、 Hash(query) % 1000 —— 通过哈希函数把具有相同特征的元素分成 1000 份，再在内存中对这些小文件逐个处理。
某个小文件太大，分为两种情况：
- 存在大量重复的元素。 ——> 存入 set 或 bitset 等容器中，会自动去重，无须担心。
- 存在大量不重复的元素。——> 换一个哈希函数，把该小文件再切分，再处理，以此类推。
2.5 拓展支持删除
以多个比特位组为一个标准单位。
