【C++学习】哈希的应用—位图与布隆过滤器

文章简介：
在这篇文章中，你会学习到关于哈希思想的最常见的两个应用，也就是 位图 与 布隆过滤器，
文章会讲解位图和布隆过滤器的概念，底层实现，对应的适应的场景，以及相关经典 海量数据面试题 及解析。

1.位图

1.1位图的概念

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

比如这道 腾讯 的面试题目：
面试题目：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
解析：
40亿个整型数据所需内存大小：10亿字节约等于1G，那么40亿个整型，就是40亿*4（字节）=160亿字节≈16G。

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

上面的两种做法都是不可行的，因为内存不够。

3. 位图解决 数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位（0/1）来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。

第三种方法，利用位图解决，因为是要在40亿个数中查找，数据的类型是一个整型，范围为0~UINT_MAX。所以我们只需要UINT_MAX个比特位，所需的内存也就是512M,然后将这40亿个整数利用这UINT_MAX个比特位就可以表示他们的存在状态；

图解：
假设有一个整型数组array（如下图），因为里面的数据范围为1~22，所以我们就可以开一个int大小的数组（有32个比特位，可以表示32个不同数的存在状态），映射地址的方法这里采用的是直接定址法；
计算：第i个整型中：i = （该数）/ 32；
该整形中第j个比特位：j = （该数）% 32；

1.2位图的实现

1. 因为位图需要整型的连续的空间，所以这里我们用vactor 即可

2. 所开空间的大小的计算：
   这里开的是一个范围，假如上面的面试题，有40亿个整型数据，因为有40亿个数据，但是不能 只开40亿个比特位的空间，因为如果只开了40亿个比特位的话，就只能表示数据大小为0~40亿的数据，然而数据类型为int，数据最大值超过了40亿，这样超过了40亿的数据就表示不了了。

3. 因为空间开的大小不一样，所以这里需要利用非类型模板参数

4. 所开的空间是以整型为单位开辟，所以确认了所需的比特位后，还需计算是多少个int（32个比特位）大小，如果换算为int大小，有余数的话，就应该多开一个int大小

template<size_t N>     //非类型模板参数
class bitset
{
public:
	bitset()
	{
		_bitset.resize(N/32+1, 0);  //所需开的空间，因为空间都只能以整型为单位开，所以需要除以32
	}
	void set(size_t x)       //将x对应的比特位置1
	{
		size_t i = x / 32;    //确定是第几个int
		size_t j = x % 32;    //确定是该int里面的第几个比特位
		_bitset[i] |= (1 << j);    //将1左移j个比特位，在与该位置的数进行 或等操作（如下图有解析）
	}
	void reset(size_t x)     //将x对应的比特位置0
	{
		size_t i = x / 32;
		size_t j = x % 32;
		_bitset[i] &= ~(1 << j);     //将1左移j个比特位，然后取反，再与该位置的数进行 与等操作（如下图有解析）
	}
	bool test(size_t x)     //查找x是否存在
	{
		size_t i = x / 32;
		size_t j = x % 32;
		return _bitset[i] & (1 << j);   //将1左移j个比特位，再与该位置的数进行 与操作（如下图有解析）
	}
private:
	vector<int> _bitset;
};
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

解析：

3.位图的应用

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

2.布隆过滤器

2.1 布隆过滤器提出

利用位图只能处理整型数据，但是现实生活中，不只是整型需要进行查找是否存在等问题，还有其他类型，比如：字符串string…
但是如果将字符串转为整型，然后再利用位图处理的话，就会面临一个问题，
就是可能不同的字符串（或则其他类型）转为整型后，利用哈希函数映射的位置相同，这就有可能误判。
分析：误判只有可能将本来不存在的一个字符串（或则其他）误判为存在，因为有可能有一个已经存在的数据与这个字符串转为整型后映射的位置相同。

举个例子：
两个数据 “abcd” 和 “aacc”
如果就按照将数据里面的每个字符相加转为整型再映射，则他们的映射位置会一样，如果“abcd”已经存在了，但是现在要判断“aacc”是否存在，这是就会误判为存在；

2.2布隆过滤器概念

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

布隆过滤器的思想就是：
将一个数据利用不同的哈希函数（假设有X个）映射到多个位置，在位图中进行标记存在，当来了一个数据需要判断存不存在的问题时，就需要将这数据利用这X个哈希函数进行映射到位图上判断在不在，如果这个数经过这了这X个哈希函数映射后，在位图中判断全部都在，那么就判断这个数据存在，如果有一个判断不在，那就不在。

如图：obj1与obj2用3个不同的哈希函数fun1,fun2,fun3映射，在位图进行标记；

注意：这里判断存在也是存在误判的，只是降低了误判概率。

2.3如何选择哈希函数个数和布隆过滤器长度

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

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

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

如何选择适合业务的 k 和 m 值呢，

公式：k = ln2 * ( m / n ）

2.4布隆过滤器的实现

2.4.1布隆过滤器插入操作

与位图类似，只是布隆过滤器的插入需要利用多个哈希函数映射多个位置。
如图：

代码实现：

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

struct Func2
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (size_t i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0) // 偶数位字符
			{
				hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
			}
			else              // 奇数位字符
			{
				hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct Func3
{
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash = hash * 33 ^ ch;
		}
		return hash;
	}
};

template<size_t N , 
	class K = string ,
	class Hash1=Func1, 
	class Hash2=Func2, 
	class Hash3 =Func3>
class bloom
{
public:
    /插入操作
	void set(const K& key)
	{
		size_t i = Hash1()(key) % M;
		size_t j = Hash2()(key) % M;
		size_t z = Hash3()(key) % M;

		_bs.set(i);
		_bs.set(j);
		_bs.set(z);
	}
	/查找操作
	void test()
	{
	/
	}
private:
	static const size_t M = N * 4;
	bitset<M> _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

2.4.2布隆过滤器查找操作

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

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

代码实现：

bool test(const K& key)
{
		
	size_t i = Hash1()(key) % M;
	bool ret = _bs.test(i);
	if (ret == false)
		return false;

	size_t j = Hash2()(key) % M;
	ret = _bs.test(j);
	if (ret == false)
		return false;

	size_t z = Hash3()(key) % M;
	ret = _bs.test(z);
	if (ret == false)
		return false;

	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.4.3 布隆过滤器删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。因为不同的元素映射的位置是可能相同的；
一种支持删除的方法：引用计数
将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。
缺陷：

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

2.5 布隆过滤器优点

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

2.6布隆过滤器缺陷

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

3.海量数据面试题

3.1 哈希切割

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
解析：
利用哈希切分，将100G文件切分为1000份（如下图A0~A999），利用相同的哈希函数将文件中的IP映射到这1000个小文件中，则相同的IP肯定会被映射到同一个小文件，然后利用map<string,int>对每个小文件统计次数，同时记录出现次数最多的IP，利用pair<stirng,int>记录，小文件统计完后，出现最多的IP就得到了。

与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？
如上图，直接利用priority_queue<pair<string,int>,Func>建小堆，TOPK问题，需要自己写一个仿函数Func来控制比较逻辑，次数比堆顶的大，则入堆。

3.2 位图应用

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

解析：利用两个位图，两个位图对应的比特位上的数字组合为次数，例如一个元素在这两个位图上的比特位组合为

   00则代表不存在，01则代表出现1次
   10则代表出现2次，11则代表出现3次
   因为只需要找到出现一次的，所以当出现次数大于3后，则不用改变，
   这样就能统计出不存在，只出现一次，出现两次，出现大于3次的元素；
1
2
3
4

扩展：
假设题目与上面相同，但是限制只有512M的空间大小，设计算法。

解析：
如果是上面的算法，需要用两个512M的位图，一共需要1G的内存。
解法：
只需要开两个256M的位图，第一次读取100亿数据中，数据大小为（ 0~2³¹-1 ）的数据， 第二次读取（2³¹~2³²-1）的数据，分两次完成，这样，无论给再小的内存，都能够完成。（两次读取时用的相同的两个位图，第一次统计完后，就知道那些出现一次，然后再用该位图统计第二次，一共就用两个256M的位图）

题目二： 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
解析：
利用两个位图，将两个文件分别set进两个文件，然后利用位图的查找，如果一个元素在两个位图查找都为真，则是交集中的一个元素；

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

解析：与题目一类似。

3.3 布隆过滤器

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

解析：

近似算法：
利用布隆过滤器，将一个文件的query set进布隆，然后去另一个文件中的query，判断在不在。

精确算法：
如图解：

极端情况下，可能某个文件的相同的元素太多，或则冲突的元素太多，都放到了一个文件中，导致某一个文件太大。
解决方法：
还是和上面的一样，先将小文件的元素放到set里面，因为set可以去重，如果放到set中，超出了所设内存大小，则抛异常（冲突元素过多），需要利用另一个哈希函数再进行哈希切分。

题目二： 如何扩展BloomFilter使得它支持删除元素的操作

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