哈希扩展 --- 位图

位图相关⾯试题

给40亿个不重复的⽆符号整数，没排过序。给⼀个⽆符号整数，如何快速判断⼀个数是否在这40亿个数中。（本题为腾讯/百度等公司出过的⼀个⾯试题）

• 解题思路1：暴⼒遍历，时间复杂度O(N)，太慢
• 解题思路2：排序+⼆分查找。时间复杂度消耗 O(N*logN) + O(logN)

深⼊分析：解题思路2是否可⾏，但是真正的问题是空间！

我们先算算40亿个数据⼤概需要多少内存。

1G = 1024MB = 1024*1024KB = 1024*1024*1024Byte 约等于10亿多Byte！

那么40亿个整数约等于16G，说明40亿个数是⽆法直接放到内存中的，只能放到硬盘⽂件中。⽽⼆分查找只能对内存数组中的有序数据进⾏查找。（对于哈希表这些就更不够了！）

• 解题思路3：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使⽤⼀个⼆进制⽐特位来代表数据是否存在的信息，如果⼆进制⽐特位为1，代表存在，为0代表不存在。那么我们设计⼀个⽤位表⽰数据是否存在的数据结构，这个数据结构就叫位图。

位图的设计

我们并不一定要将这些整数都存下来，我们只需要标记一个值在或不在，用最小的单位去存储在或不在，那么这个单位就是一个比特位了！ 

位图本质是⼀个直接定址法的哈希表，每个整型值映射⼀个bit位，位图提供控制这个bit的相关接⼝。

• 2³² 个比特位 = 4,294,967,296 bit
• 1 Byte = 8 bit

因此内存占用 = 2³² ÷ 8 = 2²⁹ Byte = 512 MB

在 C/C++ 里并没有“位”这一原生类型，只能用 int、char 之类的整型再配合位运算来模拟。
把数据放进 vector<int> 时，一个 int 被当作 32 个开关：第 0 个 int 负责 0‥31，第 1 个 int 负责 32‥63，依次排开。

给定一个整数 x，先算它在哪个 int——i = x / 32，再算它在 int 里的哪一位——j = x % 32，于是 x 就被映射到第 i 个整数的第 j 位。

用这套办法解决“40 亿个互不重复的无符号整数里有没有某个值”时，位图要覆盖 0 到 2³²-1 整个范围，因此真正需要开的是 2³² 个位，而不是 40 亿个位。把文件中的整数逐个读出来、按上述规则把对应位置 1，之后就能在常数时间内回答“某个数在不在”的查询了。

位图主要有三个核心接口：

set   : 将x映射的位标记成1

reset : 将x映射的位标记为0

test  : 检测
{
        x映射的位是1返回真
        x映射的位是0返回假
}

我们可以轻松的通过除模运算得到x的映射的位置，我们除得到的肯定是正确的，但是由于大小端的问题，整数存储就会根据大小端来：

左低右高：大端

左高右低：小端（低位存低位）（反向的）

比较符合当前我们机器的是左高右低的模式，也就是小端是当前机器的绝对主流！

对于set设置，我们就可以进行将1左移j位进行" |= "，就可以将指定位置设置为1！那么对于左低右高呢？是不是就是右移j位呢？不是的！左移不是方向，而是低位往高位移动，所以，我们没必要因为大小端去搞复杂了，左移就对了！！！

位图的实现

#pragma once
#include<vector>

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

		// x映射的位标记成1
		void set(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

			_bs[i] |= (1 << j);
		}

		// x映射的位标记成0
		void reset(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

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

		// x映射的位是1返回真
		// x映射的位是0返回假
		bool test(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

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

	private:
		std::vector<int> _bs;
	};

C++库中的位图

C++ 标准库已经备好了一个现成的位图——std::bitset<N>。核心动作依旧是 set、reset、test；额外附送的 to_string 能把整块位图变成 01 字符串，operator[] 则让你像用数组一样随手拨动某一位。

位图的好处是增删查改都只要一次位运算，空间也压到极限；坏处是它只肯收整数。

典型考题：

100 亿个整数里找出只出现一次的整数：仍是开 2³² 位，只是每一位的含义从“在/不在”换成“出现一次/多次”。因为还是整数嘛！肯定是很多重复的了！

 思想：上面之前位图，是一个位来标识，标识的是在或者不在；我们现在可以是用两个比特位来进行标识：

00: 不在
01: 在且仅有一个
10: 在且是两个及以上

所以我们只需要设计一个两个位的位图就可以解决该问题了！但是没有必要说要重新设计一个两个比特位的位图，我们可以上面的位图，我们通过两个位图的组合就可以实现了！复用前面的位图就可以了！

两个文件各 100 亿整数，1 G 内存找交集：把两个文件分别读进两张位图，然后同步扫一遍，两张图同时为 1 的位置就是交集中的数。

100 亿整数、1 G 内存，求出现次数不超过 2 次的：给每个整数配 2 位——00 表示 0 次，01 表示 1 次，10 表示 2 次，11 表示更多。最后把所有 01 和 10 的地址列出来即可。

这个问题无非就是上面的第一个问题了！只不过更加细分了而已：

00 0次
01 1次
10 2次
11 3次及以上

结合第一个问题，我们写一个更加通用的：

#pragma once
#include<vector>

namespace bit
{
	template<size_t N>
	class twobitset
	{
	public:
		void set(size_t x)
		{
			bool bit1 = _bs1.test(x);
			bool bit2 = _bs2.test(x);

			if (!bit1 && !bit2) // 00->01
			{
				_bs2.set(x);
			}
			else if (!bit1 && bit2) // 01->10
			{
				_bs1.set(x);
				_bs2.reset(x);
			}
			else if (bit1 && !bit2) // 10->11
			{
				_bs1.set(x);
				_bs2.set(x);
			}
		}

		// 返回0 出现0次数
		// 返回1 出现1次数
		// 返回2 出现2次数
		// 返回3 出现2次及以上
		int get_count(size_t x)
		{
			bool bit1 = _bs1.test(x);
			bool bit2 = _bs2.test(x);

			if (!bit1 && !bit2)
			{
				return 0;
			}
			else if (!bit1 && bit2)
			{
				return 1;
			}
			else if (bit1 && !bit2)
			{
				return 2;
			}
			else
			{
				return 3;
			}
		}

	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};
};

void test_twobitset()
{
	bit::twobitset<100> tbs;
	int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9 };
	for (auto e : a)
	{
		tbs.set(e);
	}

	for (size_t i = 0; i < 100; ++i)
	{
		//cout << i << "->" << tbs.get_count(i) << endl;
		if (tbs.get_count(i) == 1 || tbs.get_count(i) == 2)
		{
			cout << i << endl;
		}
	}
}

void test_bitset1()
{
	int a1[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };
	int a2[] = { 5,3,5,99,6,99,33,66 };

	bitset<100> bs1;
	bitset<100> bs2;

	for (auto e : a1)
	{
		bs1.set(e);
	}

	for (auto e : a2)
	{
		bs2.set(e);
	}

	for (size_t i = 0; i < 100; i++)
	{
		if (bs1.test(i) && bs2.test(i))
		{
			cout << i << endl;
		}
	}
}