哈希应用: 位图 + 布隆过滤器

哈希应用: 位图 + 布隆过滤器

1. 位图

1.1 提出问题

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

常见解决方式:

1. 遍历，时间复杂度O(N)
2. 排序(O(NlogN))，利用二分查找: logN

分析:

无论是法1还是法2，40亿个整数，每个整数4个字节，一共需要160亿字节，所占用空间是16GB，占用太多空间，所以上面的方法都是不可取的。因此我们提出了使用位图来解决问题。

速记: 1G ≈ 10亿字节 。

1.2 位图概念

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。比如: 如果二进制比特位为1，代表存在，为0代表不存在。

还是上面的问题，40亿个不重复的无符号整数，使用位图后就是40亿个比特位，40亿/8 = 5亿Byte，5亿Byte = 512MB，大大节省了空间。

我们无法开这么大的数组，但我们采用的是bit位的标记，即值是几，就把第几个位标记成1。

那么如何去找呢？实际上我们把数组的元素类型规定为char(int也可以)，这样就可以通过如下的方式去找任意一个数：x

• i = x / 8 计算x映射的位在第i个char数组的位置
• j = x % 8 计算x映射的位在这个char的第j个比特位

比特位顺序问题:

事实上，比特位的顺序与机器的大小端(大小端是按照字节序的，一个char就是一个字节)无关，这里定义左边是高地址，右边是低地址(也可以右高左低)，与我们平时习惯保持一致，也方便理解后续的操作

1.3 位图实现

对于位图的实现，主要是插入，删除，检测这3个功能，这3个功能的实现依赖的就是位运算

namespace yj
{
	template<size_t N>    //非类型模板参数
	class bitset
	{
	public:

		bitset()
		{
			_bits.resize(N / 8 + 1, 0);
		}

		bool test(size_t x)   //检测这个值是否存在
		{
			size_t i = x / 8;    
			size_t j = x % 8;

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


		void set(size_t 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)  //将某比特位置0
		{
			size_t i = x / 8;     //计算x映射的位在第i个char数组的位置
			size_t j = x % 8;

			_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
40
41

位图的结构是按照范围去开空间的，如果我们想要开满空间可以这样写:

void test_bitset2()   //开满的写法, 按照范围去开
{
    //两种写法均可
	yj::bitset<-1> bs1;
	yj::bitset<0xFFFFFFFF> bs2;      //整型的最大值
}
1
2
3
4
5
6

1.4 位图应用

1.4.1 变形题1

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

对于此整数有三种状态：

1. 出现0次 00
2. 出现1次 01
3. 出现2次及以上 10

因此，我们可以通过两个比特位来标记：此方式虽然可行，但需要第上述代码做出很大变动。那么我们可以采用另一种方式代表两个比特位，即以开两个位图的方式，每个位图的一个比特位组合成两个比特位进行标记：

代码

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
			_bs2.reset(x);
			_bs1.set(x);
		}
		//10 -> 11
	}


	void Print()
	{
		for (int i = 0; i < N; ++i)   //找只出现1次的
		{
			if (_bs2.test(i))
			{
				cout << i << 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

测试:

1.4.2 变形题2

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

和第一题的思路相同，就是变形题1的变形题，开两个位图进行处理即可

对于此整数有三种状态：

1. 出现0次 00
2. 出现1次 01
3. 出现2次 10
4. 出现3次及以上 11

1.4.3 找文件交集

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

虽然这里给了100亿个整数，但是整型最大值是42亿多，这就注定了，这里会存在大量重复数据

思路1

其中一个文件的值，读到内存的一个位图中，再读取另一个文件，判断在不在第一个位图中，在，就是交集

但是这里还会存在一定问题: 比如第一个文件中值是{1, 3, 6}，第二个文件中值是{1, 2, 3, 1, 1, 6} 那这种方法找出的交集就是: {1, 3, 1, 1, 6} 即找出的交集存在重复的值，我们必须要对其再次去重才可以。

改进方法:

每次找到交集值，都将上面位图的值设置为0，可以解决找到交集有重复值的问题

此类方法适用于数据数量较少的问题，比如有10亿个数据

思路2

给两个位图，位图1和位图2，读取文件1的数据映射到位图1，读取文件2的数据映射到位图2，遍历检测这两个位图，如果该位既在位图1存在又在位图2存在就是交集

1.4.4 总结

1. 快速查找某个数据是否在一个集合中
2. 排序 + 去重
3. 求两个集合的交集、并集等
4. 操作系统中磁盘块标记

1.5 位图优缺点

优点: 速度快，节省空间

缺点: 只能映射整型，其他类型如: 浮点数，string等等不能存储映射

所以我们引出了布隆过滤器

2. 哈希切割

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

用map显然是不行的，因为内存过大。位图同样不适用，因为找到出现次数最多的ip地址属于的模型，而位图的功能是找在或者不在的问题，以及出现的次数是确定的问题，属于的模型，所以与位图无关。

100个G显然放不进内存。因此我们要考虑将100G的文件细分成小文件，但是直接细分会导致统计不全，所以采用哈希切分的方式将HashFunc(ip)%500分成500个小的Ai号文件，这个ip就在第i个小文件中，依次处理每个小文件，使用一个unordered_map/map来统计ip出现的次数。

这里会现两种情况：

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

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

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

我们可以建一个小堆来实现，堆中存放的是pair键值对，其中key是ip，value是次数

3. 布隆过滤器

3.1 提出问题

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

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

3.2 布隆过滤器概念

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

比如这样的问题： 将以下字符串映射到各个比特位，但字符串数量较小时可能不会出现冲突，但是一旦来了一个新的字符串就可能会出现冲突，此时要如何解决呢？

首先要明白冲突是一定会存在的，我们要考虑降低冲突的概率。

一个值映射一个位置，容易误判；一个值映射多个位置，就可以降低误判率 。

上面的问题，我们可以考虑每个值映射2个位置

但是还可能会存在冲突，我们发现：

• 在，不准确，会存在误判。

• 不在，是准确的。

可能存在是因为映射可能出现重复，即产生冲突，这是布隆过滤器无法避免的，但是可以通过增加HashFunc的映射次数从而降低冲突引起的误判率。

很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

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

如何选择适合业务的 k 和 m 值呢，这里直接贴一个公式：k = m ∗ l n 2 / n k = m*ln2 / nk=m∗ln2/n

可以看出，当k=3时，m≈4.2*n。因此，下面代码中我们采用6N大小的布隆过滤器长度无疑是非常合适的。

3.3 布隆过滤器的各个接口

3.3.1 布隆过滤器的插入

向布隆过滤器中插入：“baidu”

3.3.2 布隆过滤器的查找

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

注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。
比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

3.3.3 布隆过滤器删除

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

比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。
一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。

缺陷：

1. 无法确认元素是否真正在布隆过滤器中。
2. 存在计数回绕。

3.4 布隆过滤器的实现

仿函数实现的参考:

各种字符串Hash函数 - clq - 博客园 (cnblogs.com)

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

struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long i = 0; i<s.size(); i++)
		{
			size_t ch = s[i];
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& s)
	{
		register size_t hash = 5381;
		for(auto ch:s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};


template<size_t N, class K = string, 
	class Hash1= BKDRHash, class Hash2= APHash, class Hash3= DJBHash>  //K是存放的类型
class BloomFilter
{
public:
	void set(const K& key)
	{
		size_t len = N * _X;

		size_t hash1 = Hash1()(key) % len;
		_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)
	{
		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;  
	bitset<N*_X> _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
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

3.5 布隆过滤器的优缺点

优点：

• 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
• 哈希函数相互之间没有关系，方便硬件并行运算
• 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
• 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
• 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
• 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

缺点：

• 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
• 不能获取元素本身
• 一般情况下不能从布隆过滤器中删除元素
• 如果采用计数方式删除，可能会存在计数回绕问题

3.6 布隆过滤器的应用

3.6.1 问题

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

• 近似算法：使用布隆过滤器，先将其中一个文件set进布隆过滤器中，再将另一个文件的数据进行比对，可以淘汰一定不是交集的那部分，不过余下的那部分数据中，仍会有非交集的存在。
• 精确算法：使用哈希切分，将两个大文件分别切成一个个小文件A0-A999，B0-B999（单个小文件超过1G参照上文哈希切分对于此问题的解决方法）；因为使用的是相同的哈希函数，所以A和B相同query字符串会进入编号相同的小文件，那么交集必定存在于A0和B0，A1和B1等这种相同下标的小文件中。但是由于不是平均切分可能会出现冲突多使Ai，Bi小文件过大。此时有两种情况: 单个文件中有某个大量重复的query；单个文件中有大量不同的query。这时直接使用一个unordered_set/set，依次读取文件query，插入到set中，若读取整个小文件query都可以成功插入set，那么说明是情况1；若读取整个小文件query，插入过程中抛异常则是情况2需要更换哈希函数，再次分割，再求交集。求交集: 将Ai号小文件query放入set中，Bi小文件query去比对看是否在这个set中，在就是交集。

3.6.2 实例

判断昵称是否使用过: 直接把昵称放入布隆过滤器中，查找结果不在，则是准确的；查找结果在，那就会存在误判，但只要误判率不高，这里可以接受。

判断手机号是否使用过: 在客户端和数据库之间建立一个布隆过滤器，如果通过布隆的结果发现没有找到，那么一定不在，也就不用继续向数据库中查找了。如果在，那么就需要进数据库中一一查找，因为布隆对于找到的值是不一定存在的。所以通过布隆可以提高数据不在时查找的效率。