【C++进阶08】哈希的应用(位图and布隆过滤器)

一、位图

1.1 位图的概念

面试题

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

能想到的解决思路：

1. 遍历，时间复杂度O(N)
2. 排序(O(NlogN)) + 利用二分查找: logN
3. 放到哈希表或红黑树

40亿整数就是16GB，无法全部加载到内存
遍历、排序和二分查找就都不太现实
虽然可以在文件中归并，但就慢了很多
文件中不能用下标，自然无法二分查找

虽然可以将数据一段一段放进哈希表和红黑树
但每次将数据插入进红黑树又释放
相当于暴力查找40亿数据
红黑树的特性完全没用上

所以以上3点都是不合适的
最大的原因就是内存不足

位图解决
数据是否在给定的整形数据中
结果是在或者不在，刚好是两种状态
那么可以用比特位表示数据是否存在
1为存在，0为不存在

比如数据{1,2,4,9,1517,23}在位图的样子

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

一个比特位就能表示一个整型数据在或不在
一个整型就是32比特位，相当于缩小了32倍
也就是说16G的数据只需要0.5G

1.2 位图的模拟实现

位图的三个主要接口：

1. set：将数据映射位置置成1，表示存在
2. reset：将数据映射位置置成0，表示删除
3. test：检测数据是否存在于位图

template <size_t N>
class bitset
{
public:
	bitset()
	{
		_bits.resize(N / 8 + 1, 0); // 需求N个比特位,按字节给,所以除8.除会去余,所以加1
	}

	void set(size_t x) // 将x比特位置1
	{
		size_t i = x / 8; // 计算x映射的位在第i个char数组位置
		size_t j = x % 8; // 计算x映射的位在这个char的第j个比特位
		
		_bits[i] |= (1 << j);
	}

	void reset(size_t x) // 将x比特位置0
	{
		size_t i = x / 8;
		size_t j = x % 8;

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

	bool test(size_t x) // 检测位图中x是否为1
	{
		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

1.3 位图的应用

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

方法：

1. 创建两个位图对象bs1、bs2
2. 遍历数据
   出现0次用00表示
出现1次用01表示
出现2次用10表示
出现3次及以上用11表示

如果数据映射的位置在bs1里为1
在bs2里为0表示此数据出现过2次
如果在bs1和bs2里都为1，表示出现3次及以上
方法实现：

template <size_t N>
class twobitset
{
public:
	void set(size_t x) 
	{
		// 00 -> 01
		if (_bs1.test(x) == false 
		&& _bs2.test(x) == false)
		{
			_bs2.set(x);
		}
		else if (_bs1.test(x) == false 
			&& _bs2.test(x) == true)
		{
			// 01 -> 10
			_bs1.set(x);
			_bs2.reset(x);
		}
		// 10 不变
		
	}

	void print()
	{
		for (size_t i = 0; i < N; i++) 
		{
			if (_bs2.test(i))
				cout << i << " ";
		}
	}
private:
	bitset<N> _bs1;
	bitset<N> _bs2;
};

void test_twobitset3()
{
	twobitset<1000> bs;
	int a[] = { 0, 12, 12, 0, 20, 12, 12, 0, 223, 22, 45, 4 };
	for (auto e : a)
	{
		bs.set(e);
	}

	bs.print();
}
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

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

方法1：
其中的一个文件读到内存的位图中
再读另一个文件，判断在不在上面的位图
在就是交集

问题：
找出的交集存在重复值

解决方法1：
一个数为交集就在第一个文件set那个数

解决方法2：
读取文件1映射到位图1
读取文件2映射到位图2
判断数据映射的位置在这两个位图中
是否都为1

for (int i = 0; i < N; i++)
{
	if (bs1.test(i) && bs2.test(i))
	{
		// 交集
	}
}
1
2
3
4
5
6
7

或者按位与这两个位图

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

定义两个位图对象
将数据插入到位图
出现0次用00表示
出现1次用01表示
出现2次用10表示
出现3次及以上用11表示

除了两个位图对应位置都为1
其他都打印

二、布隆过滤器

位图的优点：

1. 速度快、节省空间

缺点：

1. 只能映射整形，其他如浮点数、string等
   不能存储映射

布隆过滤器便是解决此缺点

2.1 布隆过滤器提出

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

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

2.2 布隆过滤器概念

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

用多个哈希函数将字符映射到不同的位置
以此降低重复率，查找时在所有映射的位置
查看是否均为1

查找一个值在与不在
在：是不准确的，存在误判
不在：是准确的
比如美团，本来不在
查找时每个映射的位置都跟别人冲突
导致认为它在

2.3 布隆过滤器的使用场景

1. 能容忍误判场景
   比如：改名时，快速判断昵称是否使用过

昵称在数据库，而数据库在磁盘
如果去磁盘查找修改的昵称是否使用过
效率非常慢，我们平时改昵称时
只要输入就能立即反馈昵称是否使用

这时可以把所有用户昵称放入布隆过滤器
即使误判修改昵称已使用，用户也感知不到
(只要误判率不高还是可以接受的)

2.4 布隆过滤器的实现

如何选择哈希函数个数和布隆过滤器长度
k 为哈希函数个数
m 为布隆过滤器长度
n 为插入的元素个数
p 为误报率


代码实现：

struct BKDRHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash = hash * 30 + ch;
		}
		return hash;
	}
	
};

struct APHash
{
	size_t operator()(const string& s) // 仿函数的作用：把一个类当作对象去访问或把一个对象像函数去使用
	{
		size_t hash = 0; // 加register放到最前面表示建议变量放到寄存器里面
		for (long i = 0; i < s.size(); i++)
		{
			size_t ch = s[i];
			if ((i & 1) == 0) // i 是偶数走if，i 是奇数else.奇数二进制的低位一定是1，按位与1得到的便是奇数
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			else
				hash ^= (~((hash << 11) ^ ch ^ (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;
	}
};

// N是key,插入值的个数
template<size_t N, 
class K = string,
class Hash1 = BKDRHash,
class Hash2 = APHash,
class Hash3 = DJBHash>
class BloomFilter
{
public:
	void set(const K& key)
	{
		size_t len = N * _X;
		size_t hash1 = Hash1()(key) % len; // 用Hash仿函数转成可以取模的整型值，模N是怕转出来的值超出N
		_bs.set(hash1);

		size_t hash2 = Hash2()(key) % len;
		_bs.set(hash2);

		size_t hash3 = Hash3()(key) % len;
		_bs.set(hash3);
		cout << hash1 << " " << hash2 << " " << hash3 << endl;
	}

	bool test(const K& key) // 判断3个位置，有一个位置为0就是不在
	{
		size_t len = N * _X;
		size_t hash1 = Hash1()(key) % len; 
		if (!_bs.test(hash1))
			return false;
		size_t hash2 = Hash2()(key) % len;
		if (!_bs.test(hash2))
			return false;

		size_t hash3 = Hash3()(key) % len;
		if (!_bs.test(hash3))
			return false;
		return true;
	}
private:
	static const size_t _X = 6; // 比重为6，冲突率5%以内.比重建议5-10(冲突率1%-10%)
	bitset<_X * N> _bs; // 开_X倍的空间,空间开得越大,冲突率越低
};
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

2.5 布隆过滤器的应用

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

100亿query：假设每个query平均50byte
100亿就是5000亿byte，也就是大约占用500G

1. 可以把每个文件分成1000份读进内存
   每份是0.5个G

B文件的每一份在A文件的每一份里去找
但是这样时间复杂度太高了
于是可以用哈希函数来切分文件
哈希切分：i = HashFunc(query) % 1000
每个query，算出i是多少就进入Ai小文件
B也是一样，算出i放进Bi小文件
B0、B1……在对应的A0、A1……
小文件里去找，找到了就是交集

跟之前的哈希桶很像
进入同一个桶的都是冲突的值
在这里A和B相同的值用的同一个哈希函数
便一定会进入同一个编号的文件

会导致的问题：
因为不是平均切分，可能会出现冲突多
每个Ai、Bi小文件过大

1. 单个文件大量重复query
2. 单个文件大量不同query

解决方法：
直接使用unordered_set/set
依次读取文件query，插入set中

1. 如果读取整个小文件query
   都可以成功插入set，说明是情况1
2. 如果读取整个小文件query
   插入过程抛异常则是情况2
   换其他哈希函数，再次分割求交集

说明：set插入key如果已经有了返回false
如果内存不足抛bad_alloc异常
剩下的都会成功

2、如何扩展BloomFilter使得它支持删除元素的操作

删除一个元素可能会影响其它元素
用多个位图计数的方式表示每个位置被映射了几次
删除时减减该位置

3、哈希切割
给一个超过100G大小的log file, log中存着IP地址,
设计算法找到出现次数最多的IP地址？
与上题条件相同，如何找到top K的IP？

解决方法：
哈希切分成500个小文件
依次读取数据，i = HashFunc(ip)%500
这个ip就是第i个小文件

依次处理每个小文件
使用unordered_map/map统计ip出现次数

1. 统计过程抛异常，说明单个文件过大
   冲突太多，需要重新换哈希函数
   再次哈希切分这个小文件
2. 如果没有抛异常，则正常统计
   统计完一个小文件，记录最大的
   clear map，再统计下一个小文件

总结特点：
相同的ip一定进入相同的小文件
读取单个小文件就可以统计ip出现次数

本篇博客完，感谢阅读