STL：位图和布隆过滤器

一，位图

1.1 位图的概念

      究竟什么是位图呢？？我们用一道问题来引入

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

这40亿个数中。【腾讯】

根据这个问题，我们可以用什么方法来解决呢？？？我们可以很迅速地想到一下方法：

方法1：排序+二分查找

方法2：将整数丢进哈希表或者红黑树中

          看似好像都能解决这个问题，但是我们来审视一下这个问题的关键——内存

         1G=1024MB=1024*1024KB=1024*1024*1024Byte 约等于10亿Byte，也就是说40亿个数大约需要16G内存！！没有办法将数据一次性放到内存去处理。

  （1）分析方法1：如果我们将数据分在不同的文件里，我们可以用归并排序去完成文件之间的排序，但是无法使用二分查找法，因为没有办法通过下标去直接访问元素！！！

  （2）分析方法2：问题就是所需要的内存太大了，光是数据就16G了，更何况红黑树和哈希表的底层的封装还需要一定的损耗，我们如果要使用的话也只能是一部分一部分丢进容器，然后再删掉丢下一部分，这样一方面的问题是我们其实在一开始丢进容器的时候就可以去做比对了，没有必要丢到容器里，另一方面的问题就是不适应需要多次查找比对的场景。

      因此上面两种方法都是不太现实的，但是有一种数据结构可以帮助我们解决这个问题，那就是位图——通过哈希函数中的直接定址法确定整型在不在的模型（就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。）

    所以方法3：用位图去解决  

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

       你可能会有这样的疑惑，为什么上面的排布是反着来的，即从7—>1，但其实这样才是符合我们的人为的认知的，比如1234，右边的是低位，左边才是高位。在计算机中具体是怎么排布的我们不得而知，因为那属于内存层，是我们看不到的，我们能看到的只是计算机给我们展现的虚拟层，比如说我们的监视窗口和内存窗口，每个bit位都是左高右低的排布，符合我们人的一个惯性。  而我们的左移运算符 其实就是从低位->高位  而右移运算符 其实是从高位->低位。

 1.2 位图的实现

      首先，我们的STL容器中是有位图这个容器的，名字叫做bitset。

1.2.1 基本结构

template //非类型模板参数   N表示需要开的位图的大小
class bitset
{
public:
private:
	vector _bits;
};

      我们需要去控制比特位，所以选择char作为我们的类型是最合适的，其中N是非类型模板参数，表明位图具体开多大。

1.2.2 构造函数

       我们具体应该开多大，自然是取决于我们的元素数量的，既然我们一个char有8个bit位，自然就可以表示8个整数，但是需要注意的一个原则是：宁可开多不可开少。因为假设是10，除以8之后余数会被干掉，因此我们最后一定还要加上一个1

bitset()
{
	_bits.resize(N / 8 + 1, 0); //只能开多不能开少
}

1.2.3 set

       set的作用，就是将某一位设置成1

void set(size_t x) //设置成1
{
	size_t i = x / 8;//计算x映射的位char在第i个数组的位置
	size_t j = x % 8;//计算x映射的位在这个char的第j个比特位
	//按位或   26)  return false;//鸽巢原理做优化
       //利用位图的思想
       int bitmap=0;
       for(auto ch:astr)
       {
        int i=ch-'a';//找到映射关系
        if((bitmap>>i)&1==1)  return false;//先判断该字符是否出现过 判断第i位是否是1
        //如果没出现过，将第i位的0修改为1
        bitmap|=(111
		else if (_bit1.test(x) == true && _bit2.test(x) == true) _bit2.reset(x);//11->10
		//如果是11 不处理
	}
	void Print() //打印只出现一次或者两次的整数
	{
		for (size_t i = 0; i