【数据结构】布隆过滤器——位图扩展

前端之家收集整理的这篇文章主要介绍了【数据结构】布隆过滤器——位图扩展前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

本篇博文,旨在介绍一种可以快速检索元素是否存在的数据结构 --- 布隆过滤器;本文从位图和布隆过滤器的对比,讨论了使用这两种数据结构的不同情况;并介绍了布隆过滤器的几种主要使用场景


布隆过滤器的引入

之前学习了位图,可以快速的判断一个整数是否存在于一个集合中

然而,现实生活中我们用的很多是字符串,单用位图处理不了字符串,由此引来了位图

布隆过滤器的思想

学过了哈希表后我们知道字符串哈希算法,可以将字符串转换为一个key值,然后存入位图

但是,通过字符串哈希算法后,也很有可能会造成哈希冲突(多个字符串映射成同一个key值),这样误判率就会很高

布隆过滤器的实现

于是,布隆过滤器就是采用同时进行多个字符串哈希算法,进行映射;

假设我们用5个字符串哈希算法进行映射,那么在判断一个字符串是否存在时,只需判断对应的五个位是否同时存在即可

布隆过滤器的代码实现

  1. #pragma once
  2.  
  3. #include<iostream>
  4. using namespace std;
  5.  
  6. //包我们自己定义的位图头文件
  7. #include"BitMap.h"
  8.  
  9. //定义五个字符串哈希算法
  10. template<class T>
  11. struct BKDRHash
  12. {
  13. size_t operator()(const T str)
  14. {
  15. register size_t hash = 0;
  16. for (size_t i = 0; i < str.size(); ++i)
  17. {
  18. hash = hash * 131 + str[i];
  19. }
  20. return hash;
  21. }
  22. };
  23.  
  24. template<class T>
  25. struct SDBMHash
  26. {
  27. size_t operator()(const T str)
  28. {
  29. register size_t hash = 0;
  30. for (size_t i = 0; i < str.size(); ++i)
  31. {
  32. hash = 65599 * hash + str[i];
  33. }
  34. return hash;
  35. }
  36. };
  37.  
  38. template<class T>
  39. struct RSHash
  40. {
  41. size_t operator()(const T str)
  42. {
  43. register size_t hash = 0;
  44. size_t magic = 63689;
  45. for (size_t i = 0; i < str.size(); ++i)
  46. {
  47. hash = hash * magic + str[i];
  48. magic *= 378551;
  49. }
  50. return hash;
  51. }
  52. };
  53.  
  54. template<class T>
  55. struct APHash
  56. {
  57. size_t operator()(const T str)
  58. {
  59. register size_t hash = 0;
  60. for (long i = 0; i < str.size(); ++i)
  61. {
  62. if ((i & 1) == 0)
  63. {
  64. hash ^= ((hash << 7) ^ str[i] ^ (hash >> 3));
  65. }
  66. else
  67. {
  68. hash ^= (~((hash << 11) ^ str[i] ^ (hash >> 5)));
  69. }
  70. }
  71. return hash;
  72. }
  73. };
  74.  
  75. template<class T>
  76. struct JSHash
  77. {
  78. size_t operator()(const T str)
  79. {
  80. if (str.empty())
  81. return 0;
  82. register size_t hash = 1315423911;
  83. for (size_t i = 0; i < str.size(); ++i)
  84. {
  85. hash ^= ((hash << 5) + str[i] + (hash >> 2));
  86. }
  87. return hash;
  88. }
  89. };
  90.  
  91. //定义布隆过滤器,5个HashFunc是五种不同的字符串哈希算法,用来辅助实现布隆过滤器
  92. template<typename K = string,typename HashFunc1 = BKDRHash<K>,typename HashFunc2 = SDBMHash<K>,typename HashFunc3 = RSHash<K>,typename HashFunc4 = APHash<K>,typename HashFunc5 = JSHash<K>>
  93. class BoolmFilter
  94. {
  95. public:
  96. BoolmFilter(size_t num)
  97. :_bp(num*2*5)
  98. {}
  99.  
  100. size_t HashFunC1(const K& num)
  101. {
  102. HashFunc1 hf;
  103. size_t index = hf(num);
  104. return index;
  105. }
  106. size_t HashFunC2(const K& num)
  107. {
  108. HashFunc2 hf;
  109. return hf(num);
  110. }
  111. size_t HashFunC3(const K& num)
  112. {
  113. HashFunc3 hf;
  114. return hf(num);
  115. }
  116. size_t HashFunC4(const K& num)
  117. {
  118. HashFunc4 hf;
  119. return hf(num);
  120. }
  121. size_t HashFunC5(const K& num)
  122. {
  123. HashFunc5 hf;
  124. return hf(num);
  125. }
  126. void Set(const K &num)
  127. {
  128. //用五中不同的字符串哈希算法求出五个不同的值
  129. size_t hf1 = HashFunC1(num);
  130. size_t hf2 = HashFunC2(num);
  131. size_t hf3 = HashFunC3(num);
  132. size_t hf4 = HashFunC4(num);
  133. size_t hf5 = HashFunC5(num);
  134.  
  135. //测试五个哈希值
  136. //cout << hf1 << " " << hf2 << " " << hf3 << " " << hf4 << " " << hf5 << endl;
  137.  
  138. //将五个值都放入位图中
  139. _bp.Set(hf1);
  140. _bp.Set(hf2);
  141. _bp.Set(hf3);
  142. _bp.Set(hf4);
  143. _bp.Set(hf5);
  144. }
  145.  
  146. //Reset可以用引用计数来实现
  147. //void Reset();
  148.  
  149. bool Find(K &num)
  150. {
  151. //分别判断num对应的五个值是否存在于位图中
  152. //若有一个不存在,则返回FALSE,num必定不存在
  153. //若都存在,则返回TRUE,但是不能确定一定存在
  154. int hf1 = HashFunC1(num);
  155. if(_bp.Find(hf1) == false)
  156. return false;
  157.  
  158. int hf2 = HashFunC2(num);
  159. if (_bp.Find(hf2) == false)
  160. return false;
  161.  
  162. int hf3 = HashFunC3(num);
  163. if (_bp.Find(hf3) == false)
  164. return false;
  165.  
  166. int hf4 = HashFunC4(num);
  167. if (_bp.Find(hf4) == false)
  168. return false;
  169.  
  170. int hf5 = HashFunC5(num);
  171. if (_bp.Find(hf5) == false)
  172. return false;
  173.  
  174. return true;
  175. }
  176. protected:
  177. //定义位图 _bp;
  178. BitMap _bp;
  179. };


布隆过滤器和位图的对比

位图的优点:

可以快速的判断一个整数是否存在于集合中

位图的缺点:

就如同其优点中说的,只能判断整数,无法处理其他类型的数据

布隆过滤器的优点:

1、在位图的基础上利用哈希算法进行扩充,使之可以处理字符串类型的数据

2、时间复杂度O(k),【K表示字符串哈希算法的个数】,其效率远高于其他的算法

布隆过滤器的缺点:

由于哈希冲突,布隆过滤器有一定的误判性,如何使用适量的字符串哈希算法是需要考虑的问题

布隆过滤器的误区:

使用字符串哈希算法的数量越多越好?(错)

这里要说明,字符串哈希算法过多,就会导致一个字符串会占好多个位,冲突的概率还会增大

所以,要使用适量的字符串哈希算法

布隆过滤器的几种主要应用场景:

(1)垃圾网站、邮件的过滤

(2)在爬虫中,如何快速的判断一个网页是否爬过也是布隆过滤器的使用场合之一

猜你在找的数据结构相关文章