【C++ ——— 哈希】位图 | 布隆过滤器

1、位图

1.1位图概念

1.面试题
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】
解决方案：
1.二分查找。[不能用这种方式：1.要排序，2.40亿个整数需要约16g的内存，内存开不出这么大的空间]

2. 位图解决：我们只需要标记这个值在不在，没必要存下来，让每个值映射一个比特位，需要2^32个比特位，也就是只需要0.5G。数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。

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

2.位图实现

我们用代码来实现上面的思路。

//N是需要多少比特位
template<size_t N>
class bitset
{
public:
	//构造
	bitset()
	{
		//构造函数提前开空间
		//_bits.resize(N/32+1, 0);
		_bits.resize((N >> 5) + 1, 0);
		              //2^5是32 且移位运算优先级要注意。
	}
	//映射一个值到位图中
	void set(size_t x)
	{
		//要把第j位处理为1，其他位不变。
		//找一个第j位为1其他位为0的补码
		//让他们或运算，或是两个位都为0时才为0
		size_t i = x / 32;
		size_t j = x % 32;
		_bits[i] |= (1 << j);//左移操作符向高位移动
							 //右移操作符向低位移动
							 //注意左移右移操作符不是方向的问题，是高位和低位的问题。
		
	}
	//将x的对应比特位置为0
	void reset(size_t x)
	{
		//把第j位处理位0，其他位不变
		//同上找第j位为0，其他位为1的补码
		//按位与运算。 与运算两个位都为1才为1
		size_t i = x / 32;
		size_t j = x % 32;
		_bits[i] &= ~(1 << j);
	}
	//查看这个x在位图中是否为1，为1就是存在。
	bool test(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;

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

private:
	vector<int> _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
40
41
42
43
44
45
46
47
48

我们看上题说要开40亿个整形我们要怎么开呢？

//直接写为16进制
bitset<oxffffffff> bigbs;
//-1传过去转化为size_t类型直接能转化为最大值。
bitset<-1> bigbs2;
1
2
3
4

位图的应用

1.一百亿个整数，设计算法找到只出现一次的整数?

这有一百亿个数会不会出现空间不够的情况？
不会。就算是一百亿个整数最多也就42亿九千万个整数会出现很多重复值。
不论是100亿还是1000亿都只开42亿九千万个空间
这里需要三种状态：

1. 出现0次
2. 出现1次
3. 出现两次即以上
   可以用两个位表示这三种状态。
   我们用两个位图表示一个位。
   

位图代码实现：

//用两个位图来表示一个值
class twobitset
{
public:
	void set(size_t x)
	{
		//00->01
		//01->10
		//10->状态不变出现了两次即以上
		if (_bs1.test(x) == false && _bs2.test(x) == false)
		{
			_bs2.set(x);
		}
		else if (_bs1.test(x) == false && _bs2.test(x) == true)
		{
			_bs1.set(x);
			_bs2.reset(x);
		}

	}
	void PrintfOnce()
	{
		for (size_t i = 0; i < N; i++)
		{
			if (_bs1.test(i) == false && _bs2.test(i) == true)
			{
				cout << i << endl;
			}
		}
		cout << endl;
	}



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
33
34
35
36
37
38

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

跟上题思路很像，各自映射到一个位图中。一个值两个位图都存在，就是交集。（先去重复值）

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

我们可以用上面的一个值映射两个位图解决这个方法，但是我们只有1G内存所以还是要做一些特殊处理的

template<size_t N>
//用两个位图来表示一个值
class twobitset
{
public:
	void set(size_t x)
	{
		//00->01
		//01->10
		//10->11
		//11->状态不变
		if (_bs1.test(x) == false && _bs2.test(x) == false)
		{
			_bs2.set(x);
		}
		else if (_bs1.test(x) == false && _bs2.test(x) == true)
		{
			_bs1.set(x);
			_bs2.reset(x);
		}
		else if (_bs1.test(x) == true && _bs2.test(x) == false)
		{
			_bs1.set(x);
			_bs2.set(x);
		}
	}
	void Printf()
	{
		for (size_t i = 0; i < N; i++)
		{
			if (_bs1.test(i) == false && _bs2.test(i) == true)
			{
				cout <<"1->"<< i << endl;
			}
			else if(_bs1.test(i) == true && _bs2.test(i) == false)
			{
				cout << "2->" << i << endl;
			}
		}
		cout << endl;
	}
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
33
34
35
36
37
38
39
40
41
42
43
44
45

3.布隆过滤器

搜索

1. 暴力排查 数据量大了，效率就低
2. 排序+二分查找 问题a：排序有代价 问题b：不方便
3. 搜索树-> AVL树+红黑树
4. 哈希 ->扩容代价很高
   ——————————————
   以上数据结构，都是以空间换时间、空间消耗很高

数量很大的数据
5、[整形]的在不在及其扩展问题 – 位图及其变形 以时间换空间的算法
6、[其他类型]的在不在呢？ --需要用到布隆过滤器

3.1 布隆过滤器的提出

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？

1. 用哈希表存储用户记录，缺点：浪费空间
2. 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
3. 将哈希与位图结合，即布隆过滤器

3.2布隆过滤器概念

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

用什么方法能让字符串映射到位图中呢？
我们可以考虑把先把字符串转换为一个对应的整形，不过整形的位图一个整形对应一个位，有42亿多的整型值够我们匹配，但是字符串呢？字符串可是无限的，所以肯定会有不同的字符串映射到同一个整形。
不过我们只需要判断这个字符串在不在
以上思路：
判断：在（不准确，可能存在误判不同字符串映射的整形是同一个。本质也就是哈希冲突导致的。）
判断：不在（准确，没有字符串映射肯定就是不在的）

看下图中映射方式：
一个字符串映射三个位置的整形值。会降低误判的概率
布隆过滤器无法完全解决误判，所以布隆过滤器出现的场景就需要接受误判

布隆过滤器场景：
我们玩游戏创建角色时，需要给角色创建昵称，如果直接拿你输入的昵称和数据库里存的已有昵称进行比较那样效率会很低。

我们可以在数据库和玩家客户端的中间建立一个布隆过滤器
布隆过滤器只能准确判断不在数据库中的数据。
判断在数据库中的情况时，需要额外去数据库中匹配数据。

布隆过滤器、代码实现：

struct BKDRHash
{
	size_t operator()(const string& key)
	{
		//BKDR
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};


template<size_t N ,class K = string
		,class HashFunc1 = BKDRHash
		,class HashFunc2 = BKDRHash
		,class HashFunc3 = BKDRHash>
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t Hash1 = HashFunc1()(key) % N;
		size_t Hash2 = HashFunc2()(key) % N;
		size_t Hash3 = HashFunc3()(key) % N;

		_bs.set(Hash1);
		_bs.set(Hash2);
		_bs.set(Hash3);
	}
	//一般不支持删除，删除一个值可能会影响其他值
	//非要支持删除的话，可以使用引用计数法，不过那样会
	void Reset(const K& key);
	bool Test(const K& key)
	{
		size_t Hash1 = HashFunc1()(key) % N;
		if (_bs.test(Hash1) == false)
			return false;
		size_t Hash2 = HashFunc2()(key) % N;
		if (_bs.test(Hash2) == false)
			return false;
		size_t Hash3 = HashFunc3()(key) % N;
		if (_bs.test(Hash3) == false)
			return false;


		//可能存在误判的风险
		return true;
	}
private:
	bitset<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

海量数据的面试题

布隆过滤器（哈希切分）

1.给两个文件，分别由100亿个query（数据请求），我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法（近似算法就是布隆过滤器算法）：

假设：平均一个query是50byte，100亿个query就是5000亿个byte。1G约等于10亿byte
那么5000亿byte 约等于 500G
内存存不下，红黑树/哈希表都使用不了。
分析：
1.我们可以先把两个文件的500G文件分成500份，每份1G左右

2.但是只是单纯的划分了500份空间对我们的查询比对操作效率，没有任何的提高。所以我们在划分空间时需要用到哈希算法，通过哈希函数把映射位置相同或相似的值，集中在一个小块。
我们做了这么多的目的就是为了把这块空间加载到内存中，
下图这种方式就是哈希切分法

3.之后我们把Ai和Bi的数据分别加载到内存中，对他们两个分别进行位图映射。然后判断他们中是否有交集

4.但是这种思路还有一个问题–如果单个文件过大呢？
比如这个小文件有10G
这种单个文件过大差不多有两种情况：
一、这个小文件，内大多数都是相同的query
二、这个小文件，有很多种不同的query

解决方法：
Ai和Bi分别插入setA和setB中
不管文件大小直接插入：
情况一：这个小文件大多都是相同query，插入第一个后，后面重复插入就会set失败。
情况二：不断插入set后，内存不足，会抛异常，需要换个哈希函数把这个小文件进行二次切分，再找交集。

2.给一个超过100G大小的log file，log 中存放着IP地址，设计算法找到出现次数最多的IP地址？如何找到top K的IP？

哈希切割：
1.我们先要统计次数，但是文件太大加载不到内存，我们无法统计次数，可以用哈希切分把相似IP地址分到一个区域里（跟上题思路类似）（相同IP一定会进入同一个文件）
2.切分完，直接在对应Ai中的数据使用map或者unordered_map统计次数，记得统计完次数和最大值比对进行更新。
3.top K问题：额外建一个小堆如果次数比堆顶大就进堆。