【数据结构】布隆过滤器

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

布隆过滤器

原理

  如果要判断一个数是不是在一个集合里,一半想到的是将所有的元素保存起来,然后通过比较确定。但是随着集合中元素的增加,需要的存储空间越来越大,检索速度自然会变慢。这时会有人想到使用哈希表,将元素通过哈希函数映射到一个位阵列中,将相应的比特位置为1,这样就可以判断这个元素是不是在集合之中了。
  但是哈希有一个很严重的问题,那就是哈希冲突。针对这个问题,我们的解决方法是使用多个哈希函数,用多个位表示一个值,如果它们之中有一个说元素不在集合中,那么这个元素势必就不在;但是反过来,它们都说在,却是不一定在集合之中,因为有可能它们在说谎。

优缺点

  布隆过滤器就是用于检索一个元素是否字一个集合之中,它的优点是空间效率和查询时间都由于其他一般的算法,缺点是有一定的几率识别错误,并且删除困难。
  
  之所以会出现删除困难,是因为由于哈希冲突,可能一个位被多次置1,如果我们直接删除,那么就会出现错误。如果一定要实现删除功能的话,可以想到将位数组换成一般的数组。将其初始化为0,然后每增加一个元素,相应的位置加1,删除的时候相应的位置减1就可以了。

算法实现

  1. 我们实现的布隆过滤器,底层搭载的是位图,关于位图的概念及实现,参考这里
  2. 关于哈希函数们可以参考这篇文章http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html,这里介绍了很多哈希函数

  1. //comm.hpp
  2. //这里的哈希函数都来自上面的文章
  3. #pragma once
  4. #include <string>
  5. using namespace std;
  6. class KeyToInt1
  7. {
  8. public:
  9. size_t operator()(const string& s)
  10. {
  11. return BKDRHash(s.c_str());
  12. }
  13. private:
  14. size_t BKDRHash(const char *str)
  15. {
  16. register size_t hash = 0;
  17. while (size_t ch = (size_t)*str++)
  18. {
  19. hash = hash * 131 + ch;
  20. }
  21. return hash;
  22. }
  23. };
  24.  
  25. class KeyToInt2
  26. {
  27. public:
  28. size_t operator()(const string& s)
  29. {
  30. return SDBMHash(s.c_str());
  31. }
  32. private:
  33. size_t SDBMHash(const char *str)
  34. {
  35. register size_t hash = 0;
  36. while (size_t ch = (size_t)*str++)
  37. {
  38. hash = 65599 * hash + ch;
  39. //hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
  40. }
  41. return hash;
  42. }
  43. };
  44.  
  45.  
  46. class KeyToInt3
  47. {
  48. public:
  49. size_t operator()(const string& s)
  50. {
  51. return RSHash(s.c_str());
  52. }
  53. private:
  54. size_t RSHash(const char *str)
  55. {
  56. register size_t hash = 0;
  57. size_t magic = 63689;
  58. while (size_t ch = (size_t)*str++)
  59. {
  60. hash = hash * magic + ch;
  61. magic *= 378551;
  62. }
  63. return hash;
  64. }
  65. };
  66.  
  67.  
  68. class KeyToInt4
  69. {
  70. public:
  71. size_t operator()(const string & s)
  72. {
  73. return APHash(s.c_str());
  74. }
  75. private:
  76. size_t APHash(const char *str)
  77. {
  78. register size_t hash = 0;
  79. size_t ch;
  80. for (long i = 0; ch = (size_t)*str++; i++)
  81. {
  82. if ((i & 1) == 0)
  83. {
  84. hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
  85. }
  86. else
  87. {
  88. hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
  89. }
  90. }
  91. return hash;
  92. }
  93. };
  94.  
  95.  
  96. class KeyToInt5
  97. {
  98. public:
  99. size_t operator()(const string& s)
  100. {
  101. return JSHash(s.c_str());
  102. }
  103. private:
  104. size_t JSHash(const char *str)
  105. {
  106. if (!*str) // 这是由本人添加,以保证空字符串返回哈希值0
  107. return 0;
  108. register size_t hash = 1315423911;
  109. while (size_t ch = (size_t)*str++)
  110. {
  111. hash ^= ((hash << 5) + ch + (hash >> 2));
  112. }
  113. return hash;
  114. }
  115. };
  1. //具体实现
  2. #include "comm.hpp"
  3. #include "bitMap.hpp"
  4. #include <iostream>
  5.  
  6. template <class K,class KToInt1 = KeyToInt1,class KToInt2 = KeyToInt2,class KToInt3 = KeyToInt3,class KToInt4 = KeyToInt4,class KToInt5 = KeyToInt5>
  7. class BloomFilter
  8. {
  9. public:
  10. BloomFilter(size_t size)//size表示存储的元素个数,5个比特位表示一个元素
  11. : _bmp(size * 10),_size(0)
  12. {}
  13.  
  14. bool Insert(const K& key)//插入元素
  15. {
  16. size_t bitCount = _bmp.Size();//位图能存储bitCount个比特位
  17. size_t index1 = KToInt1()(key) % bitCount;//字符串转换成整型,转换后的数字可能大于位图的位数,所以要取模
  18. size_t index2 = KToInt2()(key) % bitCount;
  19. size_t index3 = KToInt3()(key) % bitCount;
  20. size_t index4 = KToInt4()(key) % bitCount;
  21. size_t index5 = KToInt5()(key) % bitCount;
  22.  
  23. _bmp.Set(index1);//整型插入到位图中
  24. _bmp.Set(index2);
  25. _bmp.Set(index3);
  26. _bmp.Set(index4);
  27. _bmp.Set(index5);
  28. _size++;
  29.  
  30. cout << index1 << " " << index2 << " " << index3 << " " << index4 << " " << index5;//打印索引,做测试
  31. cout << endl;
  32. return true;
  33. }
  34.  
  35. bool IsInBloomFilter(const K& key)//判断一个元素是否在集合中
  36. {
  37. size_t bitCount = _bmp.Size();
  38. size_t index1 = KToInt1()(key) % bitCount;
  39. size_t index2 = KToInt2()(key) % bitCount;
  40. size_t index3 = KToInt3()(key) % bitCount;
  41. size_t index4 = KToInt4()(key) % bitCount;
  42. size_t index5 = KToInt5()(key) % bitCount;
  43. if (!_bmp.Test(index1))
  44. return false;//index1表明key不在位图中,说明key一定不在其中
  45. if (!_bmp.Test(index2))
  46. return false;
  47. if (!_bmp.Test(index3))
  48. return false;
  49. if (!_bmp.Test(index4))
  50. return false;
  51. if (!_bmp.Test(index5))
  52. return false;
  53. return true;//五个索引表明都在,key才有可能在其中
  54. }
  55.  
  56. private:
  57. BitMap _bmp;//位图存储元素
  58. size_t _size;//表示存了几个元素
  59. };
  60.  
  61.  
  62. void test()
  63. {
  64. BloomFilter<string> b(5);
  65. b.Insert("小明");
  66. b.Insert("小黄");
  67. b.Insert("小花");
  68. b.Insert("小兰");
  69. b.Insert("小熊");
  70. b.Insert("小泽");
  71. if (b.IsInBloomFilter("小熊"))
  72. cout << "小熊在名单之中" << endl;
  73. if (!b.IsInBloomFilter("小王"))
  74. cout << "小王不在名单之中" << endl;
  75. }

测试结果:

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