【C++】哈希应用：bitset和布隆过滤器_bitset切割

一、位图概念

一道面试题：
给定40亿个无序不重复的无符号整数。给一个无符号整数，如何快速判断一个数是否在这40亿个数中

1. 遍历，时间复杂度$O(N)$
2. 排序: $O(NlogN)$，利用二分查找: $logN$
3. 位图解决
   数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的

---

二、bitset的使用

bitset使用文档

1. 构造

bitset<32> b1;// 0
bitset<32> b2(-1);// 4294967295
bitset<32> b3("1010");// 10
cout << b1.to_ulong() << endl;// 转换成无符号长整型
cout << b2.to_ulong() << endl;
cout << b2 << endl;// 直接输出二进制表示
cout << b3.to_ulong() << endl;
cout << b3.to_string() << endl;// 转换成字符串
1
2
3
4
5
6
7
8

2. 访问

3. 操作

---

三、bitset的模拟实现

// 非类型模板参数
template<size_t N>
class bitset
{
public:
	bitset()
	{
		// 加一个字节避免 20 / 8 = 2访问20时越界
		//_bits.resize(N / 8+1, 0);// 1个字节8个比特位
		_bits.resize((N >> 3) + 1, 0);// 注意运算符优先级 
	}
	void set(size_t pos)
	{
		//size_t  i = pos / 8;
		size_t i = pos >> 3;// 在第i个char
		size_t j = pos % 8;// 第i个char的第j个比特
		_bits[i] |= (1 << j);
	}
	void reset(size_t pos)
	{
		size_t  i = pos >> 3;
		size_t j = pos % 8;

		_bits[i] &= (~(1 << j));
	}

	bool test(size_t pos)
	{
		size_t i = pos >> 3;
		size_t j = pos % 8;

		//return (_bits[i] >> j) & 1;
		return _bits[i] & (1 << j);
	}

private:
	std::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

---

四、布隆过滤器

1、提出

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？

用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？

1. 用哈希表存储用户记录
   缺点：浪费空间

2. 用位图存储用户记录
   缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理

3. 将哈希与位图结合，即布隆过滤器

2、概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在” ，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间

3、查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。

比如：在布隆过滤器中查找"Tencent"时，假设3个哈希函数计算的哈希值为：2、4、6，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实际该元素是不存在的。

4、删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

比如：删除"tencent"元素，如果直接将该元素所对应的二进制比特位置0， “baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储 空间的代价来增加删除操作。

缺陷：

1. 无法确认元素是否真正在布隆过滤器中
2. 存在计数回绕（删除时减少的计数被插入增加回来）

5、优缺点

• 优点
  1. 增加和查询元素的时间复杂度为$O(K)$, ($K$为哈希函数的个数，一般比较小)，与数据量大小无关
  2. 哈希函数相互之间没有关系，方便硬件并行运算
  3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
  4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有着很大的空间优势
  5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
  6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
• 缺陷
  1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
  2. 不能获取元素本身
  3. 一般情况下不能从布隆过滤器中删除元素
  4. 如果采用计数方式删除，可能会存在计数回绕问题

---

6. 模拟实现

#pragma once

#include <iostream>
#include <vector>
#include <bitset>
#include <string>
using namespace std;
namespace nb
{
	struct BKDRHash
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto ch : key)
			{
				hash *= 131;
				hash += ch;
			}
			return hash;
		}
	};

	struct APHash
	{
		size_t operator()(const string& key)
		{
			unsigned int hash = 0;
			int i = 0;

			for (auto ch : key)
			{
				if ((i & 1) == 0)
				{
					hash ^= ((hash << 7) ^ (ch) ^ (hash >> 3));
				}
				else
				{
					hash ^= (~((hash << 11) ^ (ch) ^ (hash >> 5)));
				}

				++i;
			}

			return hash;
		}
	};

	struct DJBHash
	{
		size_t operator()(const string& key)
		{
			unsigned int hash = 5381;

			for (auto ch : key)
			{
				hash += (hash << 5) + ch;
			}

			return hash;
		}
	};

	struct JSHash
	{
		size_t operator()(const string& s)
		{
			size_t hash = 1315423911;
			for (auto ch : s)
			{
				hash ^= ((hash << 5) + ch + (hash >> 2));
			}
			return hash;
		}
	};

	// 假设N是最多存储的数据个数
	// 平均存储一个值，开辟X个位
	template<size_t N,
		size_t X = 6,
		class K = string,
		class HashFunc1 = BKDRHash,
		class HashFunc2 = APHash,
		class HashFunc3 = DJBHash,
		class HashFunc4 = JSHash>
	class BloomFilter
	{
	public:
		void set(const K& key)
		{
			size_t hash1 = HashFunc1()(key) % (N * X);
			size_t hash2 = HashFunc2()(key) % (N * X);
			size_t hash3 = HashFunc3()(key) % (N * X);
			size_t hash4 = HashFunc4()(key) % (N * X);

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

		bool test(const K& key)
		{
			size_t hash1 = HashFunc1()(key) % (N * X);
			size_t hash2 = HashFunc2()(key) % (N * X);
			size_t hash3 = HashFunc3()(key) % (N * X);
			size_t hash4 = HashFunc4()(key) % (N * X);
			// 有一个为0则一定不存在
			if (!_bs.test(hash1) || !_bs.test(hash2) || !_bs.test(hash3) || !_bs.test(hash4))
			{
				return false;
			}

			// 前面判断不在都是准确，不存在误判
			return true; // 可能存在误判，映射几个位置都冲突，就会误判
		}

	private:
		std::bitset<N* X> _bs;
	};

	void test_bloomfilter1()
	{
		// 10:46继续
		string str[] = { "apple", "banana", "cherry", "fruit", "peach1","1peach","p1each","p11each","1peach1" };
		BloomFilter<10> bf;
		for (auto& str : str)
		{
			bf.set(str);
		}

		for (auto& s : str)
		{
			cout << bf.test(s) << endl;
		}
		cout << endl;

		srand(time(0));
		for (const auto& s : str)
		{
			cout << bf.test(s + to_string(rand())) << endl;
		}
	}

	void test_bloomfilter2()
	{
		srand(time(0));
		const size_t N = 100000;
		BloomFilter<N> bf;

		std::vector<std::string> v1;
		std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";

		for (size_t i = 0; i < N; ++i)
		{
			v1.push_back(url + std::to_string(i));
		}

		for (auto& str : v1)
		{
			bf.set(str);
		}

		// v2跟v1是相似字符串集，但是不一样
		std::vector<std::string> v2;
		for (size_t i = 0; i < N; ++i)
		{
			std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
			url += std::to_string(999999 + i);
			v2.push_back(url);
		}

		size_t n2 = 0;
		for (auto& str : v2)
		{
			if (bf.test(str))
			{
				++n2;
			}
		}
		cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

		// 不相似字符串集
		std::vector<std::string> v3;
		for (size_t i = 0; i < N; ++i)
		{
			string url = "zhihu.com";
			url += std::to_string(i + rand());
			v3.push_back(url);
		}

		size_t n3 = 0;
		for (auto& str : v3)
		{
			if (bf.test(str))
			{
				++n3;
			}
		}
		cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
	}
}
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202

五、海量数据面试题

1、位图应用

1. 给定100亿个整数，设计算法找到只出现一次的整数？

数的状态：0次、1次和1次以上

template<size_t N>
class twobitset
{
public:
	void set(size_t x)
	{
		if (!_bs1.test(x) && !_bs2.test(x)) // 00 --> 01 0次变成1次
		{
			_bs2.set(x); // 01
		}
		else if (!_bs1.test(x) && _bs2.test(x)) // 01 --> 1次变成1次以上
		{
			_bs1.set(x);
			_bs2.reset(x); // 10
		}

		// 10 1次以上不做处理
	}

	void PirntOnce()
	{
		for (size_t i = 0; i < N; ++i)
		{
			// 01是出现一次
			if (!_bs1.test(i) && _bs2.test(i))
			{
				cout << i << endl;
			}
		}
		cout << endl;
	}

private:
	bitset<N> _bs1;
	bitset<N> _bs2;
};

void test_twobitset()
{
	twobitset<100> tbs;
	int a[] = { 1, 2, 3, 4, 4, 5, 5, 99, 22 };
	for (auto e : a)
	{
		tbs.set(e);
	}

	tbs.PirntOnce();
}
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

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

假设这里的整数范围不超过32位整数范围。分别开两个位图，42亿个比特位表示每个整数是否存在，每个位图约0.5G（1GB约10亿字节80亿比特，1MB约100万字节），两个位图都存在的数则为交集。

3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
   

2、哈希切割

1. 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

$A_i$小文件超过1G怎么办?

情况1： 小文件中冲突的ip很多，都是不同的ip，大多数是不重复的。map统计不下。换个字符串哈希函数，递归再切分。

情况2：小文件中冲突的ip很多，大多都是相同的ip，大多数是重复。map可以统计

如何区分这两种情况？

情况1下map会因内存不足，insert失败，new节点抛异常。通过捕获异常就能区分两种情况

2. 与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

3、布隆过滤器

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

精确算法与上面的哈希切割问题解决办法大致相同：

近似算法：
使用 Bloom Filter 算法找到两个文件的交集的步骤：

1. 从第一个文件中读取所有查询，并将每个查询插入 Bloom Filter 中。
2. 从第二个文件中读取所有查询，并检查每个查询是否在 Bloom Filter 中。
3. 如果查询存在于 Bloom Filter 中，则是交集输出查询并继续处理下一个查询。
4. 如果查询不存在于 Bloom Filter 中，则继续处理下一个查询。

• 如何扩展BloomFilter使得它支持删除元素的操作
  可行的方法是加计数器但是空间消耗大。

---

参考博客：

1. 详解布隆过滤器的原理
2. 字符串Hash函数对比

---