布隆过滤器（Space/Time Trade-offsin Hash Coding with Allowable Errors）

布隆过滤器起源于 1970 年发表的一篇Space/Time Trade-offsin Hash Coding with Allowable Errors的论文，该论文主要就可容错哈希编码的时间复杂度和空间复杂度进行了探讨。在算法编码中常常使用空间换时间的方式来提高其运行速度，或者又以时间换空间的方式来降低其空间消耗，由此可得不能同时拥有时空复杂度的好处。Bloom 在该论文中指出，之所以不能同时拥有时空复杂度的好处，是因为为了保证百分之百的准确率，如果能容忍一部分错误，那么理所当然也就能同时拥有时空复杂度的好处。

基于此 Bloom 在论文中提出两种允许存在假阳性，用于测试一个元素是否存在于某个集中中的数据结构。即在允许少量测试元素被错误地识别为给定集合的成员的前提下，可以允许使用更小的哈希集合空间，且不会增加测试元素的执行时间。由此 Bloom 所提出的数据结构，除了需要考虑时间和空间以外，还需要考虑误差率。

介绍

在 Bloom 所提出的两种方法里，其中第二个方法因为时空优势比第一个方法更为明显，所以被世人熟知，也被人称为“Bloom Filter”。

方法一，和以前的哈希编码类似，都是将数据哈希组织成一个单元数组，但与往常的空间相比要小很多。因为该方法并不是将整个数据都参与哈希，而是根据指定的错误率来决定参与哈希的数据大小。即，当允许的错误率越小，通过哈希函数组成的单元数组占用的空间越大。当错误率足够小时（大约 2-b），单元数组占用的空间将等于整个目标数据的大小。

假定使用 P 代表可允许的错误率，且错误率在 1>>P>>2-b 区间，那么一个具体的 P 值就会对应一个单元数组的空间大小。例如选定一个错误率为 e（e > 2-b）,那么通过这个错误率 e 算出一个固定的 C 比特大小的单元数组，所以每一个目标数据会被哈希编码成一个 C 比特的单元数组（不一定是唯一的），故此会存在多个不同目标数据被哈希编码为同一个单元数组，错误率就是由此得来。

方法二，完全抛弃了之前通过哈希组成一个单元数组的数据结构，哈希区被认为是由 N 个单独哈希函数求值后得到的寻址位组成。首先将哈希区中的所有哈希位都置为 0，假设一个值被 N 个哈希函数计算后的寻址位分别是，“a1、a2、a3....aN”，那么就需要将“a1、a2、a3....aN“N 个寻址位对应的 0 置为 1。

详细步骤如下所示：

1. 给定一个长度为 N bits 的哈希空间。

2. 选取 d 个不同的哈希函数，每个哈希函数将给定的元素映射到[0, N-1]的位置上，并将该位置的 0 置为 1。

3. 将需要被判断的元素也用步骤 b 计算出 d 个位置，“a1、a2、a3....ad”。

4. 依次遍历 d 个位置在哈希空间上对应的值是否是 1，如果全为 1，就表示该元素有可能在哈希空间中；如果有一个不为 1，就表示该元素一定不在哈希空间中。

从上述 4 个步骤不难看出其算法存在一定的错误率，在原论文中给出了方法一和方法二的证明过程，这里就不再进行累述，如感兴趣可自行阅读Space/Time Trade-offsin Hash Coding with Allowable Errors。

例子

一个简单的例子，如下图所示：

1. 定义一个长度为 15bits 的原始哈希空间，并将每个 bit 位的值都为 0；

2. 使用两个哈希函数将 hello 分为映射到 1 号位和 5 号位，并将 1 号位和 5 号位置为 1；

3. 寻找 world 时，也同样使用两个哈希函数对其哈希求值得到 1 号位和 8 号位；

4. 在哈希空间中判断 1 号位和 8 号位的值是否 1，如果都为 1 则表示 world 有可能在哈希空间，反之则一定不在哈希空间中。