【后端基础】布隆过滤器原理

Bloom Filter 是一种非常高效的概率型数据结构，广泛应用于需要快速判断元素是否在集合中的场景。虽然它可能会产生假阳性，但通过调整位数组的大小和哈希函数的数量，可以控制假阳性率。在内存受限的环境中，Bloom Filter 提供了一个非常节省空间的解决方案。

通过适当的哈希函数和合理的配置，Bloom Filter 在大数据系统、搜索引擎、网络安全等领域具有广泛的应用前景。

一、Bloom Filter（布隆过滤器）概述

Bloom Filter 是一种空间高效的概率型数据结构，用于测试一个元素是否属于一个集合。它的特点是可以快速地判断某个元素是否在集合中，但是有一定的假阳性率。也就是说，Bloom Filter 可能会错误地告诉你某个元素存在，但实际上它并不在集合中；然而，假阴性（即元素确实存在，但 Bloom Filter 却说它不存在）是永远不会发生的。

1. Bloom Filter 的特点

1. 空间高效： 相较于传统的哈希表，Bloom Filter 在固定大小的情况下可以表示一个元素数量极大的集合。它不需要存储实际的元素值，而是通过一组哈希函数和一个位数组来表示集合。

2. 永不产生假阴性： Bloom Filter 不会错误地告诉你某个元素不存在，只会可能错误地告诉你某个元素已经存在（即假阳性）。

3. 增加元素时不会失败： 向 Bloom Filter 中添加元素不会失败，但是随着添加的元素增多，假阳性率会逐渐增加，直到所有的位都被设置为 1 为止，在此时所有查询都会返回存在的结果。

4. 无法删除元素： 删除元素在 Bloom Filter 中是不可能的，因为如果清除某个哈希值对应的位，会影响其他元素的存在性。例如，如果你删除 “geeks”，可能会错误地删除 “nerd”。这就是 Bloom Filter 无法删除元素的原因。

2. Bloom Filter 的工作原理

Bloom Filter 的基本操作包括：

• 插入元素（insert）：通过多个哈希函数计算出元素的哈希值，并将这些哈希值对应的位设置为 1。
• 查询元素（lookup）：同样计算该元素的哈希值，如果对应位全为 1，则认为元素可能存在；如果有任何一个位是 0，则可以确定元素不在集合中。

二、示例

1. 添加与查询

通过概率+节点个数来决定布隆过滤器的函数个数、数组位数

假设我们有一个长度为 10 的位数组，所有位初始值为 0，我们使用 3 个哈希函数来添加 “geeks” 和 “nerd” 这两个元素。

1. 添加 “geeks”：

   • 计算哈希值：
     • h1(“geeks”) % 10 = 1
     • h2(“geeks”) % 10 = 4
     • h3(“geeks”) % 10 = 7
   • 将位数组中的索引 1、4、7 设置为 1。

2. 添加 “nerd”：

   • 计算哈希值：
     • h1(“nerd”) % 10 = 3
     • h2(“nerd”) % 10 = 5
     • h3(“nerd”) % 10 = 4
   • 将位数组中的索引 3、5、4 设置为 1。

1. 查询 “geeks”：
   • 计算哈希值并检查位数组中的相应位置：
     • 如果所有索引（1、4、7）对应的位都为 1，则 “geeks” 可能存在。
       

2. 假阳性

由于多个元素可能会映射到同一位，Bloom Filter 会发生假阳性。例如，当我们查询 “cat” 时，计算出哈希值为 1、3、7，查到这三个位置的值为 1，虽然 “cat” 并没有被添加到 Bloom Filter 中，但它的哈希值与其他元素（如 “geeks” 和 “nerd”）重合了，因此 Bloom Filter 错误地认为 “cat” 存在。这就是假阳性。

三、Bloom Filter 的操作

• insert(x)：将元素 x 插入到 Bloom Filter 中。
• lookup(x)：检查元素 x 是否存在于 Bloom Filter 中，返回“可能存在”或“肯定不存在”。

1、假阳性概率

假阳性概率可以通过以下公式计算：

$$P={\left(1-{\left(1-\frac{1}{m}\right)}^{kn}\right)}^k$$

其中：

• m 是位数组的大小，
• k 是哈希函数的数量，
• n 是预计插入元素的数量。

位数组大小的计算：

$$m=\frac{-n\cdot \ln (p)}{(\ln (2){)}^2}$$

哈希函数数量的计算：

$$k=\frac{m}{n}\cdot \ln (2)$$

2、空间效率

Bloom Filter 的空间效率非常高。传统的集合存储结构（如哈希表、数组或链表）需要存储数据本身，而 Bloom Filter 只需要一个位数组，这使得它在内存使用上非常高效。
 

3、哈希函数的选择

Bloom Filter 使用的哈希函数应该是独立且均匀分布的。常用的非加密哈希函数如 MurmurHash、FNV、Jenkins 都能很好地工作。加密哈希函数虽然稳定且具有较强的保证，但在性能上较慢，因此在 Bloom Filter 中更常用非加密哈希函数以提高性能。

四、应用

1. 中等大小的集合过滤：Medium 用 Bloom Filter 来推荐用户已经看过的帖子，从而避免重复推荐。
2. Quora：实现了一个共享的 Bloom Filter，过滤用户已经看过的帖子。
3. Google Chrome：用 Bloom Filter 来识别恶意 URL。
4. 大数据存储系统：Google BigTable、Apache HBase、Apache Cassandra 和 PostgreSQL 等都使用 Bloom Filter 来减少磁盘查询，特别是在没有存在的行或列时。