简介

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合。它的优点是空间效率和查询时间都比一般的算法要好得多，缺点是有一定的误识别率和删除困难。

基本概念

如果想要判断一个元素是否在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。数组、链表、树等数据结构都是这种思路，它们的时间复杂度为（O(n)、O(logn)）。散列表是一个能够提供更快查询速度的数据结构（时间复杂度为O(1)）。但是随着集合中元素的增加，我们需要的存储空间越来越大，特别是随着大数据的发展，我们越来越不可能将所有的数据都先加载到内存中再进行查找。
这时，我们就可以借助一种新的数据结构，也就是本文的主题：布隆过滤器（Bloom Filter）。
我们使用一段长度为m的二进制位数组，再使用k个哈希函数，将一个值进行k次哈希，得到k个索引，并将对应的位置设置为1。

An example of a Bloom filter, representing the set {x, y, z}. The colored arrows show the positions in the bit array that each set element is mapped to. The element w is not in the set {x, y, z}, because it hashes to one bit-array position containing 0. For this figure, m = 18 and k = 3.

布隆过滤器主要提供两种方法：Add和Test。
Add：通过哈希函数计算，得到k个索引，并将其对应的二进制位设置为1。
Test：通过哈希函数计算，得到k个索引，判断如果任意位置上的二进制都为0，则表示该值一定不在集合中；但是如果所有位置上的二进制都为1，却并不能表示该值一定在集合中，这被称为假阳性，或是判断错误。
可以通过增大数组的长度m，以及增加哈希函数的数量k来降低假阳性的概率。

时间和空间复杂度

时间复杂度
由于需要计算k次的哈希，需要的时间复杂度为O(k)，而计算出对应的索引后，可以进行直接地址访问，需要的时间复杂度为O(1)，所以总的时间复杂度为O(k)。

空间复杂度
由于需要长度为m的二进制数据，所以空间复杂度为O(m)，但是由于数据的基本单位是位，假设为了处理100万条数据，为了降低假阳性的概率，我们使用长度为1000万的二进制数组，所需的内存空间为10,000,000/8/1024/1024=1.2M内存空间。

优点、缺点

优点

• 查询快
• 空间占用少

缺点

• 有一定的假阳性的概率
• 有一定的删除困难
  从上图可见，如果我们想要从数组中删除y，由于z也同时指向了y指向的第二位，所以如果将该位置为空了，则影响到了z。所以是不能直接从该数据中删除的。为了解决这个问题，出现了一些布隆过滤器的变种。

应用场景

• 大名鼎鼎的比特币
  在比特币网络中，存在一些轻节点，这些轻节点并不保存所有的区块和交易，而只是保存自己感兴趣的交易。当轻节点向全节点同步数据时，它发送的不是所有的交易列表，因为这可能会有成千上万条，甚至更多。取而代之，它发送的是通过该交易列表所计算出的一个布隆过滤器。全节点通过计算本地的区块，找到匹配的交易并发送给轻节点。
• Apache的HBase
  在HBase中，一个HFile一旦被写完就再也不会被更新，只会被查询。这时就将这个文件的所有key进行计算，得到它们的布隆过滤器，并将其写入到元数据中，以后所有对该文件的查询都会先查询对应的布隆过滤器，如果在布隆过滤器中不存在则不需要访问该文件，节省了大量的对磁盘的低速访问。
• Apache的Cassandra
  Cassandra最早是由Facebook开发，后来捐献给Apache基金会的一个高性能数据库。而支撑它高性能的一个设计是它采用了追加而不是修改的方式来处理数据文件。一块完整的数据被dump到文件后就不会再被更新。而为了提高查询一个key是否在某个文件中的效率，在每个文件被dump到硬盘上时，都会对该文件生成一个布隆过滤器，而该布隆过滤器会被存放到内存中。以后所有对该文件的访问都会先访问对应的布隆过滤器，如果布隆过滤器返回不存在，则无需再访问硬盘上的文件。这样就大大提高了查询的效率。
• 其它应用场景
  由于内存和硬盘、网络之间访问的时间存在数量级的差距，为了弥补这种差距，我们通常使用缓存。但是随着数据越来越大，内存已经不能承受将所有的数据存放到内存的压力。在这种情况下就可以使用布隆过滤器，进一步降低内存的压力，提高查询的效率。