【C++/STL】：哈希的应用 -- 位图布隆过滤器

🚀🚀前言

在前面的文章里我们已经学习了什么是哈希和以哈希表为底层的unordered系列容器的使用。本篇文章的位图&布隆过滤器也是哈希思想下的产物，经常使用它们来解决有关海量数据的问题。

一，位图

1. 位图的概念

在引出位图的概念之前，先来看一个经典面试题：

深入分析：

解题思路2是否可行，我们先算算40亿个数据⼤概需要多少内存。
1G = 1024MB =1024 * 1024KB = 1024*1024 * 1024byte约等于10亿多byte，那么40亿个整数约等于16G，说明40亿个数是无法直接放到内存中的，只能放到硬盘文件中。而二分查找只能对内存数组中的有序数据进行查找。

解题思路3：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使⽤⼀个⼆进制⽐特位来代表数据是否存在的信息，如果⼆进制⽐特位为1，代表存在，为0代表不存在。

那么我们设计⼀个⽤二进制比特位表⽰数据是否存在的数据结构，这个数据结构就叫位图。

2. STL库中的位图

根据文档可知，位图bitset 是非类型模板，N是指需要多少比特位。使用时需要包含头文件：

#include <bitset>

位图常用的核心接口主要有三个：

(1) x 映射位标记成1(插入 x，有这个数据了)

(2) x 映射位标记成0(删除 x，没有这个数据了)

(3) 检查是否存在这个数据
x映射的位是1，返回真
x映射的位是0，返回假

3. 位图的设计

位图本质是⼀个直接定址法的哈希表，每个整型值映射⼀个bit位，位图提供控制这个bit的相关接口。

实现中需要注意的是，C/C++没有对应位的类型，只能看int/char这样整形类型，我们再通过位运算去控制对应的⽐特位。⽐如我们数据存到vector< int >中，相当于每个int值映射对应的32个值，⽐如第⼀个整形映射0-31对应的位，第⼆个整形映射32-63对应的位，后⾯的以此类推，那么来了⼀个整形值x，i = x / 32；j = x % 32；计算出x映射的值在vector的第 i 个整形数据的第 j 位。

4. 位图的模拟实现

#include<vector>//非类型模板参数。需要多少比特位
template <size_t N>
class bitset
{
public:bitset(){_bs.resize(N / 32 + 1);}//x映射位标记成1void set(size_t x){//映射的位置：第i个整型数据的第j位size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);}//x映射位标记成0void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j));}//x映射的位是1，返回真//x映射的位是0，返回假bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);}
private:vector<size_t> _bs;
};

5. 位图的优缺点

优点：增删查改快，节省空间
缺点：只适⽤于整形

6. 位图相关考察题⽬

深入分析：

第一题和第三题是同一类型的题，我们先来分析这两题。首先我们知道把数据放入位图中只能标记在或不在两种状态，而题目要求的是找出出现几次的数据，可能是出现0次，1次……，显然单用一个位图的一个比特位是无法满足的。

用两个位图的标记就可以解决。我们规定00表示数据出现0次，01表示数据出现1次，10表示数据出现2次，11表示数据出现3次及以上

代码实现如下：
注意：这里用的bitset是上文我们自己实现的bitset。

我们针对第一题和第三题设计一个结构：

template<size_t N>
class twobitset
{
public:void set(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2) // 00->01{_bs2.set(x);}else if (!bit1 && bit2) // 01->10{_bs1.set(x);_bs2.reset(x);}else if (bit1 && !bit2) // 10->11{_bs1.set(x);_bs2.set(x);}}// 返回0 出现0次数// 返回1 出现1次数// 返回2 出现2次数// 返回3 出现2次及以上int get_count(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2){return 0;}else if (!bit1 && bit2){return 1;}else if (bit1 && !bit2){return 2;}else{return 3;}}private:bitset<N> _bs1;bitset<N> _bs2;
};//测试代码，可以统计出100以内哪个数据出现了几次
void test_twobitset()
{twobitset<100> tbs; //开100个bit位int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9 };for (auto e : a){tbs.set(e);}for (size_t i = 0; i < 100; ++i){cout << i << "->" << tbs.get_count(i) << endl;//if (tbs.get_count(i) == 1 || tbs.get_count(i) == 2)//cout << i << endl;}
}

第二题的代码实现：
把数据分别放入两个位图中，如果两个位图的标记均为1，说明都存在，就是二者的交集。

void test_bitset1()
{int a1[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };int a2[] = { 5,3,5,99,6,99,33,66 };bit::bitset<100> bs1;bit::bitset<100> bs2;for (auto e : a1)bs1.set(e);for (auto e : a2)bs2.set(e);for (size_t i = 0; i < 100; i++){if (bs1.test(i) && bs2.test(i))cout << i << endl;}
}

二，布隆过滤器

有⼀些场景下⾯，有⼤量数据需要判断是否存在，⽽这些数据不是整形，那么位图就不能使⽤了，使⽤红⿊树/哈希表等内存空间可能不够。这些场景就需要布隆过滤器来解决。

1. 布隆过滤器的概念

布隆过滤器是⼀种可以⽤来告诉你"某样东西⼀定不存在或者可能存在"的数据结构，它是⽤多个哈希函数，将⼀个数据映射到位图结构中。

布隆过滤器的思路就是把key先映射转成哈希整型值，再映射⼀个位，如果只映射⼀个位的话，冲突率会⽐较多，所以可以通过多个哈希函数映射多个位，降低冲突率。

布隆过滤器这⾥跟哈希表不⼀样，它⽆法解决哈希冲突的，因为他压根就不存储这个值，只标记映射的位。它的思路是尽可能降低哈希冲突。判断⼀个值key在是不准确的，判断⼀个值key不在是准确的。

2. 布隆过滤器的实现

说明：我们这里用的bitset是我们上文自己实现的bitset，不是库里的。

#include "BitSet.h"
#include <string>struct HashFuncBKDR
{size_t operator()(const std::string& s){size_t hash = 0;for (auto ch : s){hash *= 31;hash += ch;}return hash;}
};struct HashFuncAP
{ size_t operator()(const std::string& s){size_t hash = 0;for (size_t i = 0; i < s.size(); i++){if ((i & 1) == 0) // 偶数位字符hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));else              // 奇数位字符hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));}return hash;}
};struct HashFuncDJB
{size_t operator()(const std::string& s){size_t hash = 5381;for (auto ch : s)hash = hash * 33 ^ ch;return hash;}
};//要用多个哈希函数多映射几个位，以便降低哈希冲突
template <size_t N,size_t X = 5,class K = string,class Hash1 = HashFuncBKDR,class Hash2 = HashFuncAP,class Hash3 = HashFuncDJB>
class BloomFilter
{
public:void Set(const K& key){size_t hash1 = Hash1()(key) % M;size_t hash2 = Hash2()(key) % M;size_t hash3 = Hash3()(key) % M;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}//如果其中一个位为0，就确定不在，如果都为1，那就在(存在误判)bool Test(const K& key){size_t hash1 = Hash1()(key) % M;if (!_bs.test(hash1))return false;size_t hash2 = Hash2()(key) % M;if (!_bs.test(hash2))return false;size_t hash3 = Hash3()(key) % M;if (!_bs.test(hash3))return false;return true;}
private:static const size_t M = N * X; //布隆过滤器的bit长度bit::bitset<M> _bs;
};//测试代码
void TestBloomFilter1()
{BloomFilter<10> bf;bf.Set("猪八戒");bf.Set("孙悟空");bf.Set("唐僧");cout << bf.Test("猪八戒") << endl;cout << bf.Test("孙悟空") << endl;cout << bf.Test("唐僧") << endl;cout << bf.Test("沙僧") << endl;cout << bf.Test("猪八戒1") << endl;cout << bf.Test("猪戒八") << endl;
}

3. 布隆过滤器删除问题

布隆过滤器默认是不⽀持删除的，因为⽐如"猪⼋戒“和”孙悟空“都映射在布隆过滤器中，他们映射的位有⼀个位是共同映射的(冲突的)，如果我们把孙悟空删掉，那么再去查找“猪⼋戒”会查找不到，因为那么“猪⼋戒”间接被删掉了。

4. 布隆过滤器的优缺点

优点：增删查改快，节省空间
缺点：只适⽤于整形