一、布隆过滤器介绍
位图有使用起来，节省空间，并且效率高的优点。位图的缺点，只能处理整形。
假如起昵称时要看一个字符串有没有被占用，用一个bit位标识。哈希解决冲突时，可以把后续同样位置冲突的元素的挂起来，形成链表。但是现在，如果要用位图存储字符串，bit位存不了指针，挂不起来，处理不了哈希冲突。如果用哈希存储又会浪费空间。
因此能不能考虑将哈希和位图结合针对字符串等非整形的类型，设计一个像位图一样的判断key在不在的节省空间的数据结构呢？可以——布隆过滤器
布隆过滤器是一种紧凑的、巧妙的概率型数据结构，能够高效插入查询，来判断一个元素在或不在，用多个哈希函数，把一个数据映射到位图中，不仅能提高查询效率，还能节省空间
映射多个位时，这种情况下也可能存在误判，但是误判概率低了，因为当映射的多个位都被占用才会冲突，才会导致误判。如上图中的"华山"还没存入呢，要映射的几个位都变成了1，这时会导致"华山"被误判。但是这种误判发送的概率比较低，只在几个位全都被占用的情况下才发生。
二、布隆过滤器实现
1.布隆过滤器
只需要位图一个成员即可：
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #pragma once 3. #include "BitSet.h" 4. #include <string> 5. using namespace std; 6. 7. template<size_t N, class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB> 8. class BloomFilter 9. { 10. private: 11. delia::BitSet<N> _bitset; 12. };
2.三种哈希函数
由于要用三种不同的哈希算法进行计算来降低冲突，因此，可以选择3种不同的哈希算法：
（1）BKDR哈希
1. struct HashBKDR 2. { 3. size_t operator()(const string& s) 4. { 5. size_t value = 0; 6. for (auto e : s) 7. { 8. value += e; 9. value *= 131; 10. } 11. 12. return value; 13. } 14. };
（2）AP哈希
1. struct HashAP 2. { 3. size_t operator()(const string& s) 4. { 5. register size_t hash = 0; 6. size_t ch; 7. for (long i = 0; i < s.size(); i++) 8. { 9. ch = s[i]; 10. if ((i & 1) == 0) 11. { 12. hash ^= ((hash << 7) ^ ch ^ (hash >> 3)); 13. } 14. else 15. { 16. hash ^= (~(hash << 11) ^ ch ^ (hash >> 5)); 17. } 18. } 19. 20. return hash; 21. } 22. };
（3）DJB哈希
1. struct HashDJB 2. { 3. size_t operator()(const string& s) 4. { 5. register size_t hash = 5381; 6. for (auto e : s) 7. { 8. hash += (hash << 5) + e; 9. } 10. 11. return hash; 12. } 13. };
3.标识
用三种哈希函数分别计算对应的比特位，将这三个比特位都置1：
1. void Set(const K& key) 2. { 3. size_t i1 = Hash1()(key) % N;//也可以写成Hash1 hf1; size_t i1 = hf1(key) % N; 4. size_t i2 = Hash2()(key) % N; 5. size_t i3 = Hash3()(key) % N; 6. 7. cout << i1 << " " << i2 << " " << i3 << endl; 8. 9. _bitset.set(i1); 10. _bitset.set(i2); 11. _bitset.set(i3); 12. }
4.检查在不在
分别用三种哈希函数计算三个比特位，如果检测到有一个比特位为不在，那就返回不在：
1. bool Tests(const K& key) 2. { 3. size_t i1 = Hash1()(key) % N; 4. if (_bitset.test(i1) == false) 5. { 6. return false; 7. } 8. 9. size_t i2 = Hash2()(key) % N; 10. if (_bitset.test(i2) == false) 11. { 12. return false; 13. } 14. 15. size_t i3 = Hash3()(key) % N; 16. if (_bitset.test(i3) == false) 17. { 18. return false; 19. } 20. 21. return true;//可能存在误判，如"华山" 22. }
5.删除
布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素
比如：删除"钟楼"元素，如果直接将该元素所对应的二进制比特位置0，“华山”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。
三、完整代码段
BloomFilter.h:
1. #pragma once 2. #include "BitSet.h" 3. #include <string> 4. using namespace std; 5. 6. //BKDR哈希 7. struct HashBKDR 8. { 9. size_t operator()(const string& s) 10. { 11. size_t value = 0; 12. for (auto e : s) 13. { 14. value += e; 15. value *= 131; 16. } 17. 18. return value; 19. } 20. }; 21. 22. //AP哈希 23. struct HashAP 24. { 25. size_t operator()(const string& s) 26. { 27. register size_t hash = 0; 28. size_t ch; 29. for (long i = 0; i<s.size(); i++) 30. { 31. ch = s[i]; 32. if ((i & 1) == 0) 33. { 34. hash ^= ((hash << 7) ^ ch ^ (hash >> 3)); 35. } 36. else 37. { 38. hash ^= (~(hash << 11) ^ ch ^ (hash >> 5)); 39. } 40. } 41. 42. return hash; 43. } 44. }; 45. 46. //DJB哈希 47. struct HashDJB 48. { 49. size_t operator()(const string& s) 50. { 51. register size_t hash = 5381; 52. for (auto e : s) 53. { 54. hash += (hash << 5) + e; 55. } 56. 57. return hash; 58. } 59. }; 60. 61. template<size_t N, class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB> 62. class BloomFilter 63. { 64. public: 65. void Set(const K& key) 66. { 67. size_t i1 = Hash1()(key) % N;//也可以写成Hash1 hf1; size_t i1 = hf1(key) % N; 68. size_t i2 = Hash2()(key) % N; 69. size_t i3 = Hash3()(key) % N; 70. 71. cout << i1 << " " << i2 << " " << i3 << endl; 72. 73. _bitset.set(i1); 74. _bitset.set(i2); 75. _bitset.set(i3); 76. } 77. 78. bool Tests(const K& key) 79. { 80. size_t i1 = Hash1()(key) % N; 81. if (_bitset.test(i1) == false) 82. { 83. return false; 84. } 85. 86. size_t i2 = Hash2()(key) % N; 87. if (_bitset.test(i2) == false) 88. { 89. return false; 90. } 91. 92. size_t i3 = Hash3()(key) % N; 93. if (_bitset.test(i3) == false) 94. { 95. return false; 96. } 97. 98. return true;//可能存在误判，如"华山" 99. } 100. private: 101. delia::BitSet<N> _bitset; 102. }; 103. 104. void TestBloomFilter() 105. { 106. BloomFilter<100> bf; 107. bf.Set("大雁塔"); 108. bf.Set("钟楼"); 109. bf.Set("兵马俑"); 110. bf.Set("华山"); 111. }
Test.cpp
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include "BloomFilter.h" 3. 4. int main() 5. { 6. TestBloomFilter(); 7. return 0; 8. }
四、布隆过滤器优缺点
1.优点
（1）增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
（2）哈希函数相互之间没有关系，方便硬件并行运算
（3）布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
（4）在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
（5）数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
（6）使用同一组散列函数的布隆过滤器可以进行交、并、差运算
2.缺点
（1）有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
（2）不能获取元素本身
（3）一般情况下不能从布隆过滤器中删除元素
