2.3　布隆过滤器

布隆过滤器（Bloom Filter）是由一个固定大小的二进制向量或者位图（Bitmap）和一系列映射函数组成的。在初始状态时，对于长度为m的位数组，它的所有位都被置为0，如图2-1所示。

图2-1　布隆过滤器初始状态图

当有变量被加入集合时，通过k个映射函数将这个变量映射成位图中的k个点，把它们置为1。图2-2以两个数据通过3个映射函数进行映射为例展示了布隆过滤器经映射后的状态。查询某个数据的时候，只要看这些点是不是都是1就可以大概率知道集合中是否包含该数据了：如果这些点中有任何一个是0，被查询变量一定不在；如果都是1，被查询变量很可能存在。为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数会有碰撞。

图2-2　布隆函数映射示意图

可以看出，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入、查询时间都是常数；散列函数相互之间没有关系，方便并行实现；且布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。