【C++】哈希的应用 -- 位图

一、位图的概念

我们以一道面试题来引入位图的概念：

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

我们的第一反应可能是将数据进行排序之后进行二分查找，或者将数据放入unordered_map/unordered_set中，然后再进行查找。但是这两种方式看似能够实现，但是实际上是不行的，因为数据量太大了，在内存中存放不下

40亿个整数，每个整数占4个字节，一共160个字节，而1G大约10亿字节，那么我们存储40个整数就大约需要16G，而我们的内存一般只有4个G，如果我们使用排序之后进行二分查找，那么就需要开辟一个16G大小的数组，显然是无法实现的，如果我们使用红黑树或者哈希表的方式，这也是不行的，因为红黑树每个节点需要存放节点的值，三个指针和颜色，每个节点就需要消耗16个字节，而哈希表中每个桶要存放一个指向下一个节点，也有一定的消耗

我们换一个思考的方式，题目中只要判断一个数在不在，并没有其他的要求，所以我们不需要将这些树存储下来，只需要用一个值来对他们进行标记即可，而标记一个数只需要一个比特位即可，如果二进制比特位为1，则表示存在，为0表示不存在

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

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

二、位图的实现

对于位图，一般我们只需要提供一下三个接口即可：

1.set : 用于将某一数值对应的比特位置为1，即进行标记(插入数据)

2.reset：将某一数值对应的比特位置为0，即删除标记(删除数据)

3.test : 用于测试某一数值对应的比特位是否为1，即查找数据

这里我们需要一个非类型模板参数–N是给定的数据的范围，不是数据的个数，因为C++中最小的数据类型是char，占一个字节的空间，一个字节占8个比特位，可以用于标记8个位置。我们可以用一个vector来进行存储数据，所以我们在构造函数中我们将vector resize到N/8+1即可，加1是因为C++中的除法是整除法，即直接舍弃余数，而我们这里应该采取进1法，即需要多开辟一个空间。此外，我们还可以将vector中的数据的类型定义为int，此时我们开辟空间的时候应该resize到N/32+1

对于三个重要接口的实现，我们使用目标值x/8就可以得到x应该被映射到哪一个下标，即在第几个char的位置，x%8就可以得到x应该被映射到该下标的第几个比特位，然后再将对应的位置置为1或0即可

对于set：我们可以使用或等的方法，找到一个数，这个数的第j个比特位(j为在下标中的第几个位置)为1，其他的位置为0，我们使用1向左移动j为即可，然后再进行或等

对于reset:我们可以使用与等的方法，找到一个数，第j为0，其他位为1，我们只需要将1向左移动j位i，然后再进行按位取反即可，然后再进行与等

对于test：我们知道，在逻辑关系中，0为假，非0为真，那么我们就可以将那个位置的数进行与，注意是与，不是与等，与1左移j为，如果那个位置为1，那么都为0，判断为假，如果那个位置不为0，与之后也不为0，此时转换为bool类型，为真，这里会进行整形提升，但是将一个数从0提升到非0或者从非0提升到0，所以符号我们的要求

代码实现如下：

namespace hdp
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bits.resize(N / 8 + 1, 0);
		}

		void set(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			_bits[i] |= (1 << j);
		}

		void reset(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			_bits[i] &= (~(1 << j));
		}

		bool test(size_t x)
		{
			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
36

有了位图之后，我们就可以解决上面的面试题了–由于题目中说明了数据是无符号整数，那么我们就可以将N定义为-1(有符号的-1等于无符号的最大值)，然后我们只需要将这40亿个数据依次进行set，然后进行test即可

无符号的最大值大约为42亿九千万，也就是需要这么多的比特位来进行标记，计算得大约需要5亿字节，即512M，这是可以在内存中存放得下的

三、库中的 bitset

C++提供了类似于位图的东西–位的集合–bitset，它的功能比我们实现的更加的丰富，但是主要功能还是set，reset和test

四、位图的应用

位图主要运用于一下几个方面：

1.快速查找某个数据是否在一个集合中

2.排序 + 去重

3.求两个集合的交集、并集等

4.操作系统中磁盘块标记

我们来看看下面几道位图应用的题目：

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

我们发现，使用传统的位图并不能解决这个问题，因为位图只能表示存在和不存在，只能够表示两种状态，这个问题中，就存在多种状态，但是我们可以将上面的问题分为3种状态–没有出现，出现1次，出现一次以上。那么我们就可以使用两个位图结合在一起，使用两个比特位来进行标识，两个比特位最多可以标识4种状态，我们取3种即可：

00：没有出现

01：出现1次

10：出现1次以上

代码实现如下：

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

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

2.1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

这道题和上面求只出现一次的数字的思路一致，这里我们需要将出现0次，1次，2次，2次以上的状态都表示处出来，使用两个标记位即可

template<size_t N>
class twobitset
{
public:
	void set(size_t x)
	{
		if (!_bs1.test(x) && !_bs2.test(x)) //00
		{
			_bs2.set(x);//01
		}
		else if (!_bs1.test(x) && _bs2.test(x)) //01
		{
			_bs1.set(x);
			_bs2.reset(x); //10
		}
        else if(_bs1.test(x) && !_bs2.test(x)) // 10
        {
            _bs1.set(x);
            _bs2.set(x); //11
        }
	}

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

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

我们可以将第一个文件的数据全部映射到一个位图中，然后再遍历取出第二个位图中的数据进行test即可，返回true的数据即为交集，但是这样就会得到许多重复的数据，所以最终的结果需要进行去重处理。我们也可以使用两个位图分别进行映射，然后进行遍历，两者进行与运算，为1则为交集的数据

五、哈希切割

对于下面这道题目：

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

和前面我们的题目不同，这道题我们不能使用位图来解决，因为我们不知道相同的ip会出现多少次，所以就无法确定使用多少个比特位来进行标记

100G数据太大内存放不下，我们能不能将这个文件平均分为100分大小的文件，这样每个问题都只有一个G的大小，此时再依次插入map中进行统计次数，这样其实也是不行的，因为在统计下一个小的文件时，我们需要将之前的文件的统计结果即map中的数据进行clear，否则就会因为数据过多导致内存不足的情况，这样就不能够很好的统计出IP出现的次数。

我们可以想办法将相同的IP放入同一个小文件中，即我们可以使用哈希切割的方法–先使用字符哈希函数将IP转换为整数，然后再使用除留余数法将100G文件的IP地址划分到不同的小文件中

size_t Ai = HashFunc(IP) % 100;
1

经过哈希切割之后，相同的IP一定会被划分到同一个小文件中，因为相同的字符串经过哈希映射之后一定会得到相同的整数，那么模出来的结果也也一定相同，即会在同一个小文件中，但是不同的IP也可能会被划分到同一个文件中，因为会发生哈希冲突，此时文件的大小就可能会操作一个G，并且划分非结果有两种：

1.子文件中有许多相同的IP地址，此时我们可以直接使用map统计这些IP地址的数量(所有相同的IP地址一定会出现在同一个子文件中)

2.子文件中有许不同的IP地址，大多是不重复的，map统计不下，那么此时我们就需要换一个哈希函数，递归再切分

使用map统计，如果是第一种情况，可以统计出来的，不会报错

如果是第二种情况，map的insert插入失败，那是没有内存，相当于new节点失败，new失败会抛异常

最终出现次数最多的那个IP地址会被全部映射到某一个子文件中，我们对子文件使用map进行统计就可以得到其出现的次数