目录

位图

位图的实现

将x对应比特位0置1

将x对应比特位1置0

查看x位置是0还是1

位图的应用

哈希的补充

首先我们来看一道题，这是一道笔试题。

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

1. 遍历，时间复杂度O(N)

2. 排序(O(NlogN))，利用二分查找: logN

        当用二分查找，比如AVL树，最多要查找高度次。所以log40亿=32，最多要查找32次.它们都很快，但是这里有一个大麻烦，1G=1024*1024*1024byte,那么1G大概是10亿字节，一个整数要4个字节，那么10亿个整数大约要4G，所以40亿个整数要占16G的空间。16G在内存中已经块存不下了。

        并且哈希表和红黑树这种还有附带消耗，比如红黑树的节点中不仅要存key值，还要存三叉链：左孩子、右孩子、父亲指针和颜色，这样就16个字节了（指针都是4个字节在32位下，颜色用的是枚举，也是4个字节）。用哈希表的话，每个节点还要存next指针，也要消耗4个字节。并且还有一个表的消耗，消耗也不小。

3.位图

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

位图

那么如果40亿个值存不下了，就会在磁盘文件当中存储。

40亿个整数，每个值一个比特位，那么就是40亿个比特位，要占0.5G也就是500M。刚才我们已经直到40亿个整数要存16G，一个整数是4字节，一个字节8byte，那么一个整数是32byte，16G/32byte=0.5G=500M。500M对于内存是可以承受的。

但是40亿个整数不能只开40亿个比特位，需要按照整数的范围42亿来开，接近43亿。32位下，一个整数是4字节，4字节是32byte，那么整数的范围大小有2^32，一共42亿个。那么在这个40亿个整数中，有可能存在41亿的数，也有可能存在42亿的数。所以位图开比特位需要按照整数范来开，需要开42亿个比特位。

位图的实现

在C++中我们无法开辟比特位，但是我们可以开数组，开一个char类型的数组，每个数组元素类型是char，一个char是1字节=8byte，如果要开N个字节，那么就要开N/8个char类型的数组。或者也可以开int类型数组，这样每个数组元素存放的元素比特位更大，一个int=4字节=32byte，那么要开辟N个比特位，就要开辟N/32个int类型数组。

所以位图的私有成员变量可以是vector _bits;也可以是vector _bits;我们这里存char来举例。

如果按char存，不管它大端还是小端，它的第一个vector存的是0-7个比特位，第二个vector寸的是8-15个比特位，以此类推。如果是int类型的第一个vector存的是0-31个比特位，一个vector存32byte。

最开始我们要构造初始化这个vector，需要resize开辟空间，在上面我们提到给数组开辟空间，要开N/8个大小的char类型数组。但是这样的话，如果遇到不是8倍数的N，加入N是10，10/8之后结果转化位size_t为1，但是它的空间已经在第二个vector，所以我们只需要在N/8的基础上，多开一个vector的空间即可。

#pragma once
#include 

namespace wjy
{
	template
	class bit_set
	{
	public:
		bit_set()
		{
			_bits.resize(N / 8 + 1, 0);
		}
	private:
		vector _bits;
	};
}

将x对应比特位0置1

首先应该获取x所对应的vector的位置，在第几个vector，这里直接获取i=x/8所得整数，就是x所对应的在vector中第几个char，因为vector的下标是从0开始，比如10，10在是第二个vector，但是在vector中下标是1，10/8获得的整数正好是1。第二步，获取x是这个char中的第几位，我们用到的是模，j=x%8就是在char中的位置，还是一样的，char中的位数下标也是从0开始的。那么我们怎么将x的位置从0置1，且其它位置的数都不变呢？我们可以用或运算符，我们知道了x在char中是第几位，将1左移j位是对应的x的位置，用第i个vector的char来或左移好的数字，因为其它位置获得都是0，0或任何数还是原来的数字，1或原来的数字就是1，就可以将x的比特位由0置1。

为什么是左移？在上面图中我们画的是小端。左边是低位，但是实际在运算中，这个数都是左高右低的，就跟我们平时算数一样。

		void set(size_t x)
		{
			size_t i = x / 8;//第几个vector
			size_t j = x % 8;//x所在的这个char的第几位
			
			_bits[i] |= (1 << j);
		}

将x对应比特位1置0

将1置0和上面的做法是相反的，找位置是相同的，但是在第三步，我们位运算的数字是101这样的形势，这个和上面位运算的数字是相反的，所以我们直接对1左移j位，然后取反，最后将第i个char的8个比特位和这个数字或，因为去翻之后变成了101，或操作会将不用改变的位置也变成1，但是与操作，原来是0还是0，原来是1还是1。

取反我们要用按位取反~。

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

查看x位置是0还是1

找x的位置和上面一样，前两个步骤是一样的。那么想要直到x位置的状态，无非就两种1和0，那么和1左移j位与上之后，如果是1，那么这个位置就存在这个数，如果是0，就不存在，直接让最后得出的结果隐式类型抓换，从size_t转为bool类型。

		bool test(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			return _bits[i] & (1 << j);
		}

测试一下：

所以要解决最开始的那道面试题，用这种位图是比较方便的。那么要开辟42亿个位置的大小，第一种是我们自己用计算器算，1024*1024*1024*4，最后算出得数。第二种方法：可以用默认系统给的宏：UNSIGNED_INT_MAX。第三种方法：还可以用16进制的表示方法，bit_set<0xffffffff> bs;还有人给了一种方法就是开-1个空间，因为最后要转无符号整数，补码最后还会从变成全1。

开了空间之后用任务管理器查看，发现42亿个比特位就是差不多500M，也验证了我们的想法。

 在STL库中也有现成的位图，叫做bitset，为了区分，我们加了一个下划线。

位图的应用

我们再来看几个题

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

因为10亿个整数占4G，那么100亿个整数要占40个G，而整数的范围一共是42亿个，所以在着100G中每个数平均出现两次，并且不免有的数出现10次8次的，也就是说这里严格来说要分成三种状态：出现0次；出现1次；出现两次及以上。

以前的位图是1个比特位表示一个值，这道题我们用两个位图来表示一个数，因为有三种状态，出现依次就是00，出现依次就是01，出现两次及两次以上是10。如果只在一个vector中用两个比特位表示状态，这样的话还要改造上面写好的代码。所以我们使用两个位图，开辟两个vector。

所以在x这个数出现的时候，如果原来的状态是00就变成01，如果原来的状态是01就变成10，如果原来是10就不用变，因为10就代表出现两次及两次以上。

template
class TwoBitSet
{
public:
	void Set(size_t x)
	{
		if (!_bs1.test(x) && !_bs2.test(x))
		{
			_bs2.set(x);//00 -> 01
		}
		else if (!_bs1.test(x) && _bs2.test(x))//01 -> 10
		{
			_bs1.set(x);
			_bs2.reset(x);
		}
	}
private:
	wjy::bit_set _bs1;
	wjy::bit_set _bs2;
};

打印只出现一次的数字

我们直接遍历位图即可。找到01的位图，就打印出来

	void PrintOnceNum()
	{
		for (size_t i = 0; i < N; i++)
		{
			if (!_bs1.test(i) && _bs2.test(i))
			{
				cout << i << endl;
			}
		}
	}

 测试

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

第一个思路：让一个文件的整数放到一个位图中，另一个位图遍历到这个位图中找对应的数字是不是1，就找到交集。我们不必担心100亿个数1个G存不下，因为整数一共2^32=42亿,一共需要500M，所以所有的整数存下是完全够的。

但是这种方法有一个缺陷：交集会把重复值找出来，多次出现。如int a1[]={5,30,1,99,10};int a2[]={8,10,11,9,30,10,30},这样的话找交集会找成10，30，10，30,最后的结果还要想办法去重。

第二个思路：读取一个文件设置到一个位图bs1，另一个文件中的整数设置set到位图bs2中，然后遍历bs2，看bs2中的数据在不在bs1中。或者将bs1中的值依次跟bs2中的值与一下，再去看与完是1的位置就是交集。

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

和第一道题差不多，但是这里需要找出现不超过两次的整数，所以需要分四种情况：

1. 出现0次     00->01
2. 出现1次     01->10
3. 出现2次     10->11
4. 出现3次及3次以上    11--不变，出现3次就不用考虑了

所以要找出现次数的数字，需要找2，3种情况，出现0次的不能找。

那么不超过5次的所有整数需要几个位图？需要3个位图，一个值用3个比特位统计次数，用3个位图即可。一个位图500M，3个位图1.5G。所以这种位图存储比起哈希表最大的优势是节省空间。

哈希的补充

哈希表也需要扩容，哈希表在闭散列的时候（线性探测/二次探测）,如果负载因子超过0.7就要扩容，开散列的时候（哈希桶方法），负载因子超过1的时候就要扩容。

而有的专家给出扩容的最佳大小，每次扩容都扩到素数大小，哈希表的大小用素数是最好。素数：只能被1和自己整除。

在stl源码种我们可以看到，它会给一个素数表，素数表的数都是固定的，差不多也是2倍增长，如果是正好按2倍增长，不会是素数的。所以我们可以写一个获取素数的函数，当扩容的时候，遍历这个素数表，找到比当前哈希表大小还大的数字，就返回这个素数。当然整数的个数是有限的，当遍历整个素数表，都没有找到比传过来的num值大的素数，说明已经超过素数表的范围，直接返回最后一个素数42亿就好。但是理论上走不到最大值。

这里素数相当于把它写死了。如果还要变得大一些，那么这个素数表的类型不是unsigned long，而是unsigned longlong。

		size_t GetNextPrime(size_t num)//改变的是下标的值，所以返回整数
		{
			static const unsigned long __stl_prime_list[28] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};
			for (size_t i = 0; i < 28; ++i)
			{
				if (__stl_prime_list[i]>num)
				{
					return __stl_prime_list[i];
				}
			}
			return __stl_prime_list[27];
		}

当哈希表的大小是42亿，扩容之后还是42亿，说明两个数相等，相等的时候就直接跳出循环。当表的大小不是42亿，那么在扩容之后，会扩大到比表的大小还大的一个数字，这时候表还是旧表的大小，可以和newSize做比较。

		pair Insert(const T& data)
		{
			KeyOfT kot;
			iterator ret = Find(kot(data));
			if(ret!=end())//不等于end表示找到了
				return make_pair(ret,false);//返回迭代器和false的键值对，ret本身就是一个迭代器

			HashFunc hf;
			//负载因子为1的时候扩容，最好的情况是数组每个值都能挂一个桶
			if (_tables.size() == 0 || _n == _tables.size())
			{
				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				size_t newSize = GetNextPrime(_tables.size());
				if (newSize > _tables.size())
				{
					//表的大小是最大数，扩容还是扩到最大数，就跳出循环，不能扩容了
					vector newTable;
					newTable.resize(newSize);
					HashFunc hf;
					for (size_t i = 0; i < _tables.size(); ++i)
					{
						Node* cur = _tables[i];//用一个cur来遍历桶
						while (cur)
						{
							Node* next = cur->_next;//保存cur的下一个节点，不然cur连接到新表找不到下一个值了

							size_t index = hf(kot(cur->_data)) % newTable.size();
							cur->_next = newTable[index];
							newTable[index] = cur;
							cur = next;
						}
						_tables[i] = nullptr;
					}
					_tables.swap(newTable);
				}
				
			}