位图和布隆过滤器

位图

先看这样一个面试题：

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

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

时间和空间复杂度都过高，实现起来效率太差

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

虽然查找效率还可以，但将数据存起来并进行排序很消耗时间和空间

• 3. 位图解决

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

例如要存储 N 个数据，并判断0~N 中某个数是否存在于给定的数据当中，一共开 N 个比特位数组的空间，遍历需要判断的数据群，0~N 中哪个数 n 存在，就将数组第 n 个下标对应的值置为 1，在查找数据 n 的时候，只需要判断下标 n 位置存储的值是否为 1 即可。

如下图，将这些数据存入位图：

位图的实现

• 1、将数据存入位图

在计算机中，比特是最小的存储单位，而计算机中处理数据的基本单位却是字节，所以需要在以字节为单位的数组中进行定位，找到这个数据对应的比特位在顺序上属于哪一字节，并将这个字节的对应比特位改为1（1字节等于 8 比特，那么一个整形就是 32 比特）

对应比特位的计算方法：找到这个数据属于第几个整形的范畴，一个整形是32个比特位。例如，0就属于第一个int 的范畴，36就属于第二个整形的范畴，64 就属于第二个整形的范畴（0~31 32~63 64~95）以此类推。那么 36 就属于第二个整形的第 5 个比特位，64就属于第三个整形的第 1 个比特位。

假设需要将 x 写入位图（位图的空间开的足够大），那么 x / 32 就能得到 x 属于第几个 int 的范畴，x % 32就能得到 x 是这个 int 的第几个比特位。

再根据上面的计算结果，进行位运算就能将对应位置的比特位变为 1。

• 2、将数据从位图中删除

和前面的方式一样，先计算出对应的 i 和 j，然后进行位运算，将对应位置的比特位变为0

• 3、检测数据是否在位图中

先算出如果这个数据在位图中，它的具体位置，然后进行按位与运算，保证只有那个位置为1，其余位置为0。如果计算结果不为 0 的话，就说明这个在位图中为1，那么这个数据就在位图中！

• 4、测试位图

参数 800 需要传的是需要检测数据中的最大值

回到前面腾讯的面试题，需要在40多亿数字中，检测一个数在不在，那么只需要传参数的时候传 0xffffffff 或者 -1即可，然后需要判断哪一个数在不在，直接判断即可，判断的时间复杂度为O(1)，但要开 40 多亿个比特大小的数据，大概还需要 0.5G 的空间。

• 代码实现

#include<vector>
#include<iostream>
using namespace std;
namespace zyb
{
  template<size_t N>
  class bitset
  {
  public:
    bitset()
    {
      _bs.resize(N / 32 + 1);
    }
    void set(const size_t& x)
    {
      size_t i = x / 32; // 第几个 int
      size_t j = x % 32; // 这个 int 的第几个比特位
      _bs[i] |= (1 << j); // 将这个 int 的第 j 个比特位变为 1
    }
    void reset(const size_t& x)
    {
      size_t i = x / 32; // 第几个 int
      size_t j = x % 32; // 这个 int 的第几个比特位
      _bs[i] &= ~(1 << j); // 将这个 int 的第 j 个比特位变为 0
    }
    bool test(const size_t& x)
    {
      size_t i = x / 32; // 第几个 int
      size_t j = x % 32; // 这个 int 的第几个比特位
      if ((_bs[i] & (1 << j)) != 0) return true;
      return false;
    }
  private:
    vector<int> _bs;
  };
}

布隆过滤器

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

非整形的数据转化为整形，无论利用何种方式，都有可能会发生冲突的情况，发生冲突，在检测时就有可能会发生错误，这时候为了减小这种冲突带来的错误，就需要使用布隆过滤器。

布隆过滤器适用于非整形的数据，用多个哈希函数计算出多个整形值，统统映射到位图中，这样相当于一个数据在位图中就对应多个位置。当检测一个数据是否存在时，利用这几个哈希函数计算出对应于位图中的比特位位置，只有查看这些比特位都为1时，才算是这个数据存在，只要有一个位置不符合，就不存在！

总结：

分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可
能存在，因为有些哈希函数存在一定的误判。比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

有一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。但这个支持删除的方式也有缺陷，无法确认元素是否真正在布隆过滤器中，并且还存在计数回绕的情况。

布隆过滤器优缺点

优点

• 1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
• 2. 哈希函数相互之间没有关系，方便硬件并行运算
• 3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
• 4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
• 5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
• 6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

缺点

• 1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
• 2. 不能获取元素本身
• 3. 一般情况下不能从布隆过滤器中删除元素
• 4. 如果采用计数方式删除，可能会存在计数回绕问题

布隆过滤器代码

它的实现是基于位图的。

struct BKDRHash
  {
    size_t operator()(const string& s)
    {
      // BKDR
      size_t value = 0;
      for (auto ch : s)
      {
        value *= 31;
        value += ch;
      }
      if(value > 0xffffffff) value %= 0xffffffff;
      return value;
    }
  };
  struct APHash
  {
    size_t operator()(const string& s)
    {
      size_t hash = 0;
      for (long i = 0; i < s.size(); i++)
      {
        if ((i & 1) == 0)
        {
          hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
        }
        else
        {
          hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
        }
      }
      if(hash > 0xffffffff) hash %= 0xffffffff;
      return hash;
    }
  };
  struct DJBHash
  {
    size_t operator()(const string& s)
    {
      size_t hash = 5381;
      for (auto ch : s)
      {
        hash += (hash << 5) + ch;
      }
      if (hash > 0xffffffff) hash %= 0xffffffff;
      return hash;
    }
  };
  template<
    size_t N,
    class K= string, 
    class Hash1 = BKDRHash,
    class Hash2 = APHash,
    class Hash3 = DJBHash>
  class bloomfilter
  {
  public:
    void set(const K& key)
    {
      size_t i = BKDRHash()(key);
      size_t j = APHash()(key);
      size_t k = DJBHash()(key);
      _biset.set(i);
      _biset.set(j);
      _biset.set(k);
    }
    bool test(const K& key)
    {
      size_t i = BKDRHash()(key);
      size_t j = APHash()(key);
      size_t k = DJBHash()(key);
      if (_biset.test(i) && _biset.test(j) && _biset.test(k)) return true;
      else return false;
    }
  private:
    bitset<N> _biset;
  };