当前位置：首页 > news >正文

系统设计：布隆过滤器

news 2026/5/11 0:29:28

原文：towardsdatascience.com/system-design-bloom-filter-a2e19dcd4810

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/350b777cef6f9090c441e88a64b5066c.png

简介

哈希表是最广为人知和使用的几种数据结构之一。通过明智地选择哈希函数，哈希表可以在常数时间内产生插入、搜索和删除查询的最佳性能。

哈希表的主要缺点是潜在的冲突。为了避免冲突，一种标准方法包括增加哈希表的大小。虽然这种方法在大多数情况下效果良好，但有时我们仍然在使用大量内存空间方面受到限制。

必须记住，哈希表始终对任何查询提供正确响应。它可能会遇到冲突并且有时会变慢，但它始终****保证 100%的正确响应。结果发现，在某些系统中，我们并不总是需要从查询中收到正确信息。这种准确性的降低可以用来关注改进系统的其他方面。

在这篇文章中，我们将发现一种名为布隆过滤器的创新数据结构。简单来说，它是一种标准哈希表的修改版本，它以牺牲少量准确性为代价来换取内存空间的增加。

布隆过滤器

布隆过滤器以大小为 m 的布尔数组的形式组织。最初，其所有元素都被标记为 0（假）。除此之外，还需要选择 k 个哈希函数，这些函数以对象为输入并将它们映射到范围[0, m – 1]。每个输出值将后来对应于该索引处的数组元素。

为了获得更好的结果，建议哈希函数输出值，其分布接近均匀。

<…/Images/7dba5ee0846bd115fe72bc134613d834.png>

在我们的例子中，我们将使用大小为 m = 13 且 k = 3 个哈希函数的布隆过滤器。这些函数中的每一个都将输入对象映射到范围[0, 12]。

插入

每当需要添加一个新的对象时，它将通过 k 个预定义的哈希函数。对于每个输出的哈希值，该索引处的相应元素变为 1（真）。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/3e5eabb3a50f512d1340ec5bff493439.png

“香蕉”对象被添加到布隆过滤器中。哈希函数输出的值是 6、2 和 9。那些索引处的数组元素变为 1。

如果从哈希函数输出的数组元素的索引已经被设置为 1，那么它就简单地保持为 1。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/89944f4964055253a1fef694708c4226.png

“苹果”对象被添加到布隆过滤器中。数组索引为 10、9 和 4 的元素被分配为 1。即使数组的第 9 个元素已经被分配为 1，其值在这里也不会改变。

事实上，任何数组元素上 1 的存在都充当了一个部分证据，表明实际哈希到相应数组索引的元素确实存在于布隆过滤器中。

搜索

要检查一个对象是否存在，需要计算其 k 个哈希值。可能有两种情况：

如果至少有一个哈希值对应的数组元素等于 0，这意味着对象不存在。

在插入过程中，一个对象会与多个标记为 1 的数组元素相关联。如果一个对象确实存在于过滤器中，那么所有的哈希函数都会确定性地输出指向 1 的相同序列的索引。然而，指向值为 0 的数组元素显然表明当前对象不存在于数据结构中。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/29ed491a69dc07f6ddbf6370d2b3e067.png

检查“橙子”对象是否存在于布隆过滤器中。由于至少有一个哈希函数（在我们的情况下恰好是两个）输出数组索引（7 和 12），该数组的元素等于 0，这意味着“橙子”不存在于过滤器中。

如果对于所有哈希值，相应的数组元素都等于 1，这意味着对象****可能存在（不是 100%）。

正是这一陈述使得布隆过滤器成为一个概率数据结构。如果一个对象之前被添加过，那么在搜索过程中，布隆过滤器保证该对象的哈希值将与之前相同，因此可以找到该对象。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/4080375783a28508c39ed9dc034f8e34.png

检查“香蕉”对象是否存在于布隆过滤器中。由于哈希函数是确定的，它们输出与之前在插入“香蕉”时使用的完全相同的数组位置。因此，“香蕉”存在于过滤器中。

尽管如此，当对象实际上不存在但 Bloom 过滤器声称存在时，Bloom 过滤器可以产生误报响应。这种情况发生在所有针对该对象的哈希函数返回的哈希值都对应于过滤器中已插入的其他对象的数组元素值 1 时。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/8ec2cf705980c8e6857abe68c7180a90.png

误报响应的示例。尽管“cherry”之前没有被添加，但过滤器认为它存在，因为“cherry”的所有输出哈希值都指向值为 1 的数组元素。

当插入的对象数量相对于 Bloom 过滤器数组的尺寸较高时，容易出现误报答案。

误报错误估计

在给定 Bloom 过滤器的结构的情况下，可以估计得到误报错误概率。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/c58f6a7eae7bf5057bc61638a5f80f3b.png

作者采用的图像。来源：Bloom 过滤器 | 维基百科

该公式的完整证明可以在维基百科上找到。基于该表达式，我们可以做出一些有趣的观察：

随着哈希函数数量 k 的增加、数组大小 m 的增加和插入对象数量 n 的减少，FP 概率降低。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/5c945c50a37332233f18bb50f2c57f91.png

k 值增加、m 值增加或 n 值减少导致 FP 率降低

在将对象插入 Bloom 过滤器之前，如果我们知道数组大小 m，并且可以估计未来将插入的对象数量 n，我们可以找到将最小化 FP 概率所需的最佳哈希函数数量 k。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/19fa842627470e7b68db235309b004ac.png

最小化 FP 概率的最佳哈希函数数量 k

降低 FP 概率的另一种方法是几个独立 Bloom 过滤器（AND 连接）的组合。只有当一个元素存在于所有 Bloom 过滤器中时，才最终认为该元素存在于数据结构中。

约束条件

与哈希表不同，Bloom 过滤器的标准实现不支持删除。
在开始时选择的哈希函数数量 k 和数组大小 m 之后不能更改。如果有这样的需求，唯一的方法是通过插入所有先前存储的对象来构建具有新设置的另一个 Bloom 过滤器。

应用

根据维基百科页面，Bloom 过滤器在大型系统中被广泛使用：

类似于Apache HBase、Apache Cassandra和PostgreSQL的数据库使用布隆过滤器来检查不存在的行或列。这种方法比使用磁盘查找要快得多。
Medium使用布隆过滤器来过滤掉已经向用户推荐过的页面。
Google Chrome以前使用布隆过滤器来识别恶意网址。如果一个网址在布隆过滤器中返回负响应，则认为它是安全的。否则，将执行完整的检查。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/c3414d2a7c8ab83f2ac9084e02abe344.png

Google 用于检查恶意网址的算法。使用布隆过滤器可以显著减少对大量安全链接所需进行的更多计算量大的完整检查。