从位图到布隆过滤器

从一道面试题引出位图

先来看一个经典的。假设当我们需要在1千万个整数（整数的范围在1到1亿之间）里面快速查找某个整数是否存在于其中的话，如何快速查找进行判断会比较方便呢？

当然，这个问题最容易想到的就是用散列表来解决。不过，我们可以使用一种比较“特殊”的散列表，那就是位图（BitMap）。

我们申请一个大小为1亿、数据类型为布尔类型（true 或者 false）的数组。我们将这1千万个整数作为数组下标，将对应的数组值设置成true。比如，整数5对应下标为5的数组值设置为true，也就是array[5]=true。当我们查询某个整数K是否在这1千万个整数中的时候，我们只需要将对应的数组值array[K]取出来，看是否等于true。如果等于true，那说明1千万整数中包含这个整数K；相反，就表示不包含这个整数K。

不过，很多语言中提供的布尔类型，大小是1个字节的，并不能节省太多内存空间。实际上，表示true和false两个值，我们只需要用一个二进制位（bit）就可以了。那如何通过编程语言，来表示一个二进制位呢？

这里就要用到位运算了。我们可以借助编程语言中提供的数据类型，比如 int、long、char等类型，通过位运算，用其中的某个位表示某个数字。

// Java中char类型占16bit，也即是2个字节，可以表示16个数字
public class BitMap {
     
  private char[] bytes;
  private int nbits;
  
  public BitMap(int nbits) {
    
    this.nbits = nbits;
    this.bytes = new char[nbits/16+1];
  }

  public void set(int k) {
    
    if (k > nbits) return;
    int byteIndex = k / 16;
    int bitIndex = k % 16;
    bytes[byteIndex] |= (1 << bitIndex);
  }

  public boolean get(int k) {
    
    if (k > nbits) return false;
    int byteIndex = k / 16;
    int bitIndex = k % 16;
    return (bytes[byteIndex] & (1 << bitIndex)) != 0;
  }
}

位图通过数组下标来定位数据，所以，访问效率非常高。而且，每个数字用一个二进制位来表示，在数字范围不大的情况下，所需要的内存空间非常节省。

比如上面那道面试题，如果用散列表存储这1千万的数据，数据是32位的整型数，也就是需要4个字节的存储空间，那总共至少需要40MB的存储空间。如果用位图的话，数字范围在1到1亿之间，只需要1亿个二进制位，也就是12MB左右的存储空间就够了。

布隆过滤器

关于位图是不是挺简单的？不过，如果我们修改一下那道题，数字范围不是1到1亿，而是1到10亿，那位图的大小就是10亿个二进制位，也就是需要120MB的大小，消耗的内存空间，不降反增。

这个时候，布隆过滤器就要出场了。布隆过滤器就是为了解决刚刚这个问题，对位图这种数据结构的一种改进。

数据个数是1千万，数据的范围是1到10亿。布隆过滤器的做法是，我们仍然使用一个1亿个二进制大小的位图，然后通过哈希函数，对数字进行处理，让它落在这1到1亿范围内。比如我们把哈希函数设计成 f(x)=x%n。其中，x表示数字，n表示位图的大小（此处为1亿），也就是，对数字跟位图的大小进行取模求余。

不过，哈希函数会存在冲突的问题，10000001和1两个数字，经过取模求余的哈希函数处理之后，最后的结果都是1。这样就无法区分，位图存储的是1还是10000001了。

为了降低这种冲突概率，可以设计一个复杂点、随机点的哈希函数。布隆过滤器的处理思路是：既然一个哈希函数可能会存在冲突，那用多个哈希函数共同来定位一个数据，一个哈希函数可能冲突，多个全部冲突的可能性就极低了。

我们使用K个哈希函数，对同一个数字进行求哈希值，那会得到K个不同的哈希值，我们分别记作X₁​、X₂​、X₃​、…、X_K。我们把这K个数字作为位图中的下标，将对应的 BitMap[X₁​]，BitMap[X₂​​]，BitMap[X₃​​]，…，BitMap[X_K​​]都设置成true，也就是说，我们用K个二进制位，来表示一个数字的存在，1千万个数据，就需要K千万个二进制位。

当我们要查询某个数字是否存在的时候，我们用同样的K个哈希函数，对这个数字求哈希值，分别得到Y₁​、Y₂​、Y₃​、…、Y_K​。我们看这K个哈希值，对应位图中的数值是否都为true，如果都是true，则说明，这个数字可能存在，如果有其中任意一个不为true，那就说明这个数字一定不存在。

对于两个不同的数字来说，经过一个哈希函数处理之后，可能会产生相同的哈希值。但是经过K个哈希函数处理之后，K个哈希值都相同的概率就非常低了。尽管采用K个哈希函数之后，两个数字哈希冲突的概率降低了，但是，这种处理方式又带来了新的问题，那就是容易误判。

布隆过滤器的误判有一个特点，那就是，它只会对存在的情况有误判。如果某个数字经过布隆过滤器判断不存在，那说明这个数字就一定不存在，不会发生误判；如果某个数字经过布隆过滤器判断存在，这个时候才会有可能误判，有可能并不存在。不过，只要我们调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，那就可以将这种误判的概率降到非常低。

位图、布隆过滤器应用如此广泛，很多编程语言都已经实现了。比如Java 中的BitSet 类就是一个位图，Redis也提供了BitMap位图类，Google的Guava工具包提供了BloomFilter布隆过滤器的实现。