哈希应用之位图及其实现

位图

鹅厂有这样一道题，给四十亿个不重复无符号整数，无序，如何判断一个数是否在这四十亿个数中出现过

直接遍历的话，时间复杂度是N的；排序加二分是NlogN的，哈希的话会好很多，是常数级的

但是需要考虑一个问题，就是说四十亿个值内存里能不能开出来，大概算一下需要16G左右的内存，因此直接开哈希表也是不现实的

实际上要解决在不在这个问题，不需要存下来这么多数据，只需要使用整数通过哈希函数计算出对应的位置，用0表示不在，用1表示在，这样就能节省大量空间

这里四十亿个数据只需要0.5G左右即可

那其实可以拓展来讲，在不在是两种状态，也可以使用两个bit位表示四种状态，以此类推，在后面我们会尝试实现

模拟实现

在C++标准库里面也有bitset可以直接使用，而且功能也算是比较丰富的，我们主要模拟实现三个函数，一个是set置一，一个属reset置零，一个是test查询

我们用什么来承载这些个bit呢，考虑使用int，32位机器下，一个int是4个字节，刚好可以承载32个比特

如果我们想开N个bit的大小，那么至少需要N/32+1个int

这样我们就可以搭一个基本的框架了

	template<size_t N>
	class bitset {
	public:
		bitset() {
			_bits.resize(N/32+1);
		}

		void set(size_t x) {}

		void reset(size_t x) {}

		bool test(size_t x) {}
	private:
		vector<int> _bits;
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

然后这里我们考虑如何将一个位置置0，置1或者是查询

首先这里是关于位的问题，那么就考虑使用位运算

一个位置是x的位置想要置1的话，就说明不管原来是什么，置1之后结果一定是一，符合这个条件的位运算就是给这一位按位或1，那么同理的，后面分别就是按位与0，按位与1

第二个问题是，我们如何找到参与运算的bit位呢

其实只需要找到他在对应的哪个int，和int的第几个bit就行

假设是x，那么x/32，就是对应的第几个int，这里对应的是下标，就是从0开始的，x%32对应的是int的第几个位置了

接下来我们实现一下

#pragma once
namespace xu {
	template<size_t N>
	class bitset {
	public:
		bitset() {
			_bits.resize(N/32+1);
		}

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

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

		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

四状态位图

我们讲四状态位图其实就是两位，分别是00，01，10，11，可以分别对应四种状态，当然想对应三种状态也是可以的

这里的实现有两种思路，一种思路是只用一个普通位图，然后用两位来表示状态，这种思路比较好想，但是需要自己写还是比较麻烦的

第二种思路是使用两个普通位图，第一个位图来表示第一位，第二个位图来表示第二位，这样每次判断的时候虽然要将两个位图结合起来用，但是好在有我们刚刚实现的，也可以直接用库里面的

模拟实现

	template<size_t N>
	class towbitset {
	public:
		void set(size_t x) {
			if (_bs1.test(x) == false && _bs2.test(x) == false) // 00
				_bs2.set(x);
			else if (_bs1.test(x) == false && _bs2.test(x) == true) // 01
				_bs1.set(x), _bs2.reset(x);
			else if (_bs1.test(x) == true && _bs2.test(x) == false) // 10
				_bs1.set(x),_be2.set(x);
		}
	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15