位图和哈希的综合应用 —— 布隆过滤器

前言： 布隆过滤器其实是补充了位图的一个小缺陷。位图的话只可以处理整数，但是大多数情况下，我们不仅要处理整数，还要处理字符串或者是自定义类型的数据。那么还是想利用位图，因为位图比较香嘛。那怎么办？布隆过滤器。

---

1. 布隆过滤器的概念

位图是好理解的，无非就是 一种映射，但是 布隆过滤器 其实就是 结合位图 + 哈希 的综合应用。它是将 字符串或是自定义对象，转换成 可哈希对象，可哈希的对象就是 转换为 无符号整数，然后再映射到 位图中。

那么有个问题：有没有一种可能，一个无符号整数对应了 多个字符串，有可能的。不难理解，字符串相当的庞大，数字就那几个。必然 会发生 一个无符号整数 对应多个字符串的情况，这就是误判。那么该如何处理这种情况？

如果映射到一个位置，那么发生误判的情况必然很多，但是 我可不可以 映射到多个位置？
什么意思？就是字符串 转为 可哈希对象，有 很多算法，我们 可以 使得一个字符串转换为多个整数，然后映射到位图中，检查一个字符串是否在 位图中，要检查多个位置，那么就会大概率的减少误判。但是你说 完全能避免误判 ，那是不太可能的。

画图来理解一下吧：

• 假如我采用的是-》用一个哈希转换函数，也就是映射到一个比特位：
  
  发生误判就是上述情况，苹果和"sdsdas"映射到了同一个位置，这种情况下，即便你只set了"苹果"，但是你test (“sdsdas”)，发现"sdsdas" 也在，其实它不在。很好理解。

• 假如我用三个哈希转换函数，来转换这俩个字符串，那么每个字符串就会映射到三个位置：

我检查"sdsdas" 在不在，我需要查三个位置，是不是误判的情况就减少了呀。

但是存不存在 误判？依旧存在，比如:

看到了吧，如果 “李四” 并没有存入位图，但是 位图中 有"苹果"，“sdsdas”，它们会把"李四"映射的三个位置给分别占用了，导致 误判。

---

2. 布隆过滤器的实现

有了以上理解，我们就来自己实现一下，布隆过滤器，其实它的原理也不难哈。

#include 
#include 

using namespace std;

struct BKDRHash
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};

struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long 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 DJBHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};

template<size_t N,
	size_t X = 8,
	class K = string,
	class HashFunc1 = BKDRHash,
	class HashFunc2 = APHash,
	class HashFunc3 = DJBHash>
	class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		size_t index2 = HashFunc2()(key) % len;
		size_t index3 = HashFunc3()(key) % len;

		_bs.set(index1);
		_bs.set(index2);
		_bs.set(index3);
	}

	bool Test(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		if (_bs.test(index1) == false)
			return false;

		size_t index2 = HashFunc2()(key) % len;
		if (_bs.test(index2) == false)
			return false;

		size_t index3 = HashFunc3()(key) % len;

		if (_bs.test(index3) == false)
			return false;

		return true;  // 存在误判的
	}
	
private:
	bitset<X* N> _bs;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

2.1 模板参数以及其底层结构

#include 
#include 

using namespace std;
template<size_t N,
	size_t X = 8,
	class K = string,
	class HashFunc1 = BKDRHash,
	class HashFunc2 = APHash,
	class HashFunc3 = DJBHash>
	class BloomFilter
	{
	private:
	    bitset<X* N> _bs;	
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

首先我们要确定一件事: 我们要开辟多大空间的位图，空间的大小开辟，也会影响 布隆过滤器的误判率。

这个其实大佬也给出了答案：

我们的哈希函数个数取三个(k)，插入多少个元素是由我们自己定的(n)，那么开多大的位图(m)，就是我们要 算的，m = (k * n)/ln2 ; 所以 m = n * 4.2；位图开的越大，发生误判的概率越小，但是 位图空间开的太大，会导致 空间浪费；我们模拟的时候，就开辟 X* N个比特位的位图，但是 X = 8 ，8>4.2， 也是没问题的，这样误判概率更小。

也就是：

 bitset<X* N> _bs;
1

接下来，来看一下，模板参数：

template<size_t N,
	size_t X = 8,
	class K = string,
	class HashFunc1 = BKDRHash,
	class HashFunc2 = APHash,
	class HashFunc3 = DJBHash>
1
2
3
4
5
6

N是我要插入元素的个数；X默认給 8；K是要进行哈希变化对象的类型默认给 string就行；
然后就是三个哈希转换函数，这三个哈希函数，感兴趣的可以去研究一下，上面我已经给出代码，就是将 字符串转换成无符号整数。

---

2.2 Set()的实现 -》(插入)

我们要把一个字符串用哈希函数转换为三个无符号整数，然后映射到位图中：

    void Set(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		size_t index2 = HashFunc2()(key) % len;
		size_t index3 = HashFunc3()(key) % len;

		_bs.set(index1);
		_bs.set(index2);
		_bs.set(index3);
	}
1
2
3
4
5
6
7
8
9
10
11

2.3 Test() -》(检验字符串是否在位图中)

做检验的话，我们要查 字符串 在 位图映射的三个位置。

• 只要一个位置为0，那么就表示字符串一定没有在位图中
• 三个位置都是1，表示字符串可能存在(存在误判的)

    bool Test(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		if (_bs.test(index1) == false)
			return false;

		size_t index2 = HashFunc2()(key) % len;
		if (_bs.test(index2) == false)
			return false;

		size_t index3 = HashFunc3()(key) % len;

		if (_bs.test(index3) == false)
			return false;

		return true;  // 存在误判的
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.4 布隆过滤器的删除

咳咳。布隆过滤器可以支持删除嘛？大家想一想这个问题。

明显不支持，因为一个字符串映射到位图中的多个位置，如果要删除这个字符串，那么意味着要删除掉 它在位图中映射的多个位置，但是它的位置有可能是和其他字符串共用的，删除掉那几个映射，会影响 其它的字符串。

3. 布隆过滤器的应用

3.1 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

我们先给出近似的算法：

近似算法的意思就是 误判概率大一些，但基本能够找出交集、

query是字符串嘛，所以需要用到布隆过滤器，我们可以将文件一中的query全部都映射到一个布隆过滤器(a)中；然后 读取文件二的query，与布隆过滤器(a)中的数据做对比，如果文件二的query在布隆过滤器(a)中找到了，那么 就存在布隆过滤器(b)中。那么最终得到的交集就是布隆过滤器(b)。

精确算法那么就需要用到哈希切分:

把这俩大文件分别搞成多个小文件，利用哈希切分，注意俩个文件必须用的是 同一个哈希函数来进行哈希切分。然后 再在小文件中就可以找到交集了。

图解如上，那么求交集的话，就比较轻松了，因为切分成小文件，那么 内存占的是 小的。

再在小文件中 分别求交集就可以了。

这样确实是更加精确了，文件一和文件二 中的query 分别进入了编号相同的 Ai和Bi中，只要求 A0 和 B0 ，A1和B1 …… Ai和Bi的交集，最终就能够 找到所有的交集。

3.2 如何扩展布隆过滤器使得它支持删除元素的操作

上面不是讲过，布隆过滤器是不支持删除的操作嘛，因为删除操作会影响到其他的元素。

但是 也是可以 办法来支持这布隆过滤器删除操作的。

那就是 利用引用计数这种操作，

比如：注意不再是一个比特位来标识了，因为一个比特位只能是 0或1 ，它无非计数。所有我举例呢，用的是四个比特位，用四个比特位 来标识 是否存在。

注意这里不要混淆了，上面说过用三个哈希函数去映射到 位图中的不同三个比特位上。现在的意思是 三个哈希函数 去映射到 位图上的 不同 的 三个位置上，每个位置是 四个比特位。

这四个比特位是我自己定的，反正只要是映射到这个位置上，那么这个位置上的值就会 +1

说的有点不好理解，我们来看图吧：

那么我再映射一个字符串"sdasdas":

那么重复的映射的位置，它们的值 +1 ，对吧。这就很秀了，我现在删除字符串还会影响其他的字符串嘛？当然不会 ，删除就是 将字符串映射的位置的值 -1。

对吧？假如我要删除 “苹果” 字符串：

嗯，这就是布隆过滤器的删除。

---