深圳幻海软件技术有限公司 欢迎您！
更多

【C++进阶】十一、哈希的应用---布隆过滤器（二）

2023-04-02

key hash 过滤器
目录一、布隆过滤器提出二、布隆过滤器概念三、布隆过滤器实现3.1 布隆过滤器的插入3.2布隆过滤器的查找3.3 布隆过滤器的删除3.4完整代码四、布隆过滤器优点五、布隆过滤器缺陷一、布隆过滤器提出    在注册账号设置昵称的时候，有些软件要

目录

一、布隆过滤器提出

二、布隆过滤器概念

三、布隆过滤器实现

3.1 布隆过滤器的插入

3.2 布隆过滤器的查找

3.3 布隆过滤器的删除

3.4 完整代码

四、布隆过滤器优点

五、布隆过滤器缺陷

一、布隆过滤器提出

       在注册账号设置昵称的时候，有些软件要求每个用户昵称要保持唯一性，系统必须检测你输入的昵称是否被使用过，这本质就是一个K的模型，只需要判断这个昵称存在还是不存在

  1. 用哈希表存储用户昵称，缺点：浪费空间
  2. 用位图存储用户昵称，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了
  3. 将哈希与位图结合，即布隆过滤器

为什么说位图处理不了字符串？？

        位图虽然能够大大节省内存空间，但由于字符串的组合形式太多了，一个字符的取值有256种，而一个数字的取值只有10种，字符串的数量是远远大于整数的，使用位图就会出现一个整数对应多个字符串的情况，即哈希冲突，这种冲突概率是很高的（如，某个昵称明明就是没有使用过，系统却判断使用过了）

而布隆过滤器可以把这些哈希冲突大大降低

二、布隆过滤器概念

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

布隆过滤器实际上就是位图的变形、拓展

先说一下位图的误判

  1. 位图判断不在，是准确的 
  2. 位图判断在，是不准确的，因为可能本来不在，但是这个位置跟别人冲突，出现误判，对于字符串这种误判率会很高

布隆过滤器可以大大降低这些哈希冲突

假设布隆过滤器使用三个哈希函数进行映射（位图只是使用一个哈希函数），每个字符串就会映射三个比特位，那么“find”在位图中会有三个比特位会被置1，就算前两个哈希函数计算出来的位置都产生了冲突（前两个比特位为1），但由于第三个哈希函数计算出的比特位的为0（第三个比特位为0），此时就会判断这个“find”不存在，这种误判概率大大降低了

但随着位图中添加的数据不断增多，位图中1的个数也在不断增多，此时就会导致误判的概率增加

布隆过滤器的特点：

  • 当布隆过滤器判断一个数据存在可能是不准确的，因为这个数据对应的比特位可能被其他一个数据或多个数据占用了
  • 当布隆过滤器判断一个数据不存在是准确的，因为如果该数据存在那么该数据对应的比特位都应该已经被设置为1了

 如何控制误判率？？

  1. 过小的布隆过滤器很快所有的比特位都会被设置为1，此时布隆过滤器的误判率就会变得很高，因此布隆过滤器的长度会直接影响误判率，布隆过滤器的长度越长其误判率越小
  2. 此外，哈希函数的个数也需要权衡，哈希函数的个数越多布隆过滤器中比特位被设置为1的速度越快，并且布隆过滤器的效率越低，但如果哈希函数的个数太少，也会导致误判率变高。

如何选择哈希函数的个数和布隆过滤器的长度？？

有大佬通过计算得出了公式，博客链接：详解布隆过滤器的原理，使用场景和注意事项 - 知乎 (zhihu.com)https://zhuanlan.zhihu.com/p/43263751/

 

公式为：

其中k为哈希函数个数，m为布隆过滤器长度，n为插入的元素个数，p为误判率

直接使用第二个公式，这里可以大概估算一下：

  • 如果使用3个哈希函数，即 k的值为3，ln2 的值我们取0.7，那么  m = 3*n/0.7 = 4.2n 左右，也就是布隆过滤器的长度应该是插入元素个数的4倍左右
  • 如果使用4个哈希函数，即 k的值为4，ln2 的值我们取0.7，那么  m = 4*n/0.7 = 5.7n 左右，也就是布隆过滤器的长度应该是插入元素个数的6倍左右

注：布隆过滤器在STL中并没有实现，因为需求不一样，即所需哈希哈数个数不同，官方库就没有给出，有需要需要自己实现

三、布隆过滤器实现

布隆过滤器实现直接复用STL的bitset，bitset符合我们的需求，封装一下即可

size_t N 是位图长度，size_t X 是每个元素映射时建议的位图大小，布隆过滤器可以实现为一个模板类，因为插入布隆过滤器的元素不仅仅是字符串，也可以是其他类型的数据，只有调用者能够提供对应的哈希函数将该类型的数据转换成整型即可，但一般情况下布隆过滤器都是用来处理字符串的，所以这里可以将模板参数K的缺省类型设置为string

  1. template<size_t N,//位图长度，N*X需要开的空间大小
  2. size_t X = 4,//使用3个哈希函数，布隆过滤器的长度应该是插入元素个数的4倍左右
  3. class K = string,
  4. class HashFunc1 = BKDRHash,
  5. class HashFunc2  = APHash,
  6. class HashFunc3 = DJBHash
  7. //有需要再增加哈希函数
  8. >

基本框架如下：

  1. template<size_t N,//位图长度，N*X需要开的空间大小
  2. size_t X = 4,//使用3个哈希函数，布隆过滤器的长度应该是插入元素个数的4倍左右
  3. class K = string,
  4. class HashFunc1 = BKDRHash,
  5. class HashFunc2 = APHash,
  6. class HashFunc3 = DJBHash
  7. //有需要再增加哈希函数
  8. >
  9.  
  10. class BloomFilter
  11. {
  12. public:
  13.  
  14. private:
  15. std::bitset<N* X> _bs;
  16. };

 这里还需增加字符串转换成整型的哈希函数，字符串哈希算法博客：各种字符串Hash函数 - clq - 博客园 (cnblogs.com)https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html

这里选取了经过测试后综合评分最高的BKDRHash、APHash和DJBHash哈希函数，这三种哈希算法在多种场景下产生哈希冲突的概率是最小的 

三个哈希函数代码如下 ：

  1. struct BKDRHash
  2. {
  3. size_t operator()(const string& key)
  4. {
  5. size_t hash = 0;
  6. for (auto ch : key)
  7. {
  8. hash *= 131;
  9. hash += ch;
  10. }
  11. return hash;
  12. }
  13. };
  14.  
  15. struct APHash
  16. {
  17. size_t operator()(const string& key)
  18. {
  19. unsigned int hash = 0;
  20. int i = 0;
  21.  
  22. for (auto ch : key)
  23. {
  24. if ((i & 1) == 0)
  25. {
  26. hash ^= ((hash << 7) ^ (ch) ^ (hash >> 3));
  27. }
  28. else
  29. {
  30. hash ^= (~((hash << 11) ^ (ch) ^ (hash >> 5)));
  31. }
  32.  
  33. ++i;
  34. }
  35.  
  36. return hash;
  37. }
  38. };
  39.  
  40. struct DJBHash
  41. {
  42. size_t operator()(const string& key)
  43. {
  44. unsigned int hash = 5381;
  45.  
  46. for (auto ch : key)
  47. {
  48. hash += (hash << 5) + ch;
  49. }
  50.  
  51. return hash;
  52. }
  53. };
  54.

3.1 布隆过滤器的插入

插入元素时，需要通过三个哈希函数分别计算出该元素对应的三个比特位，然后将位图中的这三个比特位设置为1即可，设置直接调用库里的即可

  1. void set(const K& key)
  2. {
  3.     //计算出key对应的三个位
  4. size_t hash1 = HashFunc1()(key) % (N * X);
  5. size_t hash2 = HashFunc2()(key) % (N * X);
  6. size_t hash3 = HashFunc3()(key) % (N * X);
  7.     //设置为1
  8. _bs.set(hash1);
  9. _bs.set(hash2);
  10. _bs.set(hash3);
  11. }

3.2 布隆过滤器的查找

需要通过三个哈希函数分别计算出该元素对应的三个比特位，然后判断位图中的这三个比特位是否被设置为1即可，直接调用 bitset 的 test函数

  1. 只要这三个比特位当中有一个比特位未被设置则说明该元素一定不存在
  2. 如果这三个比特位全部被设置，则返回true表示该元素存在（可能存在误判）
  1. bool test(const K& key)
  2. {
  3. size_t hash1 = HashFunc1()(key) % (N * X);
  4. if (!_bs.test(hash1))
  5. {
  6. return false;
  7. }
  8.  
  9. size_t hash2 = HashFunc2()(key) % (N * X);
  10. if (!_bs.test(hash2))
  11. {
  12. return false;
  13. }
  14.  
  15. size_t hash3 = HashFunc3()(key) % (N * X);
  16. if (!_bs.test(hash3))
  17. {
  18. return false;
  19. }
  20. // 前面判断不在都是准确，不存在误判
  21.  
  22. return true; // 可能存在误判，映射几个位置都冲突，就会误判
  23. }

3.3 布隆过滤器的删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素

  • 布隆过滤器判断一个元素存在时可能存在误判，因此无法保证要删除的元素确实在布隆过滤器当中，此时将位图中对应的比特位清0会影响其他元素
  • 此外，就算要删除的元素确实在布隆过滤器当中，也可能该元素映射的多个比特位当中有些比特位是与其他元素共用的，此时将这些比特位清0也会影响其他元素

一种支持删除的方法：

将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。
缺陷：

  1. 无法确认元素是否真正在布隆过滤器中
  2. 存在计数回绕

布隆过滤器最终还是没有提供删除的接口，因为使用布隆过滤器本来就是要节省空间和提高效率的。在删除时需要遍历文件或磁盘中确认待删除元素确实存在，而文件IO和磁盘IO的速度相对内存来说是很慢的，并且为位图中的每个比特位额外设置一个计数器，就需要多用原位图几倍的存储空间，这个代价也是不小的

3.4 完整代码

  1. #pragma once
  2.  
  3. #include <bitset>
  4. #include <string>
  5.  
  6. namespace fy
  7. {
  8. struct BKDRHash
  9. {
  10. size_t operator()(const string& key)
  11. {
  12. size_t hash = 0;
  13. for (auto ch : key)
  14. {
  15. hash *= 131;
  16. hash += ch;
  17. }
  18. return hash;
  19. }
  20. };
  21.  
  22. struct APHash
  23. {
  24. size_t operator()(const string& key)
  25. {
  26. unsigned int hash = 0;
  27. int i = 0;
  28.  
  29. for (auto ch : key)
  30. {
  31. if ((i & 1) == 0)
  32. {
  33. hash ^= ((hash << 7) ^ (ch) ^ (hash >> 3));
  34. }
  35. else
  36. {
  37. hash ^= (~((hash << 11) ^ (ch) ^ (hash >> 5)));
  38. }
  39.  
  40. ++i;
  41. }
  42.  
  43. return hash;
  44. }
  45. };
  46.  
  47. struct DJBHash
  48. {
  49. size_t operator()(const string& key)
  50. {
  51. unsigned int hash = 5381;
  52.  
  53. for (auto ch : key)
  54. {
  55. hash += (hash << 5) + ch;
  56. }
  57.  
  58. return hash;
  59. }
  60. };
  61.  
  62. // 假设N是最多存储的数据个数
  63. // 平均存储一个值，开辟X个位
  64. template<size_t N,//位图长度，N*X需要开的空间大小
  65. size_t X = 4,//使用3个哈希函数，布隆过滤器的长度应该是插入元素个数的4倍左右
  66. class K = string,
  67. class HashFunc1 = BKDRHash,
  68. class HashFunc2  = APHash,
  69. class HashFunc3 = DJBHash
  70. //有需要再增加哈希函数
  71. >
  72.  
  73. class BloomFilter
  74. {
  75. public:
  76. void set(const K& key)
  77. {
  78. //计算出key对应的三个位的哈希地址
  79. size_t hash1 = HashFunc1()(key) % (N * X);
  80. size_t hash2 = HashFunc2()(key) % (N * X);
  81. size_t hash3 = HashFunc3()(key) % (N * X);
  82. //设置为1
  83. _bs.set(hash1);
  84. _bs.set(hash2);
  85. _bs.set(hash3);
  86. }
  87.  
  88. bool test(const K& key)
  89. {
  90. size_t hash1 = HashFunc1()(key) % (N * X);
  91. if (!_bs.test(hash1))
  92. {
  93. return false;
  94. }
  95.  
  96. size_t hash2 = HashFunc2()(key) % (N * X);
  97. if (!_bs.test(hash2))
  98. {
  99. return false;
  100. }
  101.  
  102. size_t hash3 = HashFunc3()(key) % (N * X);
  103. if (!_bs.test(hash3))
  104. {
  105. return false;
  106. }
  107. // 前面判断不在都是准确，不存在误判
  108.  
  109. return true; // 可能存在误判，映射几个位置都冲突，就会误判
  110. }
  111.  
  112. private:
  113. std::bitset<N* X> _bs;
  114. };
  116. void Test_BloomFilter()
  117. {
  118. srand(time(0));
  119. const size_t N = 100000;
  120. BloomFilter<N> bf;
  121.  
  122. std::vector<std::string> v1;
  123. std::string url = "https://blog.csdn.net/m0_64280701/article/details/129699384?spm=1001.2014.3001.5501";
  124.  
  125. for (size_t i = 0; i < N; ++i)
  126. {
  127. v1.push_back(url + std::to_string(i));
  128. }
  129.  
  130. for (auto& str : v1)
  131. {
  132. bf.set(str);
  133. }
  134.  
  135. // v2跟v1是相似字符串集，但是不一样
  136. std::vector<std::string> v2;
  137. for (size_t i = 0; i < N; ++i)
  138. {
  139. std::string url = "https://blog.csdn.net/m0_64280701/article/details/129699384?spm=1001.2014.3001.5501";
  140. url += std::to_string(999999 + i);
  141. v2.push_back(url);
  142. }
  143.  
  144. size_t n2 = 0;
  145. for (auto& str : v2)
  146. {
  147. if (bf.test(str))
  148. {
  149. ++n2;
  150. }
  151. }
  152. cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
  153.  
  154. // 不相似字符串集
  155. std::vector<std::string> v3;
  156. for (size_t i = 0; i < N; ++i)
  157. {
  158. string url = "zhihu.com";
  159. url += std::to_string(i + rand());
  160. v3.push_back(url);
  161. }
  162.  
  163. size_t n3 = 0;
  164. for (auto& str : v3)
  165. {
  166. if (bf.test(str))
  167. {
  168. ++n3;
  169. }
  170. }
  171. cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
  172. }
  173. }

四、布隆过滤器优点

  1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
  2. 哈希函数相互之间没有关系，方便硬件并行运算
  3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
  4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
  5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
  6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

五、布隆过滤器缺陷

  1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
  2. 不能获取元素本身
  3. 一般情况下不能从布隆过滤器中删除元素
  4. 如果采用计数方式删除，可能会存在计数回绕问题

----------------我是分割线---------------

文章到这里就结束了，下一篇即将更新

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览42750 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪