English

Bloom Filters by Example

Bloom filter 是一个数据结构，它可以用来判断某个元素是否在集合内，具有运行快速，内存占用小的特点。

而高效插入和查询的代价就是，Bloom Filter 是一个基于概率的数据结构：它只能告诉我们一个元素绝对不在集合内或可能在集合内

Bloom filter 的基础数据结构是一个 比特向量。下面是一个简单的示例：

表中的每一个空格表示一个比特, 空格下面的数字表示它的索引。只需要简单的对输入进行多次哈希操作，并把对应于其结果的比特置为1，就可以向 Bloom filter 添加一个元素。

相较于解释，直观的看到它的变化总是更利于我们加深理解的，所以你可以输入一些字符串然后观察上方的向量变化。其中使用了 Fnv 和 Murmur 这两个简单的哈希函数：

输入一个字符串:

fnv:
murmur:

你的集合: []

当你往集合里添加一个字符串的时候, 你可以检查应用对应哈希函数的位置是否为1。这里我用了绿色表示最新添加的元素对应位置，但是实际上你要知道，表格里的不同颜色都只代表了值为 1。

你可以简单的通过对字符串应用同样的哈希函数，然后看比特向量里对应的位置是否为1的方式来判断一个元素是否在集合里。如果是，你只知道元素可能在里面, 因为这些对应位置有可能恰巧是由其他元素或者其他元素的组合所引起的。

测试:

fnv:
murmur:

这个元素在集合中吗？否

误判的概率: 0%

这些就是 Bloom filter 全部的基础内容了。

高级话题

在写下更多关于 Bloom filter 的内容之前，我需要声明一点：我从未在生产环境使用过 Bloom filter。所以不要不假思索的相信下面的内容，我想做的只是给你一个概括式的介绍，同时告诉你可以去哪里寻找更多内容。

在下面的内容里, 我们假设在 Bloom filter 里面有 k 个哈希函数, m 个比特, 以及 n 个已插入元素。

Bloom filter 里的哈希函数需要是彼此独立且均匀分布。同时，它们也需要尽可能的快 (尽管 sha1 之类的加密哈希算法被广泛应用，但是在这一点上考虑并不是一个很好的选择).

这些都是快速，简单且彼此独立的哈希函数的例子：³ 包括 murmur, fnv 族哈希函数, 以及HashMix.

如果你希望了解一个比加密哈希函数快的哈希函数可以达到什么程度，可以参考这个故事。当把 bloom filter 的实现从 md5 切换到 murmur 时，速度提升了 800%。

一个关于 Bloom filter 实现方式的简单调查:

Bloom filter 的一个优良特性就是可以修改过滤器的错误率。一个大的过滤器会拥有比一个小的过滤器更低的错误率。

错误率会近似于 (1-e^-kn/m)^k, 所以你只需要先确定可能插入的数据集的容量大小 n, 然后再调整 k 和 m 来为你的应用配置过滤器。²

而这带来了一个显而易见的问题:

Bloom filter 使用的哈希函数越多运行速度就会越慢。但是如果哈希函数过少，又会遇到误判率高的问题。所以这个问题上需要认真考虑。

在创建一个 Bloom filter 的时候需要确定 k 的值，也就是说你需要提前圈定 n 的变动范围。而一旦你这样做了，你依然需要确定 m（总比特数）和 k (哈希函数的个数）的值。

似乎这是一个十分困难的优化问题，但幸运的是，对于给定的 m 和 n ，有一个函数可以帮我们确定最优的 k 值: (m/n)ln(2) ^{2, 3}

所以可以通过以下的步骤来确定 Bloom filter 的大小:

对于一个 m 和 k 值确定的 Bloom filter，插入和测试操作的时间复杂度都是 O(k)。这意味着每次你想要插入一个元素或者查询一个元素是否在集合中，只需要使用 k 个哈希函数对这个元素求值，然后将对应的比特位标记或者检查对应的比特位。

相比之下，Bloom filter 的空间复杂度更难以概述，它取决于你可以忍受的错误率。同时也取决于输入元素的范围，如果这个范围是有限的，那么一个确定的比特向量就可以很好的解决问题。如果你甚至不能很好的估计输入元素的范围，那么你最好选择一个哈希表或者一个可拓展的 Bloom filter。⁴.

我会将你引向 wiki而不是将它们的内容拷贝过来。 C. Titus Brown 的演讲很好的阐述了 Bloom filter 在生物信息学中的应用。

1: Network Applications of Bloom Filters: A Survey, Broder and Mitzenmacher. An excellent overview.

2: Wikipedia, which has an excellent and comprehensive page on Bloom filters