谈谈布隆过滤器

发布网友 发布时间：2024-10-02 01:41

我来回答

共1个回答

热心网友 时间：2024-10-18 03:53

布隆过滤器（Bloom Filter）本质上是一种数据结构，与 Map、List 等“传统”数据结构不同的是，布隆过滤器是一种概率型数据结构（Probabilistic data structure），其返回的结果是概率性的，而不是确切的。

不同的数据结构有不同的适用场景和优缺点，你需要仔细权衡自己的需求之后妥善适用它们，布隆过滤器就是践行这句话的代表。

这里抛出一个具有实际意义的场景：假如某个系统需要在用户访问风险网页时进行拦截，现有 10 亿条风险网页 URL 记录，需要实现一个网页过滤模块，可以根据网页 URL 判断其是否属于风险网站。额外规定，这一网页过滤模块只需保证误判、漏判的概率低于万分之一即可，在满足这一条件的前提下，应尽可能提高效率。

分析这一场景，实际上是要求实现一种高效算法，可以判断某一元素是否存在于集合中。

如果想判断一个元素是不是在一个集合中，一般想到的方法就是直接通过遍历判定是否存在集合中。这种方法在数据量小的情况下比较适用，但是随着集合中元素的增多，检索速度会越来越慢。

上述方案的改进就是将 URL 经过 MD5 或 SHA-1 哈希后再保存到 HashSet，比起直接存储 URL 更节省内存，但本质上都是 O(1) 复杂度的直接遍历。若想更进一步，还可直接将每个 URL 经过哈希函数映射到某一 Bit 位，建立一个 Bitmap，但在这一实现中，单一哈希函数发生冲突的概率非常高。

为了解决这种快速判断某个元素是否属于集合（不严格要求 100% 正确）的问题，布隆过滤器这一思想被提出了。布隆过滤器是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数，可以用于检索一个元素是否在一个集合中。

一个空的布隆过滤器是一个 m 位的 Bit 位数组，所有 Bit 位都为 0。还必须定义 k 个不同的散列函数，每个散列函数将某些集合元素均匀随机映射到 m 个数组位置之一。通常，k 是一个小的常数，它取决于所需的错误率 ε，而 m 与 k 和要添加的元素数量成正比。

要添加一个元素，将其提供给每个哈希函数以获得 k 个数组位置，将这些 Bit 位设置为 1。

要查询一个元素，将其提供给每个哈希函数以获取 k 个数组位置，如果这些位置中的任意 Bit 位为 0，则该元素肯定不在集合中；如果这些位置的 Bit 位全部为 1，则要么元素在集合中，要么在插入其他元素期间，这些位偶然被设置为 1，从而导致误报。

从布隆过滤器中删除一个元素是不可能的，因为没有办法知道它映射到的 k 位中的哪一个应该被清除。尽管将这些 Bit 位中的任何一个设置为 0 就足以删除该元素，但这样也会删除碰巧映射到该位上的任何其他元素。

上图是一个布隆过滤器示例，表示集合 {x, y, z}。彩色箭头显示每个集合元素映射到的位数组中的位置。元素 w 不在集合 {x, y, z} 中，因为它散列到一个包含 0 的位数组位置。对于该图，m = 18 和 k = 3。

设计简单，布隆过滤器是一种设计十分精巧的数据结构，其核心思想极其简单，易于实现

空间效率高，相比于传统数组、链表等数据结构，布隆过滤器不需要存储元素本身

速度快，布隆过滤器插入/查询时间都是常数 O(k)

易于优化，各个散列函数相互之间没有关系，方便由硬件并行实现

保密性好，布隆过滤器不需要存储元素本身，只存储其存在与否的标志位

可能误报，且存入的元素数量越多，误报率越大

无法删除元素，要想删除一个元素，只能重新进行散列（但布隆过滤器的衍生数据结构解决了这一问题）

标准 Bloom Filter 只支持插入和查找两种操作，但在现实世界中，数据集往往不是一成不变的，这时候就需要一种支持删除元素的 Bloom Filter。Counting Bloom Filter 将标准 Bloom Filter 数组的每一位扩展为一个计数器，在插入元素时给对应的 k 个计数器的值分别加 1，删除元素时给对应的 k 个计数器的值分别减 1。Counting Bloom Filter 通过占用更多空间的代价，使得 Bloom Filter 支持了删除操作。

Partial Bloom Filter 和标准 Bloom Filter 唯一不同的地方在于哈希函数的映射范围。在 Partial Bloom Filter 中，数组被等分成 k 个区域，每个哈希函数只映射到其中一个区域；而在标准 Bloom Filter 中，每个哈希函数都映射到同一区域（都映射到整个数组）。

在实际应用中，Partial Bloom Filter 具有一定的优势，因为一旦哈希函数的映射范围独立开来，k 个哈希函数就可以并行访问数组，从而提高性能。

布隆过滤器可以用于检索一个元素是否在一个集合中，在实际系统中，常见的应用场景如下：

网页爬虫：将已经爬取过的 URL 存入布隆过滤器，对将要爬取的 URL 进行去重，避免重复爬取 URL 地址

拦截恶意网页：Google Chrome 基于布隆过滤器识别恶意 URL（就像本文“背景与意义”部分提到的一样）

反垃圾邮件：从数十亿个垃圾邮件列表中判断某邮箱是否为垃圾邮箱

避免重复推送：通过布隆过滤器判断用户是否阅读过某视频或文章，避免其反复被推送

防止穿库：Google BigTable、Apache HBase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找

应对缓存击穿：当数据库查询发生缓存大量击穿的情形时，只有在布隆过滤器中，才去查询缓存；如果没查询到，则穿透到数据库；如果不在布隆器中，则直接返回数据不存在

一般来说，算法需要考虑两方面问题，时间复杂度和空间复杂度。两者不可皆得，要么时间换空间，要么空间换时间。概率型数据结构的引入，使得算法设计有了一种新的思路——准确性换时间/空间。作为概率型数据结构的重要代表，布隆过滤器设计得十分精巧，笔者认为解析它是一件十分令人愉悦的事情.

另，可视化地体验一下布隆过滤器可能比阅读本文的描述更有趣，在 jasondavies.com 这一网站上，提供了一个可视化的布隆过滤器，可以用它方便地演示布隆过滤器的行为。

[1] Bloom, Burton H. (1970), "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of the ACM, 13 (7): 422–426

[2] Fan, Li; Cao, Pei; Almeida, Jussara; Broder, Andrei (2000), "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol", IEEE/ACM Transactions on Networking, 8 (3): 281–293