Bloom Filter 简介

Bloom Filter（中文译作：布隆过滤器）是 1970 年由 Bloom 提出的。它实际上是由一个很长的二进制位数组和一系列 Hash 函数组成。

Bloom Filter 是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter 的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter 不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter 通过极少的错误换取了存储空间的极大节省。

Bloom Filter 算法

创建一个 m 位 BitSet，先将所有位初始化为 0，然后选择 k 个独立的哈希函数。第 i 个哈希函数对字符串 str 哈希的结果记为 hash,,i,,(str)，且 i 的范围是 0 到 m-1 。有关 Bloom Filter 的操作的过程可以参考http://billmill.org/bloomfilter-tutorial/

添加字符串

对于字符串 str，分别计算 hash,,1,,(str)，hash,,2,,(str)…… hash,,k,,(str)。然后将 BitSet 的第 hash,,1,,(str)，hash,,2,,(str)…… hash,,k,,(str)位设为 1。就此，就完成了将字符串 str 映射到 BitSet 中的 k 个二进制位。

查找字符串

下面是检索字符串 str 是否在 BitSet 中：

对于字符串 str，分别计算 hash,,1,,(str)，hash,,2,,(str)…… hash,,k,,(str)。然后检查 BitSet 的第 hash,,1,,(str)，hash,,2,,(str)…… hash,,k,,(str)位是否全为 1。

若一个字符串对应的 bit 位不全为 1，则可以肯定该字符串一定没有被 Bloom Filter 记录过。

但是若一个字符串对应的 Bit 全为 1，实际上是不能 100%的肯定该字符串被 Bloom Filter 记录过的。因为有可能该字符串的所有位都刚好是被其他字符串所对应，这种将该字符串划分错的情况，称为 false positive 。

删除字符串

在基本的 Bloom Filter 中，字符串加入了就被不能删除了，因为删除会影响到其他字符串。实在需要删除字符串的可以使用Counting Bloom Filter(CBF)，这是一种基本 Bloom Filter 的改进，CBF 将基本 Bloom Filter 每一个 Bit 改为一个计数器，这样就可以实现删除字符串的功能了。

Bloom Filter 参数选择

hash 函数选择

hash 函数的选择对性能影响比较大，一个优秀的 hash 函数应该做到将字符串等概率的映射到各个 bit。与此同时，选择 k 个不同的 hash 比较繁琐，一种简单的策略就是采用同一个 hash 函数然后传入 k 不同的参数。下面列举的是一些软件框架中 BloomFilter 所使用的 hash 函数。