哈希扩展（位图与布隆过滤器）

位图

   题目：从40亿个没有排序的无符号整数查找一个数是否存在
  

• 方法一：
  依次遍历：O(N) 太慢了
  
• 排序 + 二分
  

1G = 1024MB = 1024 * 1024KB = 1024 1024*1024byte ~= 10亿byte。*
10亿byte是一个G，那么40亿个整形为160亿字节 ,也就是16GB的内存，那我们内存肯定放不下，但是内存却放不下。

• 位图
  

                                              2                            32                                       2^{32}                  232 = 42亿多，那么其实我们并不须要把每一个数都存储下来，我们可以使用一个bit位来表示它在不在即可，那么一个字节是8个比特位，以是我们所须要的空间为，$2^{32} /$8 ~= 5亿 ~= 500MB。那么500MB是可以担当的。

如上图，每一个蓝色方块代表的是一个整形，每个整型都有32位bit位，以第一个整型为例，我们可以表示 0~31这个范围的数字在不在，**如果在对应的bit位就变为1，如果不在对应的bit位就是0。**那我们如何直到插入的数字x是那个位置的呢？                                   i                         =                         x                         /                         32                              i = x / 32                  i=x/32，                                   j                         =                         x                              j = x % 32                  j=x，我们这里的                                   i                              i                  i表示我们对应的哪个整型，而                                   j                              j                  j表示对应的整型的哪个bit位。
位图代码实现：

1. namespace bit
2. {
3.         template<size_t N>
4.         class bitset
5.         {
6.         public:
7.                 bitset()
8.                 {
9.                         _bs.resize(N/32 + 1);
10.                 }
11.                 void set(size_t x)
12.                 {
13.                         int i = x / 32;
14.                         int j = x % 32;
15.                         //把对应的第j个bit位变为1，其他位置不变
16.                         //j = 4,  00000000 |= 00010000 = 00010000
17.                         _bs[i] |= (1 << j);
18.                 }
20.                 void reset(size_t x)
21.                 {
22.                         int i = x / 32;
23.                         int j = x % 32;
24.                         //把对应的第j个bit位变为0，其他位置不变
25.                         //j = 4,  00000000 &= (~00010000) -> 11101111 = 00000000
26.                         _bs[i] &= (~(1 << j));
27.                 }
29.                 //验证x是否存在
30.                 bool test(size_t x)
31.                 {
32.                         int i = x / 32;
33.                         int j = x % 32;
34.                         return (_bs[i] & (1 << j));
35.                 }
36.         private:
37.                 vector<int> _bs;
38.         };
39. }

复制代码

上图的蓝色方块其实就是一个个的整型，我们创建一个vector来存储每一个整型，在创建vector的时候，我们要根据数据的范围来初始化vector大小，由于一个整型最大为42亿多，以是我们最多须要开辟134217728个整型。而我们vector是在堆区上开辟的以是也就不会存在内存不够的题目。如许查询42亿中一个数是否存在我们就可以在内存当中操控了。134217728*4 = 536,870,912 ~= 500MB。
总结一下位图：

• 优点：效率高，方便插入与删除
  
• 缺点：只得当整型。
  

如上图，库里面其实也实现了bitset，只不过它实现的方式和我们的差别，库里面直接使用一个整型来存储对应位置是否存在，以是他这里如果直接存储42亿的话还会报错，空间太大了。
布隆过滤器

   布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比力奇妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西肯定不存在或者大概存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节流大量的内存空间
  布隆过滤器是哈希表和位图的结合使用，我们使用hash函数来把字符串变为整型，让对应位图中的位置变为1。相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。
实现原理：

HashMap的题目

追念一下，如果让你判断一个某个元素是否存在的时候，信赖大部分人都会选择HashMap，O(1)时间就可以得出结果了，但是HashMap的缺点就是空间消耗太大了，而且由于负载因子的原因，我们数组并不能被放满，那么当数据量很大比方上亿的时候，所需内存空间也很大。
布隆过滤器结果

布隆过滤器跟位图的一样的，如下图：

和位图不一样的是，我们的位置是由哈希函数算出来的，以是我们不但单可以使用整型也可以使用字符串，通过对应的哈希函数转为整型，而由于字符串哈希函数大概会（"abcba）和（“caabb”）产生冲突，我们一样寻常一个元素会有多个哈希函数来盘算出差别的位置，如许可以降低冲突几率。

如上图，我们"abandon"通过三个哈希函数算出来的位置为：                                   [                         3                         ,                         8                         ,                         12                         ]                              [3,8,12]                  [3,8,12]，而                                   "                         b                         a                         i                         d                         u                         "                              "baidu"                  "baidu"通过三个函数算出来的位置为：                                   [                         5                         ,                         8                         ,                         10                         ]                              [5,8,10]                  [5,8,10]，这也就代表了我们这个位置大概会被别的字符串占用，这也就导致了我们布隆过滤器大概会出现误判的情况。
比方：随着数据量的增长，我们即是内存里面并没有                                   "                         a                         p                         p                         l                         e                         "                              "apple"                  "apple"这个字符串，但是通过哈希函数算出来的位置都被别人占完了，以是 即是内存里面并没有这个元素，返回的结果也大概为有。
同时布隆过滤器另有几个公式：
m : 表示布隆过滤器中bit的位数
n：表示插入元素的个数
k：表示哈希函数的个数
结论：
当哈希函数个数固定的时候我们有一个结论：                                   (                         误判率                         )                         f                         (                         k                         )                         =                         (                         1                         −                                   1                                       e                                                        n                                     k                                              m                                                                 )                            k                                       (误判率) f(k) = (1-\frac{1}{{e^{\frac{nk}{m}}}})^k                  (误判率)f(k)=(1−emnk​1​)k这就意味着我们的n越大，我们的分母越大，整个数越小，1-这个数就越大，以是误判率就越大，而我们的m越大我们的误判率越小。 m/n越大，误判率越小。
当我们的n和m固定的时候，                                   k                         =                                   m                            n                                  l                         n                         2                              k = \frac{m}{n}ln2                  k=nm​ln2 误判率最小。
当我们误判率p和插入个数n去确定的情况下，通逾盼望的误判率和插入个数可以得出来我们的bit长度为：                                   m                         =                         −                                              n                               l                               n                               p                                                 (                               l                               n                               2                                           )                                  2                                                            m = -\frac{nlnp}{(ln2)^2}                  m=−(ln2)2nlnp​。
代码实现：

1. //三个哈希函数
2. struct BKDRHash
3. {
4.         size_t operator()(const string& s)
5.         {
6.                 // BKDR
7.                 size_t value = 0;
8.                 for (auto ch : s)
9.                 {
10.                         value *= 31;
11.                         value += ch;
12.                 }
13.                 return value;
14.         }
15. };
17. struct DJBHash
18. {
19.         size_t operator()(const string& s)
20.         {
21.                 size_t hash = 5381;
22.                 for (auto ch : s)
23.                 {
24.                         hash += (hash << 5) + ch;
25.                 }
26.                 return hash;
27.         }
28. };
30. struct APHash
31. {
32.         size_t operator()(const string& s)
33.         {
34.                 size_t hash = 0;
35.                 for (long i = 0; i < s.size(); i++)
36.                 {
37.                         if ((i & 1) == 0)
38.                         {
39.                                 hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
40.                         }
41.                         else
42.                         {
43.                                 hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
44.                         }
45.                 }
46.                 return hash;
47.         }
48. };
50. namespace bit
51. {
52.         //N表示插入个数，X表示 M / N (M为bit长度)
53.         template<size_t N,
54.                         size_t X = 5,
55.                         class K = string,
56.                         class Hash1 = BKDRHash,
57.                         class Hash2 = DJBHash,
58.                         class Hash3 = APHash>
59.         class boolmfilter
60.         {
61.         public:
62.                 void set(const K& key)
63.                 {
64.                         size_t M = N * X;
65.                         //分别求出对应的整型
66.                         size_t hash1 = Hash1()(key) % M;
67.                         size_t hash2 = Hash2()(key) % M;
68.                         size_t hash3 = Hash3()(key) % M;
70.                         //设置到位图当中
71.                         _bs.set(hash1);
72.                         _bs.set(hash2);
73.                         _bs.set(hash3);
74.                 }
76.                 bool test(const K& key)
77.                 {
78.                         size_t M = N * X;
79.                         //三个位置当中只要有一个位置不存在，那么这个元素一定不存在。
80.                         size_t hash1 = Hash1()(key) % M; //不能超过bit数组可容纳的长度
81.                         if (!_bs.test(hash1))
82.                                 return false;
83.                         size_t hash2 = Hash2()(key) % M;
84.                         if (!_bs.test(hash2))
85.                                 return false;
86.                         size_t hash3 = Hash3()(key) % M;
87.                         if (!_bs.test(hash3))
88.                                 return false;
90.                         //如果三个位置都存在也不一定存在，可能是其他元素把位置占完了。
91.                         return true;
92.                 }
93.         private:
94.                 bit::bitset<N*X> _bs;
95.         };
96. }
98. void Test_boolmfilter()
99. {
100.         string s1("apple");
101.         string s2("banana");
102.         string s3("pear");
104.         bit::boolmfilter<10> bs1;
105.         bs1.set(s1);
106.         bs1.set(s2);
107.         bs1.set(s3);
109.         //前三个在，后三个不在
110.         cout << bs1.test(s1) << endl;
111.         cout << bs1.test(s2) << endl;
112.         cout << bs1.test(s3) << endl;
113.         cout << bs1.test("aaaa") << endl;
114.         cout << bs1.test("bbbb") << endl;
115.         cout << bs1.test("cccc") << endl;
116. }

复制代码

固然了想要测出来原来不在的却输出在我们还须要更多的数据，这里数据太少了测不出来。

1. //测试相似误判和不相似误判
2. void Test_BoolFilter()
3. {
4.         srand(time(0));
5.         const int N = 1000000;
6.         vector<string> v;
7.        
8.     //原始数据
9.         bit::boolmfilter<N> bs;
10.         string url = "https://blog.csdn.net/anjibgdexuexi?type=blog";
11.         for (int i = 0; i < N; i++)
12.         {
13.                 v.push_back(url + std::to_string(i));
14.         }
15.         for (auto& e : v) bs.set(e);
17.         v.clear();
18.         //相似数据，相同前缀，不同后缀
19.         for (int i = 0; i < N; i++)
20.         {
21.                 string nurl = url;
22.                 nurl += std::to_string(9999999 + i);
23.                 v.push_back(nurl);
24.         }
25.         int n = 0;
26.         for (auto& e : v)
27.         {
28.                 if (bs.test(e))
29.                         n++;
30.         }
31.         cout << "相似字符串误判率：" << (double)n / (double)N << endl;
33.         v.clear();
35.         //不相似，前后缀都不一样
36.         for (int i = 0; i < N; i++)
37.         {
38.                 string str = "孙悟空";
39.                 str += std::to_string(rand() + i);
40.                 v.push_back(str);
41.         }
43.         int n1 = 0;
44.         for (auto& e : v)
45.         {
46.                 if (bs.test(e))
47.                         n1++;
48.         }
49.         cout << "不相似字符串误判率：" << (double)n1 / (double)N << endl;
50. }

复制代码

上段测试代码，我们就可以看到布隆过滤器的误判率了，同时当我们m/n越大我们误判率就越小。
海量数据处置惩罚

位图应用

   

• 给定100亿个整数，设盘算法找到只出现一次的整数？
  

  由于有一百亿个整数，但是由于整数最大的值就是42亿多，以是我们设置bit位长度的时候只须要设置                                             2                            32                                       2^{32}                  232即可。剩下的大量的重复值。当我们须要记录某个元素的出现次数的时候我们一样寻常想到的都是哈希表，这里数据量太大内存肯定是不够的，以是我们可以使用位图。上述我们位图每个元素用一个bit位来表示在不在。
那么这里的话我们只须要使用两个bit位来表示：

• 如果两个bit位都是0，说明不在
  
• 如果第一个为0，第二个为1，表示出现了一次
  
• 如果第一个为1，第二个为0，表示出现了2次
  
• 如果两个都为1，表示出现了三次及以上
  

代码实现：以下代码对于超过两次的统一设置为3次。

1. template<size_t N>
2.         class twobitset
3.         {
4.         public:
5.                 twobitset()
6.                 {
7.                         _bs.resize(N / 32 + 1);
8.                 }
9.                 void set(size_t x)
10.                 {
11.                         int i = x / 16;
12.                         int j = x % 16;
13.                         //第j位和j+16位来表示
14.                         int one = (_bs[i] & (1 << (j+16))) > 0; //获取第j+16位
15.                         int two = (_bs[i] & (1 << j)) > 0;       //获取第j位
16.                         if (one == 0 && two == 0) // 00 ->01
17.                         {
18.                                 _bs[i] |= (1 << j);
19.                         }
20.                         else if (one == 0 && two == 1) // 01 -> 10
21.                         {
22.                                 _bs[i] &= (~(1 << j));
23.                                 _bs[i] |= (1 << (j + 16));
24.                         }
25.                         else if (one == 1 && two == 0) // 10 -> 11
26.                         {
27.                                 _bs[i] |= (1 << j);
28.                         }
29.                 }
30.                 //验证x是否存在
31.                 int test(size_t x)
32.                 {
33.                         int i = x / 16;
34.                         int j = x % 16;
36.                         //第j位和j+16位来表示
37.                         int one = (_bs[i] & (1 << (j + 16))) > 0; //获取第j+16位
38.                         int two = (_bs[i] & (1 << j)) > 0;       //获取第j位
40.                         if (one == 0 && two == 0) // 00 ->01
41.                         {
42.                                 return 0;
43.                         }
44.                         else if (one == 0 && two == 1) // 01 -> 10
45.                         {
46.                                 return 1;
47.                         }
48.                         else if (one == 1 && two == 0) // 10 -> 11
49.                         {
50.                                 return 2;
51.                         }
52.                         else
53.                                 return 3;
54.                 }
55.         private:
56.                 vector<int> _bs;
57.         };

复制代码

如上段代码，我们用每个整型的前16个bit位和后16个bit位表示出现的次数。但其实另有另一种实现方式，我们直接使用两个位图，那么次数还是一样的变化过程，而且比我们上面这种方式要简单很多，直接复用位图的成员函数。
代码实现：

1.         template<size_t N>
2.         class twobitset
3.         {
4.         public:
5.                 void set(size_t x)
6.                 {
7.                         if (_bs1.test(x) == 0 && _bs2.test(x) == 0) // 00 ->01
8.                         {
9.                                 _bs2.set(x);
10.                         }
11.                         else if (_bs1.test(x) == 0 && _bs2.test(x) == 1) // 01 -> 10
12.                         {
13.                                 _bs2.reset(x);
14.                                 _bs1.set(x);
15.                         }
16.                         else if (_bs1.test(x) == 1 && _bs2.test(x) == 0) // 10 -> 11
17.                         {
18.                                 _bs2.set(x);
19.                         }
20.                         //超过两次的这里不处理
21.                 }
22.                 //验证x是否存在
23.                 int test(size_t x)
24.                 {
26.                         if (_bs1.test(x) == 0 && _bs2.test(x) == 0) // 00
27.                         {
28.                                 return 0;
29.                         }
30.                         else if (_bs1.test(x) == 0 && _bs2.test(x) == 1) // 01
31.                         {
32.                                 return 1;
34.                         }
35.                         else if (_bs1.test(x) == 1 && _bs2.test(x) == 0) // 10
36.                         {
37.                                 return 2;
39.                         }
40.                         else
41.                                 return 3;
42.                 }
43.         private:
44.         //直接复用位图
45.                 bit::bitset<N> _bs1;
46.                 bit::bitset<N> _bs2;
47.         };
48. }

复制代码

  

• 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
  

  使用位图遍历其中一个文件，统计每个元素是否存在，然后再依次遍历另一个文件，如果在位图中，则 参加到交集里面。
   

• 位图应用变形：1个文件有100亿个int，1G内存，设盘算法找到出现次数不超过2次的全部整数
  

  如上段代码，都已次数小于即是2的即可。
布隆过滤器应用

   

• 给两个文件，分别有100亿个query（查询字符串），我们只有1G内存，如何找到两个文件交集？ 假设每一个query都有50个字节，那么一共有5000亿字节 ~= 500G内存，那如何做呢？
  

  

• 平均分成1000个小文件。
  

如上图，我们把大文件A和大文件B均分为1000个小文件，然后再进行查找交集，但是这里有均分会有一个题目，我们A0须要去和                                   B                         0                         ,                         B                         1...                         B                         999                              B0,B1...B999                  B0,B1...B999每一个都要去找交集，A1也是一样那么这里就是                                   O                         (                                   N                            2                                  )                              O(N^2)                  O(N2)的时间复杂度。

• 哈希切分
  

我们通过哈希函数求出每个                                        q                            u                            e                            r                            y                                  query                     query然后对1000取模，就可以求出这1000个小文件对应的坐标，那么我们                                        A                            i                                  Ai                     Ai小文件就不须要每个都要和                                        B                            i                                  Bi                     Bi小文件去查交集了。
由于我们雷同字符串通过哈希函数%1000肯定求出来的是同一个坐标，不大概求出来的坐标差别，以是我们                                   A                         i                              Ai                  Ai只需和对应的                                   B                         i                              Bi                  Bi去找交集即可，如许时间复杂度有                                   O                         (                                   N                            2                                  )                         −                         >                         O                         (                         N                         )                              O(N^2)->O(N)                  O(N2)−>O(N)。不过这里有个缺陷，由于布隆过滤器会出现误判的情况，对与交集我们肯定不会错，但是不是交集的大概也被误判进去了O.o?。
但是哈希切分另有一个题目，那就是有大概其中一个文件特殊大，几G或者几十G都有大概（重复值过多或求出来的哈希值一样），本质上都是哈希冲突，那怎么办呢？
针对这个题目可以进行二次分别，再使用一个新的哈希函数进行求坐标。就是当一个文件的内容太大的时候，在对这个                                   A                         i                              Ai                  Ai分别为多个                                   A                         A                         i                              AAi                  AAi，于此同时我们对应的                                   B                         i                              Bi                  Bi也须要分别为多个                                   B                         B                         i                              BBi                  BBi。但其实我们可以不管这个题目，无论文件多么的大，我们都直接使用set插入即可。
我们set插入失败只有两种大概：1. query已存在。2. 内存不够，那么如果是重复值过多的情况下，由于set的特性就可以办理，如果真的就是哈希函数不可，我们差别的值也很多， 那么单独对这个文件再换一个哈希函数进行重新分别即可。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。