[C++数据结构](23)哈希：位图，布隆过滤器，哈希切割

哈希特殊应用

位图(BitMap)

题目：

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断这个数是否在这40亿个数中。

思路：

把这40亿个数放进 unordered_set 里？显然不现实，因为光是40亿个整型就需要约15GB空间，更别提哈希表的其他资源消耗，内存空间不够。

注意到我们需要找的是一个数存不存在，记录一个数是否存在只需要一个bit位，这样的话，一个bit位一个地址，采用直接定址法只需要开 $2^{32}$ (整型能表示的数据个数) 个bit，也就是 512MB 空间

代码实现：

注意一些位运算的技巧

template<size_t N> // 非类型模板参数，表示要开的位数
class bit_set
{
public:
	bit_set()
	{
		_bits.resize(N / 8 + 1, 0); // N/8会省略小数，导致开的空间不够，所以+1多开一个字节
	}

	// x位置设为1
	void set(size_t x)
	{
		// 计算x位置在第几个字节
		size_t i = x / 8;
		// 计算在这一字节的第几个bit位
		size_t j = x % 8;

		_bits[i] |= 1 << j;
	}

	// x位置设为0
	void reset(size_t x)
	{
		size_t i = x / 8;
		size_t j = x % 8;
		_bits[i] &= ~(1 << j);
	}

	// 判断x在不在
	bool test(size_t x)
	{
		size_t i = x / 8;
		size_t j = x % 8;
		return _bits[i] & (1 << j);
	}

private:
	vector<char> _bits;
};
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

---

其实库里面提供了位图容器

详情参考文档：bitset - C++ Reference (cplusplus.com)

---

位图应用

1. 从100亿个整数中，找到只出现一次的整数

重写一个位图，让两个bit表示一个状态，一共三种状态：出现0次、出现1次、出现多次。

这样这个位图需要开的空间是原来位图的2倍，也就是1GB

代码实现：

使用两个bitset实现，就不需要重写映射关系了

template<size_t N>
class two_bitset
{
public:
	//出现0次、1次、多次分别表示为：00、01、10
	void set(size_t x)
	{
		bool in1 = _bs1.test(x);
		bool in2 = _bs2.test(x);
		if (!in1 && !in2) // 如果还未出现
		{
			// 设为01
			_bs2.set(x);
		}
		else if (!in1 && in2) // 如果已经出现一次
		{
			// 设为10
			_bs1.set(x);
			_bs2.reset(x);
		}
		// 如果已经出现2次及以上，不动
	}

	bool isOnce(size_t x)
	{
		return !_bs1.test(x) && _bs2.test(x);
	}

private:
	bitset<N> _bs1;
	bitset<N> _bs2;
};
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

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

   分别建立两个位图，两个位图中都记为1的值就是交集

3. 1个文件有100亿个整数，我们有1G内存，从中找出出现次数不超过2次的所有整数。

   在第一题的基础上加一个状态，让 10 表示出现2次，11 表示出现3次即以上

位图优点：

节省空间，快

位图缺点：

只能针对整型。

布隆过滤器

位图只能针对整型，因为整型可以使用直接定址法，且不存在哈希冲突。如果将字符串转换成整型则可能出现哈希冲突，而位图中没有真正存入这个字符串，无法进行比对，所以不能解决哈希冲突的问题。

布隆过滤器则是对位图的一种改造，可以让一个 key 映射多个地址（使用多个哈希函数），降低哈希冲突的概率。不过它依然有一定的误判概率。在查找的时候，它只能告诉你这个值一定不在或可能在。

具体映射多少个地址，要看具体情况，映射的越多，哈希冲突的概率越小，但是占用的空间就越大。

如何选择合适的哈希函数个数呢，这里直接给出公式：
$$\begin{gathered} m=-\frac{n\ln p}{{\ln }^{2}2} \\ k=\frac{m}{n}\ln 2 \end{gathered}$$
$k$ 为哈希函数个数，$m$ 为布隆过滤器长度，$n$ 为插入元素的个数，$p$ 为误报率。

实现

三个哈希函数的版本：

template<class K, size_t M,
	class HashFunc1,
	class HashFunc2,
	class HashFunc3>
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t hash1 = HashFunc1()(key) % M;
		size_t hash2 = HashFunc2()(key) % M;
		size_t hash3 = HashFunc3()(key) % M;

		_bs.set(hash1);
		_bs.set(hash2);
		_bs.set(hash3);
	}

	bool Test(const K& key)
	{
		// 三个位只要有一个为0就是不存在
		size_t hash1 = HashFunc1()(key) % M;
		if (!_bs.test(hash1)) return false;
		size_t hash2 = HashFunc2()(key) % M;
		if (!_bs.test(hash2)) return false;
		size_t hash3 = HashFunc3()(key) % M;
		if (!_bs.test(hash3)) return false;
		// 都为1则表示可能存在
		return true;
	}

private:
	bitset<M> _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

布隆过滤器支持删除吗，如何删除？

• 可以支持，但是不能直接删，因为删除一个值可能影响其他值，如果两个值的三个映射有交集，那么删除一个另一个就也找不到了。
  • 解决方案：可以使用多个位图来表示一个地址被映射的次数，删除一个值的时候只要在相应的映射位置减1即可，不过这样还存在一个误判，如果删除操作之后这个值的三个映射位置的计数都没有减为0，那么这个值会被误判为存在。
• 布隆过滤器的一大优点就是节省空间，支持删除需要多开额外的空间，所以它一般不去实现删除操作。

---

布隆过滤器应用场景：

1. 注册的时候，快速判断一个昵称是否使用过。
   • 不在，是确定的，可以使用
   • 在，则再去数据库确认一遍
2. 黑名单
   • 不在，同行
   • 在，再去系统确认

哈希切割

问题：给一个超过100G的log文件，log中存着IP地址，如何找出出现次数最多的IP地址。

这是个 kv 模型，不可使用位图和布隆过滤器。

解决方案：创建100个文件，然后依次读取ip，算出 i = HashFunc(ip) % 100，把这个 ip 放到第 i 个文件里面。这样可以保证同样的 ip 进入同一个的文件，最后使用 unordered_map 对每个文件进行统计（统计完一个文件，clear，再统计下一个文件）。

缺陷：

• 某个小文件太大

  原因：

  • 某个ip相同的太多
  • 映射冲突到这个文件的ip太多

解决方案：

• 捕获内存不足的异常，说明内存不够
  • 针对这个小文件，换个哈希函数再次进行哈希切割，分成更细小的文件。

应用：给两个文件，分别有100亿个ip，我们只有1G内存，如何找两个文件的交集

解决：创建A0 A1 ··· A999，B0 B1 ··· B999，共2000个小文件，分别计算两个文件中的 i = HashFunc(ip) % 1000，分别放到Ai，Bi中，最后对每一对小文件求交集。