布隆过滤器

末蓝、 2022-06-12 22:14 413阅读 0赞

布隆过滤器实际上就是哈希和位图的结合
它的优点：速度快并且节省空间
它的缺点：存在误判（比如存在不同的字符串可能存在相同的ASCII，这样我们在判断的时候就会出现误判）
这样的误判一定是发生在 判断它存在的情况下
误判一定不会发生在 不存在的情况下
为了降低误判率，我们必须尽可能的减少哈希冲突
也就是一个Key值可以有多个映射的位置

  1. #include<iostream>
  2. #include<stdlib.h>
  3. #include<string>
  4. #include"BitMap.h"
  5. using namespace std;
  6. template<class K>
  7. struct _HashFunc1
  8. {
  9.     size_t BKDRHash(const char *str)
  10.     {
  11.         register size_t hash = 0;
  12.         while (size_t ch = (size_t)*str++)
  13.         {
  14.             hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313.. 
  16.         }
  17.         return hash;
  18.     }
  20.     size_t operator()(const string &s)
  21.     {
  22.         return BKDRHash(s.c_str());
  23.     }
  24. };
  26. template<class K>
  27. struct _HashFunc2
  28. {
  29.     size_t SDBMHash(const char *str)
  30.     {
  31.         register size_t hash = 0;
  32.         while (size_t ch = (size_t)*str++)
  33.         {
  34.             hash = 65599 * hash + ch;
  35.             //hash = (size_t)ch + (hash << 6) + (hash << 16) - hash; 
  36.         }
  37.         return hash;
  38.     }
  40.     size_t operator()(const string &s)
  41.     {
  42.         return SDBMHash(s.c_str());
  43.     }
  44. };
  46. template<class K>
  47. struct _HashFunc3
  48. {
  49.     size_t RSHash(const char *str)
  50.     {
  51.         if (!*str)        // 这是由本人添加，以保证空字符串返回哈希值0 
  52.             return 0;
  53.         register size_t hash = 1315423911;
  54.         while (size_t ch = (size_t)*str++)
  55.         {
  56.             hash ^= ((hash << 5) + ch + (hash >> 2));
  57.         }
  58.         return hash;
  59.     }
  61.     size_t operator()(const string &s)
  62.     {
  63.         return RSHash(s.c_str());
  64.     }
  65. };
  67. template<class K>
  68. struct _HashFunc4
  69. {
  70.     size_t RSHash(const char *str)
  71.     {
  72.         register size_t hash = 0;
  73.         size_t magic = 63689;
  74.         while (size_t ch = (size_t)*str++)
  75.         {
  76.             hash = hash * magic + ch;
  77.             magic *= 378551;
  78.         }
  79.         return hash;
  80.     }
  82.     size_t operator()(const string&s)
  83.     {
  84.         return RSHash(s.c_str());
  85.     }
  86. };
  88. template<class K>
  89. struct _HashFunc5
  90. {
  91.     size_t RSHash(const char *str)
  92.     {
  93.         register size_t hash = 0;
  94.         size_t ch;
  95.         for (long i = 0; ch = (size_t)*str++; i++)
  96.         {
  97.             if ((i & 1) == 0)
  98.             {
  99.                 hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
  100.             }
  101.             else
  102.             {
  103.                 hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
  104.             }
  105.         }
  106.         return hash;
  107.     }
  109.     size_t operator()(const string &s)
  110.     {
  111.         return RSHash(s.c_str());
  112.     }
  113. };
  114. template<class K=string,typename HashFun1=_HashFunc1<K>,
  115.     typename HashFun2 = _HashFunc2<K>,
  116.     typename HashFun3 = _HashFunc3<K>,
  117.     typename HashFun4 = _HashFunc4<K>,
  118.     typename HashFun5 = _HashFunc5<K>>
  119. class BloomFiler
  120. {
  121. public:
  122.     BloomFiler(size_t n)
  123.         :_bp(n*5*2)
  124.         , _range(n*5*2)
  125.     {
  127.     }
  128.     void Set(const K&key)
  129.     {
  130.         size_t Hash1 = HashFun1()(key);
  131.         size_t Hash2 = HashFun2()(key);
  132.         size_t Hash3 = HashFun3()(key);
  133.         size_t Hash4 = HashFun4()(key);
  134.         size_t Hash5 = HashFun5()(key);
  135.         _bp.Set(Hash1%_range);
  136.         _bp.Set(Hash2%_range);
  137.         _bp.Set(Hash3%_range);
  138.         _bp.Set(Hash4%_range);
  139.         _bp.Set(Hash5%_range);
  140.     }
  141.     bool Test(const K&key)
  142.     {
  143.         size_t Hash1 = HashFun1()(key);
  144.         if (_bp.Test(Hash1%_range) == false)
  145.         {
  146.             return false;
  147.         }
  148.         size_t Hash2 = HashFun2()(key);
  149.         if (_bp.Test(Hash2%_range) == false)
  150.         {
  151.             return false;
  152.         }
  153.         size_t Hash3 = HashFun3()(key);
  154.         if (_bp.Test(Hash3%_range) == false)
  155.         {
  156.             return false;
  157.         }
  158.         size_t Hash4 = HashFun4()(key);
  159.         if (_bp.Test(Hash4%_range) == false)
  160.         {
  161.             return false;
  162.         }
  163.         size_t Hash5 = HashFun5()(key);
  164.         if (_bp.Test(Hash5%_range) == false)
  165.         {
  166.             return false;
  167.         }
  168.         return true;
  169.     }
  170. protected:
  171.     BitMap _bp;
  172.     size_t _range;
  173. };
  174. int main()
  175. {
  176.     BloomFiler<>bf(500);
  177.     string s1 = "child";
  178.     string s2 = "qqild";
  179.     string s3 = "eeild";
  180.     string s4 = "ddild";
  181.     bf.Set(s1);
  182.     bf.Set(s2);
  183.     bf.Set(s3);
  184.     bf.Set(s4);
  185.     cout<<bf.Test(s1)<<endl;
  186.     cout << bf.Test(s2) << endl;
  187.     cout << bf.Test(s3) << endl;
  188.     cout << bf.Test(s4) << endl;
  189.     system("pause");
  190.     return 0;
  191. }

但是这样的布隆过滤器不支持删除操作，因为可能会影响其他位置上的元素
因此为了支持删除操作将其修改成为引用计数版本的但是这样做必须要来维护引用计数，使用数组来存放引用计数，不再涉及位运算，因此这样做实际上去除了布隆过滤器原本节省空间的优势。

  1. #include<iostream>
  2. #include<stdlib.h>
  3. #include<vector>
  4. #include<string>
  5. #include"BitMap.h"
  6. using namespace std;
  7. template<class K>
  8. struct _HashFunc1
  9. {
  10.     size_t BKDRHash(const char *str)
  11.     {
  12.         register size_t hash = 0;
  13.         while (size_t ch = (size_t)*str++)
  14.         {
  15.             hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313.. 
  17.         }
  18.         return hash;
  19.     }
  21.     size_t operator()(const string &s)
  22.     {
  23.         return BKDRHash(s.c_str());
  24.     }
  25. };
  27. template<class K>
  28. struct _HashFunc2
  29. {
  30.     size_t SDBMHash(const char *str)
  31.     {
  32.         register size_t hash = 0;
  33.         while (size_t ch = (size_t)*str++)
  34.         {
  35.             hash = 65599 * hash + ch;
  36.             //hash = (size_t)ch + (hash << 6) + (hash << 16) - hash; 
  37.         }
  38.         return hash;
  39.     }
  41.     size_t operator()(const string &s)
  42.     {
  43.         return SDBMHash(s.c_str());
  44.     }
  45. };
  47. template<class K>
  48. struct _HashFunc3
  49. {
  50.     size_t RSHash(const char *str)
  51.     {
  52.         if (!*str)        // 这是由本人添加，以保证空字符串返回哈希值0 
  53.             return 0;
  54.         register size_t hash = 1315423911;
  55.         while (size_t ch = (size_t)*str++)
  56.         {
  57.             hash ^= ((hash << 5) + ch + (hash >> 2));
  58.         }
  59.         return hash;
  60.     }
  62.     size_t operator()(const string &s)
  63.     {
  64.         return RSHash(s.c_str());
  65.     }
  66. };
  68. template<class K>
  69. struct _HashFunc4
  70. {
  71.     size_t RSHash(const char *str)
  72.     {
  73.         register size_t hash = 0;
  74.         size_t magic = 63689;
  75.         while (size_t ch = (size_t)*str++)
  76.         {
  77.             hash = hash * magic + ch;
  78.             magic *= 378551;
  79.         }
  80.         return hash;
  81.     }
  83.     size_t operator()(const string&s)
  84.     {
  85.         return RSHash(s.c_str());
  86.     }
  87. };
  89. template<class K>
  90. struct _HashFunc5
  91. {
  92.     size_t RSHash(const char *str)
  93.     {
  94.         register size_t hash = 0;
  95.         size_t ch;
  96.         for (long i = 0; ch = (size_t)*str++; i++)
  97.         {
  98.             if ((i & 1) == 0)
  99.             {
  100.                 hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
  101.             }
  102.             else
  103.             {
  104.                 hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
  105.             }
  106.         }
  107.         return hash;
  108.     }
  110.     size_t operator()(const string &s)
  111.     {
  112.         return RSHash(s.c_str());
  113.     }
  114. };
  115. template<class K = string, typename HashFun1 = _HashFunc1<K>,
  116.     typename HashFun2 = _HashFunc2<K>,
  117.     typename HashFun3 = _HashFunc3<K>,
  118.     typename HashFun4 = _HashFunc4<K>,
  119.     typename HashFun5 = _HashFunc5<K >>
  120. class BloomFilerRef
  121. {
  122. public:
  123.     BloomFilerRef(const int&n)
  124.         : _range(n * 5 * 2)
  125.     {
  126.         _v.resize(n * 5 * 2);
  127.     }
  128.     void Set(const K&key)
  129.     {
  130.         size_t Hash1 = HashFun1()(key)%_range;
  131.         _v[Hash1]++;
  132.         size_t Hash2 = HashFun2()(key) % _range;
  133.         _v[Hash2]++;
  134.         size_t Hash3 = HashFun3()(key) % _range;
  135.         _v[Hash3]++;
  136.         size_t Hash4 = HashFun4()(key) % _range;
  137.         _v[Hash4]++;
  138.         size_t Hash5 = HashFun5()(key) % _range;
  139.         _v[Hash5]++;
  140.     }
  141.     void Reset(const K&key)
  142.     {
  143.         size_t Hash1 = HashFun1()(key) % _range;
  144.         _v[Hash1]--;
  145.         size_t Hash2 = HashFun2()(key) % _range;
  146.         _v[Hash2]--;
  147.         size_t Hash3 = HashFun3()(key) % _range;
  148.         _v[Hash3]--;
  149.         size_t Hash4 = HashFun4()(key) % _range;
  150.         _v[Hash4]--;
  151.         size_t Hash5 = HashFun5()(key) % _range;
  152.         _v[Hash5]--;
  153.     }
  154.     bool Test(const K&key)
  155.     {
  156.         size_t Hash1 = HashFun1()(key) % _range;
  157.         if (_v[Hash1] == false)
  158.         {
  159.             return false;
  160.         }
  161.         size_t Hash2 = HashFun1()(key) % _range;
  162.         if (_v[Hash2] == false)
  163.         {
  164.             return false;
  165.         }
  166.         size_t Hash3 = HashFun1()(key) % _range;
  167.         if (_v[Hash3] == false)
  168.         {
  169.             return false;
  170.         }
  171.         size_t Hash4 = HashFun1()(key) % _range;
  172.         if (_v[Hash4] == false)
  173.         {
  174.             return false;
  175.         }
  176.         size_t Hash5 = HashFun1()(key) % _range;
  177.         if (_v[Hash5] == false)
  178.         {
  179.             return false;
  180.         }
  181.         return true;
  182.     }
  183. protected:
  184.     vector<size_t>_v;
  185.     size_t _range;
  186. };

发表评论

表情：
评论列表 （有 0 条评论，413人围观）

还没有评论，来说两句吧...

相关阅读

    相关 布隆过滤器

    布隆过滤器 什么是布隆过滤器？ 布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的`二进制向量`和`一系列随机映射函数`。布

    古城微笑少年丶古城微笑少年丶/ 0 赞/ 354 阅读

    相关 布隆过滤器

    > 布隆过滤器\[1\]（Bloom Filter）是由布隆在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一

    r囧r小猫r囧r小猫/ 0 赞/ 358 阅读

    相关 布隆过滤器

    布隆过滤器实际上就是哈希和位图的结合 它的优点：速度快并且节省空间 它的缺点：存在误判（比如存在不同的字符串可能存在相同的ASCII，这样我们在判断的时候就会出现误判）

    末蓝、末蓝、/ 0 赞/ 414 阅读

    相关 布隆过滤器

    布隆过滤器原理 布隆过滤器有什么用？ 布隆过滤器是可以用于判断一个元素是不是在一个集合里，并且相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。 特

    系统管理员系统管理员/ 0 赞/ 416 阅读

    相关 布隆过滤器

    布隆过滤器介绍 > 布隆过滤器在wiki上的介绍: 布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布

    喜欢ヅ旅行喜欢ヅ旅行/ 0 赞/ 501 阅读

    相关 布隆过滤器

    布隆过滤器常常被用来检测某个元素是否是巨量数据集合中的成员 1、基本原理： (1)将长度为m的位数组元素全部置为0； (2)对集合S中的某个成员a，分别用k个哈希函数对其

    亦凉亦凉/ 0 赞/ 518 阅读