cold's world【译文】理解布隆过滤器Fri 10 May 2019原文：Understanding Bloom filters with Pharo Smalltalk。本文通过 HTML 转录了 PharoPDS 库及其扩展附带的交互式教程，以探索和理解布隆过滤器。因此，如果您想在真实的环境中修改这些数据结构，请尝试在 Pharo 镜像中安装这个库，并按照交互式教程并使用提供的自定义工具进行操作。理解布隆过滤器布隆过滤器是一个非常节省空间的数据结构，由 Burton Howard Bloom 于 1970 年所提出（Space/Time Trade-offs in Hash Coding with Allowable Errors），布隆过滤器用于测试一个元素是否是集合的成员之一。常规的哈希搜索通过将一系列值存储在哈希表上，不管是基于链表还是开放寻址（open addressing)，随着越来越多的元素添加到哈希表中，定位元素的期望时间都会从初始的常量的 O(1) 退化或增加到线性的 O(N)。布隆过滤器提供了一个替代的数据结构，可以实现在添加元素或检查元素是否是成员上，不管在空间和时间上都可以保证常量级的性能，并且和已经添加到过滤器中的元素数量是无关的。为了达到如此高效的表现所需要付出的代价是：布隆过滤器是一个概率性的数据结构。Bloom 他在开创性的论文中解释如下：新的方法打算比传统相关的方法减少一定量哈希码所需要的空间。通过利用某些应用可以容忍少量的误差来减少空间的使用，特别是那些拥有大量的数据参与无法通过传统的方法保留核心哈希区域的应用。背景Donald Knuth 在他著名的 The Art of Computer Programming 中写下了如下对布隆过滤器的描述：想象一个拥有非常大量的数据且如果搜索没有成功则无需完成任何计算的搜索应用。比如，我们可能想检查一些人的信用评级或者护照编号，如果文档中没有该人的任何记录我们就无需做任何调查。类似地，在计算机排版应用程序中，我们可能有一个简单算法可以正确地连接大多数单词，但该算法会对大约 5W 个异常单词无效; 如果我们在异常文件中找不到该单词，就可以放心的使用该简单算法。同时 Andrei Broder 和 Michael Mitzenmacher 在著名的布隆过滤器原理（The Bloom Filter Principle(Internet Mathematics Vol. 1, No. 4: 485-509Network Applications ofBloom Filters: A Survey)）中提出：在一个空间宝贵的情况下要使用列表或集合并且可以接受误报，则可以考虑使用布隆过滤器。真实世界的例子Medium 使用布隆过滤器避免推荐给用户已经读过的文章。Google Chrome 使用布隆过滤器识别恶意 URL。Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。Squid Web 代理使用布隆过滤器处理缓存摘要。基本理解布隆过滤器可以通过舍弃元素的特征来高效的存储大规模集合，比如它仅将通过算法对每一个元素应用哈希函数得到的数字存储到一系列位上进行关联。事实上，布隆过滤器通过一个长度（m）和不同哈希函数的数量（k）的比特数组（bit arrary）来表示。该数据结构仅支持两种操作：添加一个元素到集合中来，测试一个元素是否集合的成员。布隆过滤器的数据结构是一个初始比特位都为 0 的比特数组，代表布隆过滤器为空。举个例子，考虑如下示例中创建的布隆过滤器表示一个包含 10 个元素的集合并且误报率（FPP, False Positive Probability）为  0.1 （10%）。一个空的布隆过滤器将通过一个长度为 m=48 (storageSize) 和 4 个哈希函数的比特数组用以支持生产范围在 {1, 2, ..., m} 的值。表示如下：emptyBloomFilter<gtExample>| bloom |bloom := PDSBloomFilter new: 10 fpp: 0.1.self assert: bloom size eqauls: 0.self assert: bloom hashes equals: 4.self assert: bllom storageSize equals: 48.^ bloom要插入一个元素 x 到布隆过滤器中，需要对元素 x 应用到每一个哈希函数 \(h_i\) 上并计算它的值为 \(j=h_i(x)\) ，然后将布隆过滤器中 j 对应的位设置为 1 。作为一个例子，我们将在上面的过滤器中插入一些城市的名字。让我们通过 'Madrid' 开始：withMadridBloomFilter<gtExample>| bloom |bloom := self emptyBloomfilter.bloom add: 'Madrid' asByteArray.self assert: bloom size equals: 1.^ bloom布隆过滤器计算出了 4 个哈希值用以在集合中找到关联 'Madrid' 的比特位。如上图所展示，布隆过滤器设置了 9, 18, 39 和 48 。不同的元素可能共享一个比特位，比如现在我们添加另一个城市 'Barcelona' 到上面相同的布隆过滤器中：如你所见，在添加 'Barcelona' 到上面布隆过滤器之后只有 30, 36 和 42 所对应的比特位被设置，也就意味着元素 'Madrid' 和 'Barcelona' 共享了一个比特位。要想测试给定的元素 x 是否在布隆过滤器之中，只需要检查所有的哈希函数 k 计算出的对应的比特位。如果所有位都被设置来，则表示元素 x 可能在布隆过滤器中，否则元素 x 一定不在其中。元素存在不确定性是由于一些比特位可能是被之前添加的其他不同的元素所设置。考虑前面的例子，在已经添加了元素 'Madrid' 和 'Barcelona' 的情况下，我们来测试元素 'Barcelona' 是否是该过滤器的成员，布隆过滤器计算出该元素的 4 个哈希值并且检查对应的比特位是否被设置，结果显示字符串 'Barcelona' 可能存在于过滤器之中，然后 contains: 'Barcelona' 返回 true ：withMadridAndBarcelonaCheckBarcelonaBloomFilter<gtExample>| bloom |bloom := self withMadridBloomFilter.bloom add: 'Barcelona' asByteArray.self assert: bloom size equals: 2.self assert: (bloom contains: 'Barcelona' asByteArray).^ bloom现在如果我们检查元素 'Berlin' ，布隆过滤器为了找到对