布隆过滤器是您可能已经知道或至少听说过的数据结构之一。对于那些寻求简单回顾的人来说，它们是一种概率数据结构，可用于确定某物是否在集合中，为某些检查提供了轻微的返回误报结果的机会，但使用的空间少于完整的哈希图。您可能不知道的是，虽然您可以将它们用作节省空间的哈希/字典，但还有其他一些您可能不知道的用例。然而，在继续使用之前，让我们花点时间来构建一个。很多人似乎缺乏这种理解，并认为布隆过滤器比实际情况更复杂或更神秘。事实证明，如果您不介意效率低下（至少一开始是），那么构建布隆过滤器实际上非常容易。我将使用 JavaScript 实现一个，因为任何阅读本文的人都可以使用浏览器控制台进行操作。为什么？好吧，我发现一些简单的代码往往是明确的，并且可以很好地传达含义。您需要的第一件事是哈希函数。理想情况下，对于布隆过滤器，您希望使用诸如 Murmur3 和 FNV-1a 之类的东西，因为您希望散列尽可能快，并且分布良好。有关更多详细信息，请参阅这个优秀的 stackexchange 问题和第一条评论。然而，因为浏览器中的 JavaScript 没有附带哈希，这里是 Java 字符串哈希的一个端口，它让我们无需实现任何太困难的东西。您可以将以下内容复制并粘贴到您的控制台中，这将为字符串添加哈希函数。 // 原始哈希函数，用于字符串返回正的 32 位 int // 不要在生产中使用，使用 murmur3 或 fnv1 对象。 defineProperty(String.prototype, 'hashCode', { value : function() { var hash = 0, i, chr; for ( i = 0; i < this.length; i ++) { chr = this.charCodeAt( i ); hash = (( hash << 5) - hash) + chr; hash |= 0; // 转换为32位整数 } return Math.abs( hash); }});
因此，完成后以免创建我们的过滤器。从本质上讲，过滤器本身只是一个位数组。您只需要为数组中的每个条目存储两个状态。请注意，在许多语言中，使用布尔值并没有得到一点支持，因此使用布尔值作为后备数组可能不像您预期的那样高效。您往往需要使用位集实现或位打包成整数以提高效率，但这超出了我们在这里需要的范围。让我们创建一个布隆过滤器，它包含 16 个布尔值来表示输出位，然后散列两个单词并将它们放入过滤器中。 // 以 16 个 0 开始我们的布隆过滤器，表示它的空 varbloom = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; // 使用单个散列向过滤器添加一些单词 // 我们使用 % 将我们的 32 位数字转换为 16 个值之一 // 用于我们的布隆过滤器bloom[“something”的长度。 hashCode() % 绽放。长度] = 1;绽放[“另一个”。 hashCode() % 绽放。长度] = 1;运行上述内容后，您的布隆过滤器应设置 2 位，如下所示，[ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1 , 0] 如您所见，此过滤器中的位置 7 和 15 现在已设置。为了检查过滤器中是否存在某些内容，您可以执行相同的散列操作并检查值而不是设置。因此，如果我们想查看过滤器中是否存在某些内容，请注意由于布隆过滤器的误报属性，注释“可能”在过滤器中。
以上几乎是您开始使用布隆过滤器所需的全部内容。对于真正的实现换出更好的散列函数，实际上将其中两个与盐一起使用以获得超过 2 个散列，您需要降低误报率。您还需要为任何重要的事情增加过滤器本身的大小。使用此计算器来确定达到所需误报率所需的过滤器大小。请注意，误报率实际上是一项功能，在某些情况下，您可能希望提高或降低误报率以实现目标。如果您正在寻找有关如何在此处实施的更多详细信息，请参阅要点 https://gist.github.com/boyter/0cffa9ff8e2e7259d455594d744f1164，其中包含更多详细信息和示例。请注意，布隆过滤器对您可以添加的术语数量没有任何内置限制。您可以根据需要向其中添加任意数量的术语，但在某些时候，它会将误报率推向接近 100%，从而使过滤器实际上毫无用处，因此需要预先了解要在其中存储多少个术语有效地使用它们。布隆过滤器不仅仅是一个空间高效的哈希图！让我们来看看它们的一些越来越不常见的用例。第一个也是最明显的是将其用作查找缓存。这与哈希图的想法相同，但更节省空间。考虑运行一个视频/音乐电子商店，您可以从后端数据库或缓存中提取有关电影或歌曲的详细信息。使用布隆过滤器前端，您可以使用少量内存来过滤对后端的请求，只需查看您确信结果存在的位置。因为您需要存储的每个密钥都可以容纳约 10 位数据，所以您可以交换少量内存以避免后端系统过载。您还可以使用布隆过滤器来减轻网站上的缓存破坏攻击。对于任何网站，使用各种缓存级别以防止多个请求访问您的后端并使其过载是相当普遍的。然而，大多数网站也允许在 URL 本身或通过 GET 参数使用参数。考虑一个电子商务网站，其中您有许多产品 ID，通过摆弄 URL，有人可以遍历它们。虽然您可以缓存每个产品的结果，但如果有人恶意决定请求没有产品的项目，会发生什么情况？您必须检查您的后端以实际检查它是否在那里，这在规模上可能会在您的系统上发生争用。您可以使用布隆过滤器来保存所有产品 ID，并且只有在过滤器显示该项目实际出现时才点击后端进行完整查找。
Akami 还使用布隆过滤器来避免一个命中奇迹项目填充缓存。为只请求一次的项目填充缓存几乎没有什么好处，而且互联网的长尾非常大。 Akami 意识到了这一点，并使用布隆过滤器来确定相关项目是否在第二次请求之前被请求过，并且只有在第二次请求之后才会缓存该项目。任何缓存系统都可以使用类似的技术来避免使用很少请求的项目填充缓存。拼写检查器也是布隆过滤器的一个用例，当时您真的不得不担心内存使用情况。每学期约 10 位，您可以将大量单词打包到有限的内存中，并通过快速查找来确定单词是否是真实单词。需要考虑的一件事是布隆过滤器的属性。因为您通过不可逆函数多次散列密钥，所以可以在最后共享您的布隆过滤器，作为共享您持有的信息而不共享信息本身的一种方式。您甚至可以让暴力破解获取信息变得不可能，因为您可以将过滤器配置为具有更高的错误率，并在攻击者暴力破解时使用误报淹没攻击者。考虑一个分布式社交网络，我想让两个人确定他们的联系人列表中是否有任何重叠。由于隐私原因，我想这样做而不必共享列表。您可以为每个用户联系人构建一个过滤器，并交换它们。然后检查过滤器以确定我们是否有重叠，即使您拥有两个过滤器，也无法重建任何一个列表。假设我担心有人会得到这些过滤器的副本，我也可以提高误报率以阻止潜在的攻击。你也可以进一步扩展这个想法。假设我想确定两个用户的社交圈之间的重叠。构建两个大小相同的过滤器，其中包含每个用户的朋友。然后比较两个过滤器的位。重叠越多，共享位越多。这也适用于查找单词或句子之间的距离，无论文本有多长，它都有效，因为它更接近于单词/术语而不是它们出现的频率。您将文档拆分为 ngrams（比如 trigrams），将每个添加到您的过滤器中并以相同的方式比较它们。重叠的位越多，它们就越接近。共享合理所有权证明的想法是布隆过滤器的一个有趣用例。举例来说，您已经获得了一个散列密码列表，并想证明您拥有它们而不传输散列本身。您可以将它们全部编码到配置了高错误率的布隆过滤器中。您还可以使用布隆过滤器来制作搜索引擎。我第一次在 Hacker News https://www.stavros.io/posts/bloom-filter-search-engine/ 上读到了这个想法，这个想法是你为每个要索引的文档构建一个布隆过滤器，然后遍历每个过滤器检查条款是否在每个条款中。这适用于几千个文档的小规模。
然而，这是布隆过滤器搜索引擎的一个相当原始的版本。事实证明，你可以做得更好。布隆过滤器的好处是您可以使用按位运算查询它们。实际上，如果您将每个文档存储在相同大小的过滤器中，您最终会在一个块中得到一组过滤器，如下所示，对于 3 个文档，每个文档都有 8 位布隆过滤器。这很好，因为假设您搜索了一个哈希值为 10010000 的术语（请注意，搜索过滤器必须与您正在搜索的文档一样长），然后您可以应用按位 OR 操作逐步浏览每个文档以查看结果是否为零如果不是，则意味着我们可能有匹配的文档。按位运算在任何 CPU 上都非常快，因此从 CPU 的角度来看，实际检查实际上是免费的。问题是你需要遍历整个语料库的每个记忆部分。然而，有一种方法可以减少这种情况。如果您旋转位向量，则只需检查那些与您的搜索词哈希位位置匹配的向量，这样文档就会从行移动到列。然后给定我们的搜索 10010000，您将查看 term1 和 term4 的位（因为位位置 1 和 4 已设置）。然后将它们 OR 在一起，您会得到 1，表明文档 1 是搜索的可能匹配项。它还将我们为该查询查看的位数从 24 减少到 9。当您有更大的过滤器时（这是您所期望的），这更令人印象深刻。搜索 10010000 位置 1 和 4 已设置，因此我们要使用过滤器位置 term1 和 term4term1 100term4 100then 中的那些取值或将它们放在一起 100，这意味着第一列中的文档 1 可能是匹配项 这种搜索技术真正酷的是因为按位运算是如此之快，您可以认为它们是免费的，您最终只会受到内存带宽的限制，这意味着您实际上可以根据每台机器索引中的文档数量计算每次搜索需要多长时间。
然而，bing.com 的一部分设法进一步改进了这个算法。这完全超出了本文档的范围，但它涉及使用他们所谓的排名较高的行，在这些行中，它们在逻辑上将过滤器的一半与自身进行“或”以减少内存访问。除了能够将过滤器长度分片到不同的机器（可能因为规模原因）之外，它们还能够将内存访问减少到每秒可以在每台机器上运行数千次搜索的水平。它是一个非常酷的技术集合。布隆过滤器的变体包括压缩布隆过滤器、过期和计数布隆过滤器。它们使用较少的内存，使旧密钥过期并记录添加密钥的次数（如果您以内存为代价正确实现它，则允许删除）。另一个类似的是布谷鸟过滤器，它的工作方式与布隆过滤器类似，不同之处在于它有一个内置限制，在此限制之后它将不再添加项目，可以删除项目并具有一些不同的内存特性。所以一开始我想自己实现 bitfunnel 变成了比我预期的更长的布隆过滤器。我不得不承认，它们现在是我最喜欢的数据结构（哇……你得有多少书呆子才能拥有其中一个）取代我以前的向量空间。虽然我在日常工作中并没有真正使用布隆过滤器，但我希望像 https://boyter.org/posts/media-clipping-using-ffmpeg-with-cache-eviction -2-random-for-disk-caching-at-scale/ 2 随机缓存逐出我可能会在这些天的某一天使用它。