【C++】-- 哈希应用之布隆过滤器（一）

2023-02-07 85

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【C++】-- 哈希应用之布隆过滤器

一、布隆过滤器介绍

位图有使用起来，节省空间，并且效率高的优点。位图的缺点，只能处理整形。

假如起昵称时要看一个字符串有没有被占用，用一个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）一般情况下不能从布隆过滤器中删除元素

（4）如果采用计数方式删除，可能会存在计数回绕问题