布隆过滤器

布隆过滤器（Bloom Filter）是一种由 Burton Howard Bloom 在 1970 年提出的，空间效率极高的概率型数据结构。它专门用于判断“一个元素是否在一个集合中”。

以下是关于布隆过滤器的详细介绍：

---

1. 基本原理 (Basic Principle)

布隆过滤器的核心是一个很长的二进制向量（Bit Array）和一组随机映射函数（Hash Functions）。

• 初始化：创建一个长度为 $m$ 的比特数组，所有位都置为 0。
• 添加元素：
  1. 选定 $k$ 个独立的哈希函数。
  2. 当一个元素被加入集合时，用这 $k$ 个哈希函数分别计算该元素的哈希值。
  3. 将这 $k$ 个哈希值对数组长度 $m$ 取模，得到 $k$ 个位置。
  4. 将比特数组中这 $k$ 个位置的值全部设为 1。
• 查询元素：
  1. 用同样的 $k$ 个哈希函数计算该元素的哈希值。
  2. 检查比特数组中这 $k$ 个位置的值。
  3. 如果任意一个位置是 0，则该元素一定不在集合中。
  4. 如果所有位置都是 1，则该元素可能在集合中（存在误报风险）。

---

对此设计的认识

k 个哈希函数相当于是一个空间中的点在 k 个维度上的投影的计算方法，k 个哈希的值就唯一决定了空间中的一个点。

我们可以将每一个一个点的 k 个维度的投影全部记录下来，但是这样就会导致这个记录数据随着点的数量线性增长，同时还会面临对过滤器本身检索时间的线性增加，所以布隆过滤器选择了再进行一次哈希，将数据压缩到长度为 m 的比特数组。

由于两次哈希都有碰撞可能，所以布隆过滤器的结论是集合中不存在，确定是不存在；但是如果结果是存在，那么存在与否无法确认。

2. 例子 (Example)

假设我们有一个长度为 10 的比特数组（$m=10$），和 2 个哈希函数（$k=2$）。

1. 初始状态：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
2. 插入元素 “Apple”：
   • Hash1(“Apple”) % 10 = 3
   • Hash2(“Apple”) % 10 = 7
   • 数组变为：[0, 0, 0, 1, 0, 0, 0, 1, 0, 0]（位置3和7置为1）
3. 插入元素 “Banana”：
   • Hash1(“Banana”) % 10 = 1
   • Hash2(“Banana”) % 10 = 7
   • 数组变为：[0, 1, 0, 1, 0, 0, 0, 1, 0, 0]（位置1置为1，位置7已经是1了）
4. 查询 “Cherry”（不在集合中）：
   • Hash1(“Cherry”) % 10 = 2
   • Hash2(“Cherry”) % 10 = 5
   • 由于位置 2 和 5 都是 0，判定 “Cherry” 一定不存在。
5. 查询 “Peach”（不在集合中，但可能产生误报）：
   • Hash1(“Peach”) % 10 = 1
   • Hash2(“Peach”) % 10 = 3
   • 位置 1 和 3 都是 1（由 Apple 和 Banana 贡献）。布隆过滤器会返回 “可能存在”，这就是假阳性（False Positive）。

---

3. 数学理论 (Mathematical Theory)

布隆过滤器的性能由三个因素决定：比特数组大小 $m$、哈希函数个数 $k$、插入元素个数 $n$。

• 假阳性概率（False Positive Rate, $P$）： 在插入 $n$ 个元素后，任意一个比特位仍为 0 的概率是：$(1-\frac{1}{m}{)}^{kn}\approx e^{-kn/m}$。 因此，某个不在集合中的元素被误判为在集合中的概率约为： $P\approx (1-e^{-kn/m}{)}^k$

• 最优哈希函数个数 $k$： 对于给定的 $m$ 和 $n$，使误判率最小的 $k$ 为： $k=\ln 2\cdot \frac{m}{n}\approx 0.693\cdot \frac{m}{n}$

• 所需存储空间 $m$： 如果预期的元素个数为 $n$，容忍的误判率为 $P$，则需要的比特数 $m$ 为： $m=-\frac{n\ln P}{(\ln 2{)}^2}$

---

4. 特性 (Characteristics)

优点：

1. 极高的空间效率：不存储元素本身，只存储位。比 Hash Set 等结构节省大量空间。
2. 查询时间极快：插入和查询的时间复杂度都是 $O(k)$，与集合中元素的数量无关。
3. 保密性强：由于不存储原始数据，在某些对隐私敏感的场景（如密码黑名单）非常有优势。

缺点：

1. 存在误报（False Positives）：它可能会告诉你某个元素在集合中，但实际上不在。
2. 零漏报（No False Negatives）：如果它说某个元素不在，那它绝对不在。
3. 删除困难：标准的布隆过滤器不支持删除元素。因为多个元素可能映射到同一个比特位，删除一个元素（将 1 置为 0）可能会影响其他元素的判断。
   • 注：可以使用“计数布隆过滤器（Counting Bloom Filter）”来解决删除问题，但会消耗更多空间。

---

5. 常见应用场景

• 防止缓存击穿：在访问数据库之前，先用布隆过滤器判断 Key 是否存在。如果布隆过滤器说不存在，直接返回，避免无效查询大量涌入数据库。
• 垃圾邮件过滤：判断一个邮件地址是否在数亿个垃圾邮件黑名单中。
• 爬虫 URL 去重：在爬取网页时，判断某个 URL 是否已经爬取过。
• 数据库优化：Google BigTable 和 Apache Cassandra 使用布隆过滤器来减少对磁盘中不存在的行或列的访问。

总结

布隆过滤器是一个典型的 “空间换精度” 的设计，它用极小的代价解决了大规模数据的快速过滤问题，只要你的业务逻辑能容忍极小概率的误报，它就是最优选。

Appendex

数学公式推导

推导布隆过滤器的假阳性概率（False Positive Rate）是一个经典的概率统计过程。我们可以将其拆解为以下四个核心步骤：

1. 变量定义

首先明确公式中的变量含义：

• $m$：比特数组的长度（Bit Array Size）。
• $n$：已经插入到过滤器中的元素数量。
• $k$：哈希函数的个数。

---

2. 第一阶段：单个比特位被置为 0 的概率

我们将推导在所有元素插入完成后，数组中某个特定的位（比如第 $i$ 位）仍然是 0 的概率。

1. 单次哈希： 当一个哈希函数对一个元素进行哈希时，它选中某个特定位置的概率是 $\frac{1}{m}$。那么，没选中该位置的概率就是： $1-\frac{1}{m}$
2. 一个元素的所有哈希： 一个元素有 $k$ 个哈希函数。这 $k$ 个函数都没选中该位置的概率是： $(1-\frac{1}{m}{)}^k$
3. 所有 $n$ 个元素的所有哈希： 总共进行了 $n\times k$ 次哈希操作。所有这些操作都没选中该位置的概率（即该位保持为 0）是： $P_{zero}=(1-\frac{1}{m}{)}^{kn}$

---

3. 第二阶段：引入自然常数 $e$ 的近似

为了方便计算，我们利用高等数学中的极限公式：当 $x$ 很大时，$(1-\frac{1}{x}{)}^x\approx e^{-1}$。

1. 我们将原式变形： $P_{zero}={\left[(1-\frac{1}{m}{)}^m\right]}^{\frac{kn}{m}}$
2. 当 $m$ 足够大时，括号内部 $(1-\frac{1}{m}{)}^m\approx e^{-1}\approx \frac{1}{2.718}$。
3. 代入得： $P_{zero}\approx (e^{-1}{)}^{\frac{kn}{m}}=e^{-kn/m}$ 这就是你提到的第一个公式：在插入 $n$ 个元素后，任意一个比特位仍为 0 的概率。

---

4. 第三阶段：比特位被置为 1 的概率

既然位为 0 的概率是 $P_{zero}$，那么位为 1 的概率（即被某个哈希函数击中的概率）就是： $P_{one}=1-P_{zero}\approx 1-e^{-kn/m}$

---

5. 第四阶段：假阳性概率 $P$ 的推导

假阳性定义： 当查询一个实际不存在的元素时，由于哈希冲突，恰好该元素对应的 $k$ 个哈希位置全都是 1。

1. 假设这 $k$ 个位置是独立的（这是一个理想化的假设，但在 $m$ 很大时非常接近真实情况）。
2. 第 1 个位置是 1 的概率是 $P_{one}$。
3. 第 2 个位置也是 1 的概率是 $P_{one}$。
4. …
5. 所有 $k$ 个位置同时为 1 的概率就是 $P_{one}$ 的 $k$ 次幂： $P=(P_{one}{)}^k\approx (1-e^{-kn/m}{)}^k$

---

总结推论直观理解：

• $e^{-kn/m}$：数组中**空着（为0）**的部分比例。
• $1-e^{-kn/m}$：数组中**填了（为1）**的部分比例。
• $(1-e^{-kn/m}{)}^k$：如果你随机在数组里选 $k$ 个点，这 $k$ 个点全都被填过的概率。

结论：

• 当数组长度 $m$ 增大时，$P$ 减小（空间换精度）。
• 当元素个数 $n$ 增大时，$P$ 增大（存得越多，越容易误报）。
• 当哈希函数 $k$ 变化时，对 $P$ 的影响是非线性的，存在一个最优的 $k$ 值能使 $P$ 达到最小。

这两个公式的推导是布隆过滤器理论中最核心的部分，本质上是一个求极值的过程。我们将从上一步得到的假阳性概率公式 $P\approx (1-e^{-kn/m}{)}^k$ 出发进行推导。

---

1. 最优哈希函数个数 $k$ 的推论

我们的目标是：给定 $m$（数组长度）和 $n$（元素个数），找到一个 $k$，使得 $P$ 最小。

第一步：简化表达式 为了方便计算，我们令 $f=e^{-kn/m}$。这里的 $f$ 实际上是经过 $k$ 个哈希函数处理 $n$ 个元素后，某个比特位仍然为 0 的概率。 那么公式变为： $P=(1-f{)}^k$

第二步：利用 $f$ 反推 $k$ 根据 $f=e^{-kn/m}$，取对数得 $\ln f=-kn/m$，所以： $k=-\frac{m}{n}\ln f$

第三步：将 $k$ 代入 $P$ 的表达式中并取对数 为了求极值，我们对 $P$ 取自然对数： $\ln P=k\ln (1-f)$ 代入第二步中的 $k$： $\ln P=-\frac{m}{n}\ln f\cdot \ln (1-f)$ $\ln P=-\frac{m}{n}\left[\ln f\cdot \ln (1-f)\right]$

第四步：求导找极值 我们要使 $\ln P$ 最小。由于 $-\frac{m}{n}$ 是常数且为负数，这等价于求函数 $g(f)=\ln f\cdot \ln (1-f)$ 的最大值。 根据对称性（或者对 $g(f)$ 求导并令其等于 0）： 当 $f=1-f$ 时，即 $f=\frac{1}{2}=0.5$ 时，$g(f)$ 取得最大值。

直观理解： 当布隆过滤器中正好有一半的比特位被置为 1，另一半为 0 时，该结构承载的信息熵最大，误判率最低。

第五步：得出结果 将 $f=1/2$ 代回 $f=e^{-kn/m}$： $e^{-kn/m}=\frac{1}{2}$ $-kn/m=\ln (1/2)=-\ln 2$ $k=\frac{m}{n}\ln 2\approx 0.693\cdot \frac{m}{n}$

---

2. 所需存储空间 $m$ 的推论

我们的目标是：已知预期的误判率 $P$ 和元素个数 $n$，计算最少需要多少比特位 $m$。

第一步：使用最优 $k$ 时的 $P$ 值 在上述推导中我们知道，当 $k$ 取最优值时，$f=1/2$。 代入假阳性概率公式： $P=(1-f{)}^k=(1-1/2{)}^k=(\frac{1}{2}{)}^k$ $P=2^{-k}$

第二步：对 $P$ 取对数 $\ln P=\ln (2^{-k})=-k\ln 2$

第三步：代入最优 $k$ 的表达式 将 $k=\frac{m}{n}\ln 2$ 代入上式： $\ln P=-(\frac{m}{n}\ln 2)\cdot \ln 2$ $\ln P=-\frac{m}{n}(\ln 2{)}^2$

第四步：解出 $m$ $m\ln P=-n(\ln 2{)}^2$ $m=-\frac{n\ln P}{(\ln 2{)}^2}$

---

3. 结论的实际意义

1. 关于 $k$：

   • 如果哈希函数太少，位数组里 1 太少，容易冲突。
   • 如果哈希函数太多，位数组很快就会被填满 1，也容易冲突。
   • 最优状态是：让数组里刚好有一半是 1。

2. 关于 $m$：

   • 公式 $m=-\frac{n\ln P}{(\ln 2{)}^2}$ 告诉我们，空间需求 $m$ 与元素个数 $n$ 成线性正比，与期望误差 $P$ 的对数成反比。
   • 如果你想让误判率从 1% 降到 0.1%，你需要显著增加 $m$（大约增加 1.5 倍空间）。

经验法则： 在最优情况下，每个元素大约需要 9.6 个比特（bits）来维持 1% 的误判率。无论你处理的是 100 万数据还是 10 亿数据，这个比例（$m/n$）是恒定的。

工程例子

在工程实践中（如 RocksDB, HBase, Cassandra, Google BigTable），布隆过滤器通常被存储在内存中，用来拦截对磁盘上不存在的数据的随机读请求。

为了方便估算，我们通常设定一个最常用的误判率标准：$P=1\%$（这是大多数数据库默认或推荐的平衡点）。

在 $P=1\%$ 的情况下，推导公式告诉我们：每个元素大约需要 9.6 bits (约 1.2 字节)。

以下是针对不同量级数据量的布隆过滤器尺寸表：

1. 不同数据规模下的内存占用 (误判率 $P=1\%$)

数据量 ($n$)	占用比特数 ($m$)	占用内存 (字节/MB)	备注
10 万 (10^5)	96 万 bits	117 KB	相当于一张高清图标的大小
100 万 (10^6)	960 万 bits	1.14 MB	极小，现代手机 APP 都能轻松负载
1000 万 (10^7)	9600 万 bits	11.44 MB	相当于一首高品质 MP3 的大小
1 亿 (10^8)	9.6 亿 bits	114.4 MB	约等于一个轻量级浏览器的内存占用
10 亿 (10^9)	96 亿 bits	1.12 GB	这是一个大型商业数据库分片常见的规模
100 亿 (10^10)	960 亿 bits	11.17 GB	需要 16G 内存以上的服务器专门承载

---

2. 误判率对大小的影响（以 1 亿条数据为例）

如果我们改变对“精度”的要求，内存占用会随之变化。依然以 1 亿条数据 ($n=10^8$) 为例：

• 追求极致性能 ($P=0.1\%$):
  • 每个元素需要约 14.4 bits。
  • 总占用：171.6 MB。
  • 适用场景：磁盘 I/O 极其昂贵，必须严防死守。
• 工程平衡点 ($P=1\%$):
  • 每个元素需要约 9.6 bits。
  • 总占用：114.4 MB。
  • 适用场景：主流数据库默认配置。
• 节省内存 ($P=5\%$):
  • 每个元素需要约 6.2 bits。
  • 总占用：74.3 MB。
  • 适用场景：内存资源极度紧张，能挡住 95% 的无效请求即可。

---

3. 工程中的真实案例：RocksDB

在 RocksDB（被用于 TiDB, CockroachDB 等）中，布隆过滤器的配置通常如下：

• 默认配置： bits_per_key = 10。
• 计算： 如果你的数据库里有 1 亿个 Key。
• 内存开销： $1\text{ 亿}\times 10\text{ bits}=1\text{ Gbits}\approx 125\text{ MB}$。
• 效果： 它可以过滤掉 99% 以上原本需要读取磁盘的“不存在的 Key”查询。

4. 为什么这个数据量非常“划算”？

我们可以对比一下：

• 如果用 Hash Set 存储 1 亿个 UUID（每个 36 字节）： 需要 $1\text{ 亿}\times 36\text{ Byte}\approx 3.6\text{ GB}$ 的内存（这还没算 Hash 表的额外指针开销）。
• 如果用布隆过滤器： 只需要 125 MB。

结论： 布隆过滤器用 1/30 的内存代价，解决了 99% 的无效查询问题。在工程上，这种用极小内存交换极大 I/O 性能提升的买卖是非常划算的。通常在千万到亿级数据量时，布隆过滤器的优势最为明显。