您现在的位置是：首页 >其他 >论文的角度—布隆过滤器网站首页其他

  布隆过滤器起源于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，就表示该元素一定不在哈希空间中

  从上述步骤d不难看出其算法存在一定的错误率。

  如上图所示：

• 首先，定义一个长度为15bits的原始哈希空间，并将每个bit位的值都为0；
• 然后，使用两个哈希函数将hello分为映射到1号位和5号位，并将1号位和5号位置为1；
• 其次，寻找world时，也同样使用两个哈希函数对其哈希求值得到1号位和8号位；
• 最后，在哈希空间中判断1号位和8号位的值是否1，如果都为1则表示world有可能在哈希空间，反之则一定不在哈希空间中。

  在原论文中给出了方法一和方法二的证明过程，这里就不再进行累述，如感兴趣可自行阅读Space/Time Trade-offsin Hash Coding with Allowable Errors。