[C++] 布隆过滤器的模拟实现

定义

• 将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1；
• 布隆过滤器如果说某个元素不存在时，该元素一定不存在；如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判；
• 布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

目的

• 像string这样的类映射到位图上时，容易产生冲突，但是这种冲突我们又没办法彻底解决，只能减少冲突；所以，使用布隆过滤器减少冲突，可能会增加误判，但是误判的概率降低了。

布隆过滤器的优点

1. 增加和查询元素的时间复杂度为：O(K)， (K为哈希函数的个数，一般比较小)，与数据量大小无关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

布隆过滤器的缺陷

1. 有误判率，不能准确判断元素是否在集合中
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素
4. 如果采用计数方式删除，可能会存在==计数回绕问题 ==

布隆过滤器的模拟实现

1）实现基本框架

• 底层是位图，使用BKDRHash、SDBMHash、RSHash这三个哈希函数

template <size_t N, class K = string, 
	class Hash_1 = BKDRHash, 
	class Hash_2 = SDBMHash,
	class Hash_3 = RSHash>
class BloomFilter{
	private:
		BitSet<N> _bs;
	};
1
2
3
4
5
6
7
8

2）实现基本操作

Set—比特位置1

void Set(const K& x){
			/*	Hash_1 h1;
			h1(x);*/
			size_t i1 = Hash_1()(x) % N;
			size_t i2 = Hash_2()(x) % N;
			size_t i3 = Hash_3()(x) % N;
			cout << i1 << " " << i2 << " " << i3 << endl;
			_bs.set(i1);
			_bs.set(i2);
			_bs.set(i3);
		}
1
2
3
4
5
6
7
8
9
10
11

Test—测试某个数据是否在位图中

• 如果位图上有一个位上的值不为1，则不存在；全部为1，可能存在(误判)

bool Test(const K& key){
			size_t i1 = Hash_1()(key) % N;
			size_t i2 = Hash_2()(key) % N;
			size_t i3 = Hash_3()(key) % N;
			if (!_bs.test(i1))
				return false;
			if (!_bs.test(i2))
				return false;
			if (!_bs.test(i3))
				return false;
			return true;
		}
1
2
3
4
5
6
7
8
9
10
11
12