一、位图

1.位图概念

今天的内容从一道面试题开始引入：

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

这40亿个数中。

首先我们对40亿个无符号整数改变一下，它到底是多少G呢？

40亿个整数大概是  40亿*4个字节=160亿个字节

4G=2^32byte，大概为42亿九千万字节，所以1G大概就是10亿字节 ，所以40亿个整数大概就是16G，那这么大数据放到内存中肯定是放不下的，所以什么二分查找，什么map，set更何况还有额外的消耗，这更不可能完成了，于是我们可以利用哈希的思想来搞一个位图！

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

代表不存在。

位图是一种直接定址法的哈希，因此效率很高，用O(1)就可以探测到对应位是0还是1，效率非常高，因此可以快速判断。

利用每一个比特位的0或1的情况，来判断数在不在，所以40亿不重复的数，开辟2^32-1个比特位，转化为G，也就512m，内存很小。

举例说明：

每个数我们可以先num/8，算出他在第几个char里，然后再num%8算出在哪一位

比如：23/8=2，在第二个char；23%8=7，在第七位上面。

那如何把任意一位置1，且不改变其他位？

把它和左移（向高位移动）以后的1（即其他位是0，只有要改变那一位是1）和原来的数进行或运算，就可以得到结果。保证了其他位不变，只有该位被改变为了1.

那到底怎么移动呢？

（一个char中）

那可能有人就会想，这会不会跟大小端有关系，数据在内存中的存储形式？？？

错错错，大错特错，首先大小端只存在于大于1字节的数据类型中，其次不管从哪边移动，本质是向高位或者低位移动。

所以说，%8以后，是哪一位，1直接左移几位（即向高位移动）。

那么在把某一位置为1以后，要重新置为0的话，应该怎么搞呢？

同理得：直接将1移位以后，再取反，将结果和原数进行与运算。

那要测试这个数在不在位图中，怎么测试呢？也就是看某一位是不是1

直接返回  1移位以后和原数相与的结果，不为0则存在，为0则不存在。

我们来看代码实现：

template<size_t N>
  class bitset
  {
  public:
    bitset()
    {
      //_bit.resize((N/8) + 1, 0);
      _bit.resize((N >> 3) + 1, 0);//左移3位就相当于/8，效率更快一些，但要注意运算符的优先级
    }
    void set(size_t x)
    {
      size_t i = x >> 3;
      size_t j = x % 8;
      _bit[i] |= (1 << j);//在知道是哪一个char之后，直接把这一个char相与。
    }
    void reset(size_t x)
    {
      size_t i = x >> 3;
      size_t j = x % 8;
      _bit[i] &= (~(1 << j));
    }
    bool test(size_t x)
    {
      size_t i = x >> 3;
      size_t j = x % 8;
      return _bit[i] & (1 << j);
    }
  private:
    vector<char> _bit;
  };

2.位图的应用

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

统计次数的话，那么就需要两个位图来实现，两个比特位来统计00（0次），01（1次），10（2次及以上）。

直接上代码：

template<size_t n>
  class two_bitset
  {
  public:
    void set(size_t x)
    {
      if (!_bs1.test(x) && !_bs2.test(x))//00
      {
        _bs2.set(x); //0次变1次
      }
      else if (!_bs1.test(x) && _bs2.test(x))//01
      {
        _bs1.set(x);
        _bs2.reset(x);//1次变两次
      }
    }
    void printonce()
    {
      for (size_t i = 0; i < n; ++i)
      {
        if (!_bs1.test(i) && _bs2.test(i))
        {
          cout << i << endl;
        }
      }
      cout << endl;
    }
  private:
    bitset<n> _bs1;
    bitset<n> _bs2;
  };

一个数如果在两个位图中的同一位置都是0，那么说明就是0次 ，再进来的数就要将00第二位set为01，表示出现一次，后面同理可得。

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

首先我们知道，整数的范围最大是42亿多，所以100亿个整数中，一定存在许多重复的整数。

所以将文件中的数据都放入位图中，只看 存在或者不存在两种状态，这就自动去掉了重复的数，某一位一直是1。只有512MB，可以存入内存中进行处理。

然后两个位图进行相与操作，同时为1说明是交集。

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

数

首先我们知道，整数的范围最大是42亿多，所以100亿个整数中，一定存在许多重复的整数。

所以将文件中的数据都放入位图中，只看 存在或者不存在两种状态，占用内存很少。

通过两个位图来表示次数，00（0次），01（1次），10（2次），11（3次及以上），然后控制条件（只找01，10）输出结果，和第一个问题其实是一样的。

二、哈希切分

还是一道面试题来引入哈希切分：

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

由前面所学，我们可能会想到位图，但是行不通，要统计次数就要开辟多个位图，

成倍的开辟位图来表示次数的话，会占用大量的内存空间，内存也存不下。

我们用的是map，但是在用map之前，要把大文件处理：

那我们就可以利用哈希的思想来把100G的文件分成100个小文件，每个1G，那么不就可以进内存了吗？

那怎么分？？？平均分？那当然不行，平均分对于分散的ip地址，都不在同一个小文件中，进入内存用map统计时，结果是不正确的。

直接哈希切分！！

我们可以对100G大文件中的ip进行哈希切分，利用哈希表的思想，将哈希值相同的放入同一个小文件中，然后通过一个一个的小文件进入内存读取并统计个数，搞完一个clear掉，记录再进下一个。

理想很美好，现实却有点骨感？

单个文件超过1G:

因为存在哈希冲突，在数据进入小文件时，就会产生下面两种情况：

       1.一个小文件中，差不多都是不重复的数据，且个数还挺多，且map再加额外开销，导致内存很大，直接报错。

       2.一个小文件中，都是很多重复的数据，且个数还挺多，但是map却可以存下（重复的只增加次数），可以统计。

所以我们无需判断是哪种情况，直接无脑map，第一种情况发生就抛异常，捕获以后，换另一种哈希函数，再进行递归分割，拆成更小的文件后用map统计次数。与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

利用堆来解决topK问题。

三、布隆过滤器

1.布隆过滤器的概念

开始讲布隆过滤器之前，我们要说一说位图的缺点是什么？