面试的时候可能会考到这种大数据处理的问题，如果不记得布隆过滤器是干嘛的，那就G喽！

本文参考：https://blog.csdn.net/weixin_58450087/article/details/123512052 编写

1. 什么是布隆过滤器？

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。它通过多个哈希函数将一个数据映射到位图的结构中（也就是一个数据映射位图的多个位置，这样就可以减少冲突的概率）。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

1.1. 引入

在认识布隆过滤器之前，我们先要认识一下哈希和位图的思想。

  • 哈希：通过哈希函数将value映射到数组中的某个key值下标的位置进行存储，方便查询；但对于海量数据来说占用空间大。
  • 位图：通过比特0和1来代表某一位的状态，极致节省空间；但无法处理哈希冲突问题。

布隆过滤器就是这两个思想的结合，可以帮助我们处理海量数据！

1.2. 思想

在哈希中，我们一般只使用一个哈希函数来进行value和key的映射，哈希可以通过拉链法或者线性探测法来解决哈希冲突问题。

但在布隆过滤器中，因为需要使用位图来做底层的数据结构，此时一个哈希函数就不够了，我们需要多个哈希函数，同时针对一个value进行计算，并将计算出来的多个结果位都置1，以此来减少冲突的概率，同时节省空间。

img

比如我有字符串A、B、C和三个哈希函数

  • A计算出来是10、29、39；
  • B计算出来是29、30、54；
  • C计算出来是30、34、44；

那么就需要将位图中对应的比特置1，当查询B字符串的时候，判断29、30、54位是否为1，有一个不为1则可以确定B不在过滤器中，全为1的时候可以确定B可能在布隆过滤器中。

1.2.1. “可能在”问题

为什么布隆过滤器只能判断出是可能在呢？看看下面的情况：

  • A计算出来1、2、3；
  • B计算出来4、5、6；

将A和B放入布隆过滤器，假设来了一个C字符串，计算出来2、3、6。这时候问题就出现了，C字符串并不在布隆过滤器中，但它计算出来的对应位都被A和B置为1了，此时我们就只能得出一个C可能在布隆过滤器中的结论，没有办法确定C到底在不在。

如果C计算出来是2、6、9，可以确定C绝对不在布隆过滤器中！因为第9位并没有被置为1。

这也是布隆过滤器的得名所在，它只是一个过滤器！并非100%能确定结果的！布隆过滤器只可以确定绝对不在和可能在。

1.2.2. 无法删除元素

因为布隆过滤器是用位图记录1和0的，如果我们将一个元素的哈希函数对应的值全都从1置0来删除的话，可能会影响到其他元素。

比如A是1、2、6，B是5、6、8，删除A的时候将1、2、6置0，这就影响了B（因为B也需要第6位来判断他是否在）

解决方法是采用计数方式来代替删除：位图的每一位进行一定扩展，比如扩展到3个bit来表示，这样就有了一个最大值为7的计数器，遇到一位映射就加一，删除就减一。

但这会引出两个问题：

  1. 位图的大小会成倍增加，可能会导致布隆过滤器的内存优势削弱；
  2. 如果计数器溢出了，会出现计数回绕问题；

计数回绕问题：当实际出现次数超过计数器位数后，会导致溢出回归到初始值，无法确定计数器是否正确。比如上文说的用3个bit来计数，假设这一位的出现次数已经是8了，得到的二进制结果是1000，此时低三位变成了全0，下一次判断的时候会发现这一位压根没有值，造成了错误判断。

所以实际场景中，我们又需要判断到底用几位来做这个计数器，以达到一定的平衡性。不过鉴于布隆过滤器的使用场景大多都是个过滤，避免删除元素反而成了更好的措施。

1.2.3. 如何精确确认？

前文提到了，布隆过滤器无法100%确认某个元素一定存在。那如果某一个场景一定需要100%确认，咋办？

举个实际的例子，假设一个游戏，用户注册的时候给自己起个玩家昵称，此时游戏需要保证玩家昵称不能重复，这时候可以怎么做？

  • 玩家键入一个名字后，客户端发起API请求，向数据服务器申请检查该名字是否已经被使用。

这是一个很简单的数据库查询（暂时不考虑数据库缓存的问题），但如果一个游戏刚刚开服或者做活动，大量新玩家涌入，一个玩家每输入一个名字的时候就需要发送一个API请求，数据库服务器还能接受的了这么海量的查询请求吗？

  • 在查询数据库之前设立一个布隆过滤器，将全服玩家昵称映射进去。
  • 当新玩家注册的时候，访问布隆过滤器，判断玩家昵称是否存在；
  • 如果布隆过滤器判断不存在（百分百可靠），API直接返回结果，允许玩家用该昵称注册；
  • 如果布隆过滤器判断存在，则回数据库查询到底是否存在，如果存在则要求玩家改昵称，如果不存在（误判）则允许玩家用该昵称注册。

这时候，布隆过滤器的“过滤”功能就很明显的体现了。而且因为查询的时候都是读操作，这时候就可以用多线程并发的读写锁来对布隆过滤器进行加锁，一定程度上提高查询的并发效率。

当然，玩家昵称注册的这个功能还有其他的解决办法，比如拳头的瓦洛兰特和暴雪的游戏，玩家昵称后还会带有一个#以及四位数字标识，比如我是慕雪#1234。可以让这四位数字标识由服务端生成，来避免两个玩家完全重名。除非同一个名字的四位标识都用完了（0000到9999），才提示玩家该昵称不可用。这样也一定程度上进行了过滤，减少了对数据库的查询次数。

1.3. 优缺点

优点

  • 增加和查询的时间复杂度都为O(K)，K为哈希函数的个数
  • 多个哈希函数之间没有关系，方便进行并行计算（多线程）
  • 布隆过滤器并不存储元素本身，所以占用空间小，特别是海量数据处理时
  • 如果多个布隆过滤器使用的是相同的哈希函数，则可以进行并集\交集\差集的计算

缺点

  • 没有办法百分百确定value一定在，只能确定一定不在；
  • 无法从布隆过滤器中直接获得value；
  • 不能从布隆过滤器中删除元素（用计数方式删除会有计数回绕问题）

1.4. 布隆过滤器的位图长度选择

对于布隆过滤器来说，M（位图长度）和K（哈希函数个数）越多的时候，冲突的概率就越少。可以根据具体场景的需求，选用更大的M和K来解决冲突，让冲突的概率变小，具体需要多小的冲突概率，是由业务需要来确定的。

布隆过滤器的哈希函数与位图长度的选择关系公式如下

1
2
3
4
5
6
7
m = - n * ln(p) / (ln(2)^2);
k = m/n * ln(2);

// k 为哈希函数个数
// m 为布隆过滤器长度
// n 为插入的元素个数
// p 为可接受该容器的误报率（0-1）

img

PS：GPT说最终位图的长度还需要K*M，感觉是在瞎说，查了不少资料，应该是不需要进行这一步的。

2. 代码

2.1. 位图

布隆过滤器的代码基于位图。位图就不单开博客记录了，本质就是一个整形数组，把每一个比特当作位图中的每一位进行处理，对应按位与和按位或操作就OK了，不是很难理解。

位图的底层可以用vector，也可以用原生的new/delete的数组来处理。用原生的可以节省一定的空间消耗。

位图的优点是可以节省空间，查找和设置的耗时极低，都是O(1)的时间复杂度。缺点是没有办法处理冲突情况，且只支持整数数据。

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
class BitMaps
{
private:
	size_t _bitCount; // 位图中比特的个数
	//std::vector<uint32_t> _bitMap; // 使用int32_t来确保长度
	uint32_t* _bitMap; // 用动态内存管理来节省一定空间，vector会有额外内存消耗
	static const uint8_t _weight = 32; // 用的int32，设置为32方便后序修改

	size_t GetIndex(size_t bit) {
		return bit / _weight;
	}
	size_t GetOffset(size_t bit) {
		return bit % _weight;
	}
public:
	// 需要多少比特的空间
	BitMaps(size_t bitCount):_bitCount(bitCount),_bitMap(nullptr) {
		// 需要多少个int来存放空间
		size_t arraySize = bitCount / _weight + 1;
		// 用原生数组一定程度上节省空间
		// _bitMap.resize(arraySize);
		_bitMap = new uint32_t[arraySize];
		// 遍历初始化为全0
		for (size_t i = 0; i < arraySize; i++)
		{
			_bitMap[i] = 0;
		}
	}

	// 使用动态内存管理，需要delete
	~BitMaps()
	{
		if (_bitMap != nullptr) {
			delete[] _bitMap;
		}
	}

	// 将第几位的比特设置为1
	void Set(size_t bit)
	{
		// 超出范围的时候报错
		assert(bit <= _bitCount); 
		
		// 计算下标位置
		size_t index = GetIndex(bit);
		// 计算是这个下标的第几位
		size_t offset = GetOffset(bit); // 0 到 31
		// 设置进位图，按位或（有1为1）
		_bitMap[index] |= (1 << offset);
	}
	// 将对应位设置为0
	void Reset(size_t bit)
	{
		// 超出范围的时候报错
		assert(bit <= _bitCount);

		// 计算下标位置
		size_t index = GetIndex(bit);
		// 计算是这个下标的第几位
		size_t offset = GetOffset(bit); // 0 到 31
		// 设置进位图，按位与，此时对应位为0，与之后肯定是0
		_bitMap[index] &= ~(1 << offset);
	}

	// 判断第几位是否存在
	bool Test(size_t bit)
	{
		// 超出范围，肯定不存在
		if (bit > _bitCount) {
			return false;
		}
		// 计算下标位置
		size_t index = GetIndex(bit);
		// 计算是这个下标的第几位
		size_t offset = GetOffset(bit); // 0 到 31
		// 判断是否为1，按位与
		uint32_t num = (1 << offset);
		// 与位图中的值按位与，只有两个都是1，才是1
		num &= _bitMap[index];
		// 为0代表不存在
		return num != 0; 
	}
};

2.2. 布隆过滤器

2.2.1. 基本框架

布隆过滤器需要指定哈希函数，有两种实现方式

  • 通过模板参数来指定哈希函数（但是只能固定个数）
  • 通过函数来添加哈希函数（内部可以用一个function的vector来遍历调用）

这里为了实现方便且以思路实现为主，采用第一种方式来处理。

2.2.2. 常用字符串哈希函数

下面是三个比较常用的字符串哈希函数，由它们帮我们计算一个子串对应的三个位图下标。

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
struct BKDRHash
{
	size_t operator()(const std::string& str)
	{
		register size_t hash = 0;
		for (size_t i = 0; i < str.size(); ++i)
		{
			hash = hash * 131 + str[i];
		}

		return hash;
	}
};

struct SDBHash
{
	size_t operator()(const std::string& str)
	{
		register size_t hash = 0;
		for (size_t i = 0; i < str.size(); ++i)
		{
			hash = 65599 * hash + str[i];
		}
		return hash;
	}
};

struct RSHash
{
	size_t operator()(const std::string& str)
	{
		register size_t hash = 0;
		size_t magic = 63689;
		for (size_t i = 0; i < str.size(); ++i)
		{
			hash = hash * magic + str[i];
			magic *= 378551;
		}
		return hash;
	}
};

2.2.3. 类构造

布隆过滤器直接复用位图的实现即可，模板参数用缺省值来指定为字符串。如果需要存放其他类型的成员，不仅需要修改T参数，还需要修改三个哈希函数来适配该参数。

这里为了方便，直接用乘6来替代布隆过滤器的长度计算公式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class T= std::string, class Hash1 = BKDRHash, class Hash2 = SDBHash, class Hash3 = RSHash>
class BloomFilter
{
public:
	// 长度计算公式 m = - n * ln(p) / (ln(2)^2) 
	// 为了实现方便，暂时用6来替代
	BloomFilter(size_t size)
		:_bs(6 * size)
		, _bitSize(6 * size)
	{}
private:
	BitMaps _bs; // 位图
	size_t _bitSize;// 能够映射bit个数 
};

2.2.4. 设置元素

设置元素的时候，通过三个哈希函数计算不同的下标值，设置进位图里面就行了。注意这里哈希函数的返回结果需要模一下位图的长度，避免越界。

1
2
3
4
5
6
7
8
9
10
11
// 设置
void Set(const T& t)
{
	size_t hash1 = Hash1()(t) % _bitSize;
	size_t hash2 = Hash2()(t) % _bitSize;
	size_t hash3 = Hash3()(t) % _bitSize;

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

2.2.5. 查找元素

同样是调用位图的test函数，只有三个都在的时候，才是元素可能在布隆过滤器中。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 判断
bool Test(const T& t)
{
	size_t hash1 = Hash1()(t) % _bitSize;
	size_t hash2 = Hash2()(t) % _bitSize;
	size_t hash3 = Hash3()(t) % _bitSize;
	
	bool ret1 = _bs.Test(hash1);
	bool ret2 = _bs.Test(hash2);
	bool ret2 = _bs.Test(hash3);
	// 只有三个都为true才是可能在
	return ret1 && ret2 && ret3;
}

2.2.6. 删除元素

前文提到了，布隆过滤器的删除可以用计数器的方式来实现，但是会有计数回绕问题。所以这里布隆过滤器的实现先不管删除啦。

2.3. 测试布隆过滤器

测试一下set和test有么有什么问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void TestBloomFilter()
{
	BloomFilter<> bf(100);

	bf.Set("test1");
	bf.Set("test2");
	bf.Set("test3");
	bf.Set("test4");

	std::cout << bf.Test("test1") << std::endl;
	std::cout << bf.Test("test2") << std::endl;
	std::cout << bf.Test("test3") << std::endl;
	std::cout << bf.Test("test4") << std::endl;


	std::cout << bf.Test("test6") << std::endl;
	std::cout << bf.Test("tsdfaba") << std::endl;
}

输出如下，符合预期

1
2
3
4
5
6
1
1
1
1
0
0

这里还可以构造一部分海量数据来测试这个布隆过滤器的准确度如何。但是构造海量的字符串用例感觉很是麻烦，暂时不弄了。

3. 实际场景问题

3.1. 给一个巨大的logFile，内部存放IP地址，设计算法找到TOPK的IP或出现频率最多的IP？

先创建1000个小文件，然后通过一个哈希函数i = hash(IP) % 1000计算出IP地址存放的位置（这样相同的IP地址会存入一个文件），随后依次读取这些小文件，使用一个uordered_map<string,long long>来计算每一个IP地址出现的次数。

因为相同的IP地址肯定在同一个小文件内，所以每次unordered_map得到的IP计数肯定是准确的。

这里注意内存的消耗，如果1000个小文件后内存还是会爆，则将文件数量进一步扩大到10000个，以此类推。

再用一个小根堆来存放整体TopK的IP地址：因为我们需要出现频率最高的IP地址，所以用小堆可以将堆内出现频率最低的放在堆顶。这样只要得到一个比堆顶出现次数更多的IP地址，就弹出堆顶将其插入。

  • 使用哈希函数将logFile中的IP地址映射到不同的小文件中（一行一个IP，直接在文件尾部写入即可）；
  • 遍历小文件，使用uordered_map<string,long long>来计算IP地址出现频次；
  • 每次遍历一个小文件后，遍历unordered_map，将IP地址出现频次高于堆顶元素的IP插入小根堆（弹出堆顶后插入）；
  • 遍历完毕一个小文件，清空unordered_map（避免爆内存）；

遍历完毕所有小文件后，得到的就是TopK出现频率最多的IP地址。此时堆顶元素就是出现频率从高到低在第K个的IP地址，堆内元素是出现频次在前K个的IP地址。

3.2. 给出两个50亿行的文件，一行是一个128字节的字符串，如何找到这两个文件中同时出现过的字符串？

面大厂的时候遇到了这个问题，当时忘记布隆过滤器了，没有答出来，哭死。

3.2.1. 布隆过滤器

使用一个布隆过滤器来实现：

  • 创建一个布隆过滤器
  • 按行读取文件A，计算字符串哈希，映射进布隆过滤器中
  • 按行读取文件B，计算字符处哈希，判断是否在布隆过滤器中，在则存放至交集内。

注意，因为布隆过滤器不能保证100%的准确性，所以需要根据准确度的要求扩大布隆过滤器的位图长度或增加哈希函数。

这里可以来计算一下这样做的内存消耗。用下面的python函数来计算位图的长度

1
2
3
4
5
6
7
8
9
10
11
import math

n = 50 * 10**8  # 预期的元素数量
p = 0.005       # 期望的误判率
k = 4           # 哈希函数数量

## math.log默认的底就是e
m = -n * math.log(p) / (math.log(2)**2)  # 计算位图长度

print("位图长度m：", m)
print("占用内存GB：",m/(8*1024*1024*1024))

输出结果如下

1
2
位图长度m： 55138767091.28201
占用内存GB： 6.418997316071998

还可以用这个网站来在线计算，hur.st/bloomfilter。这个网站使用的公式和上文不同。

由图可知，当n为50亿的，哈希函数4个，误报率0.005（千分之5）的时候，需要7.5GB的空间来存放布隆过滤器。

image-20240330111317153

虽然6.41GB和7.53GB看上去还是一个很大的内存占用，但是对于服务器动则128GB起步的物理内存大小而言，这已经是相对来说可以接受的占用了。哪怕如今一台16GB内存的家用电脑，理论上也能完成这样的工作。

如果直接将50亿个128字节的字符串加载到内存里面，要多少空间呢？

1
2
(5 * 10^9 * 128) / (8*1024*1024*1024)
结果是 74.506GB

image-20240330103449933

74.5GB和7.5GB是将近10倍的内存占用差距，更别提这里只是计算了加载字符串的内存占用，还没有计算如果使用哈希或者红黑树来保存这些字符串的额外内存占用呢，如果算上至少奔着80GB+去了。

3.2.2. 精确算法

精确算法就还是需要使用哈希切分加set对比的思路了，设定一万个或者十万个小文件，遍历原始文件，通过哈希i = hash(IP) % 小文件数量映射字符串到第i个小文件中，对A和B都做如此操作，得到A1到Ai个和B1到Bi个小文件。

因为求的是字符串交集，使用相同哈希函数的情况下，A和B的相同字符串肯定会在同一个i的小文件中，此时就可以通过对A1小文件建立一个unordered_set，遍历B1小文件判断是否在set中，再处理A2和B2，以此类推，得到最终的交集。

注意，如果题目给出了内存限制，我们还需要进一步计算切割出来的小文件的大小是否大于了内存的限制。如果大于了，则采用上述思路对这个小文件再进行一次切分，直到切出来的小文件可以完整的在内存限制之内即可。

3.3. 给定10亿个int整数，如何设计算法找到只出现了一次的数（不重复的整数）

10亿个整数肯定没有办法都load到内存里面，这里需要用到位图来实现。

方法一：扩展位图，使用2个比特来记录一个数，00代表没出现，01代表出现一次，10代表出现2次及以上。最终位图操作完毕后，重新遍历位图即可得到结果。

方法二：用两个位图同时操作，数字第一次出现的时候，在第一个位图置1，第二次出现的时候，在第二个位图置1。最终只有一个位图中置1的数就是只出现了一次的数。思路同上。

这两种方法的消耗空间 (2*4*(10^9))/(8*1024*1024*1024) ≈ 0.931GB，足够在内存中处理了。

1个文件有10亿个int，限定1G内存，设计算法找到出现次数不超过2次的所有整数。这个问题也能用上述方法来处理。

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

方案一： 将文件1的整数映射到一个位图中，然后读取文件2中的数据，判断是否在位图中，在就是交集。（位图的长度取决于这些整数的数据范围）

方案二： 将文件1的整数映射到一个位图中， 将文件2的整数映射到另一个位图中，然后将两个位图进行按位与（遍历按位与），与之后位图中为1的位就是两个文件的交集。

3.5. 已知某个文件内包含一些电话号码，每个号码为 8 位数字，统计不同号码的个数

每个号码八位数，不考虑电话号码的实际情况，8位最多99,999,999，一共有10^8种情况。也就是需要10^8位bit，大概12.5M内存即可。

申请一个数组，遍历所有号码，将号码对应的bit置为1，最后统计bit位1的数量即为不同的号码数。

3.6. 5亿个int整数找它们的中位数

参考：https://www.nowcoder.com/discuss/384700130958602240

解法一：当内存不足以存放5亿个int整数时，我们依然使用分而治之的方法，但hash映射分成小文件的时候需要注意，我们要保证把数据分散到不同文件中时仍然保持着顺序，即按数值大小进行分流，这样才能找到正确的中位数。

  • 我们遍历这5亿个int整数时，考虑其二进制的最高位，按照最高位（符号位，0表示正数，1表示负数）进行二分，即最高位为1存入文件a，最高位为0存入文件b，这样文件a中的数是一定比文件b中的数小。
  • 统计文件a和文件b中的整数个数，如果文件a和文件b中的整数个数相同，那么中位数则是文件a中的最小值和文件b中的最大值的平均值。如果文件a中的整数个数小于文件b，那么中位数肯定在文件b中，反之亦然。
  • 如果文件a或文件b中的整数还是无法直接读取进内存中，那么继续使用上个步骤的方法进行分流，并判断中位数所处的位置，直到中位数所在的那部分数据大小可以直接放到内存中，然后对这部分排序，计算出中位数的值。

解法二：用堆来解决这个问题，前提是整数能被全部加载到内存中。

思路可以参考leetcode题目 295. 数据流的中位数，为了方便后序归档和复习，对这到题单独开一篇题解。思路还是K神的【点我看思路】。

3.7. 海量数据进行排序

这个是涉及到外排序相关的知识了，也算大数据处理，干脆一起记录在这里。

1
2
https://blog.csdn.net/qq_43915356/article/details/106877167
https://blog.csdn.net/ailunlee/article/details/84548950

问：假设给你8GB数据，内存只有2GB，如何排序？

首先我们需要将8GB分为4个2GB的小文件，依次读取每个小文件对其进行排序并存入一个排序好的文件中。得到其中一个有序子串。

随后，同时读取两个2GB的文件（每一次都只从两个文件中读取一个内容），对比，将小的那个输出到目标文件中。直到遍历完毕两个2GB的文件，即得到了一个4GB的有序子串。

对两个有序的4GB子串做同样的处理，输出成最终的8GB文件。

N个有序子串的归并叫做N路归并。

但是这里会有一个磁盘IO的问题，我们两两归并的时候，会涉及到从两个文件中读取一次，再输出到最终文件中的一次。归并的次数越多，IO的次数也就越多，速度也就越慢。

所以可以适当的增加归并文件的数量，比如同时读取三个2GB的文件，对三个数进行排序，输出到目标文件中。但是这里需要注意有序性的问题。比如文件A和B中的第一个记录小于C的记录，此时会以A0\B0\C0输出到目标文件中，但有可能会出现A1和B1还是小于C0的情况，这种就比较麻烦了（俺没想出好的解决办法）。

4. The end

布隆过滤器和位图，以及哈希分而治之的思想在大数据梳理中非常有用，一定要记住！