布隆过滤器

1. 概述与学习目标

1.1 什么是布隆过滤器

布隆过滤器（Bloom Filter）是一种空间高效的概率数据结构（space-efficient probabilistic data structure），用于高效地判断一个元素是否可能属于一个集合。它由 Burton Howard Bloom 于 1970 年在《Space/Time Trade-offs in Hash Coding with Allowable Errors》Communications of the ACM 13(7):422-426 提出（DOI: 10.1145/362686.362692），其核心思想是用 $k$ 个独立哈希函数将元素映射到 $m$ 位的位数组，并允许可控的假阳性（false positive）以换取 10-100 倍的空间节省。

布隆过滤器的形式化定义如下：

• 集合 $S = \{x_1, x_2, \ldots, x_n\}$ 是待表示的元素集合，$|S| = n$
• 位数组 $\mathbf{B}[0..m-1]$，初始全为 0，每个位仅占 1 bit 内存
• 哈希函数族 $h_1, h_2, \ldots, h_k: U \to \{0, 1, \ldots, m-1\}$，每个 $h_i$ 独立均匀地将任意元素 $x$ 映射到位数组的某个位置

插入元素 $x$ 时，将 $\mathbf{B}[h_1(x)], \mathbf{B}[h_2(x)], \ldots, \mathbf{B}[h_k(x)]$ 全部置为 1：

$\texttt{insert}(x): \quad \forall i \in [1, k], \quad \mathbf{B}[h_i(x)] \leftarrow 1$

查询元素 $y$ 时，检查 $\mathbf{B}[h_1(y)], \mathbf{B}[h_2(y)], \ldots, \mathbf{B}[h_k(y)]$ 是否全为 1：

$\texttt{query}(y): \quad \text{return } \bigwedge_{i=1}^{k} \mathbf{B}[h_i(y)]$

布隆过滤器具有两条核心保证：

1. 无假阴性（No false negatives）：若 $x \in S$，则查询 $x$ 必返回 true。这是因为插入 $x$ 时已将 $h_i(x)$ 对应的位置为 1，后续操作只会置位不清位，故查询时这些位必为 1
2. 有假阳性（Possible false positives）：若 $x \notin S$，查询 $x$ 仍可能返回 true。这是因为 $x$ 的 $k$ 个哈希位置可能被其他元素的插入操作全部置为 1

1.2 为什么需要布隆过滤器

考虑以下工程问题：一个 Web 应用的用户表有 1 亿条记录，每次用户登录时需要校验用户名是否已存在。直接将 1 亿用户名加载到内存的哈希表中：

• 内存消耗：假设每个用户名平均 20 字节，哈希表开销（含指针、桶）约 5 倍，共需 10 GB 内存
• 加载时间：从磁盘加载 1 亿条记录至内存约需 30 秒，启动缓慢
• 维护成本：哈希表常驻内存，挤占缓存空间

布隆过滤器的解决方案：

• 在 1% 假阳性率下，每个元素仅需 9.58 bit，1 亿元素共需 $9.58 \times 10^8 \text{ bit} \approx 120$ MB
• 查询时间 $O(k)$，$k = 7$，远快于磁盘 I/O
• 假阳性率 1% 意味着每 100 次不存在的查询中仅有 1 次会穿透到后端数据库，有效拦截 99% 的无效请求

典型应用场景包括：

1.3 核心思想

布隆过滤器的核心思想可以总结为三条工程权衡：

1. 空间 vs 精度：用位数组替代完整的元素存储，每个元素仅需 9-15 bit（取决于假阳性率），空间节省 10-100 倍
2. 时间 vs 精度：用 $k$ 次哈希函数查询替代完整哈希表查询，查询时间 $O(k)$ 且 $k$ 通常为 7-15，远快于磁盘 I/O
3. 确定性 vs 概率性：放弃”精确判断”换取”概率判断”，但保证无假阴性这一关键性质，使所有假阳性都能被后端完整数据结构兜底

这三条权衡使布隆过滤器成为预处理层（pre-filter）的理想选择：在昂贵的精确查询（磁盘 I/O、网络请求、数据库查询）之前，先用布隆过滤器过滤掉绝大多数无效请求，仅在假阳性发生时才触发真正的查询。

1.4 学习目标

完成本章学习后，读者应能够：

1. 记忆（Remember）：布隆过滤器的五要素结构（位数组 $m$ 位、$k$ 个哈希函数、插入流程、查询流程、无假阴性定理）与 Bloom 1970 CACM 13(7):422-426 论文核心贡献
2. 理解（Understand）：Bloom 1970 原始动机、Fan-Cao-Almeida-Broder 1998《Summary Cache》推动 Counting Bloom Filter 工业化、Mitzenmacher 2002《Compressed Bloom Filters》网络传输优化、Fan-Andersen-Kaminsky 2014《Cuckoo Filter》的演进脉络
3. 应用（Apply）：使用假阳性率公式 $P = (1 - e^{-kn/m})^k$、最优哈希函数个数 $k_{\text{opt}} = (m/n) \ln 2$ 设计布隆过滤器参数，编写 Python/C++/Java 三语言实现
4. 分析（Analyze）：基于 $k$ 个哈希函数独立性假设与泊松近似，证明假阳性率上界；基于单调性（插入只置位不清位）证明无假阴性定理
5. 评估（Evaluate）：布隆过滤器与 Hash Set、Cuckoo Filter、HyperLogLog、Count-Min Sketch 在空间、查询时间、假阳性率、删除支持、计数支持维度上的优劣对比
6. 设计（Design）：Counting Bloom Filter、Spectral Bloom Filter、Stable Bloom Filter、Compressed Bloom Filter、Cuckoo Filter 等变种以支持删除、计数、流式数据、网络传输等扩展需求
7. 创造（Create）：基于布隆过滤器设计缓存穿透防护系统、爬虫 URL 去重引擎、邮件恶意 URL 检测系统、区块链 SPV 节点轻客户端、数据库查询缓存层

2. 历史动机与演进

2.1 Bloom 1970：原始动机与首次提出

1960 年代末，Burton Howard Bloom 在 Computer Associates International 从事文档处理系统开发，遇到一个具体工程问题：如何为自动断字器（automatic hyphenation program）提供一个空间高效的字典查询机制。

断字器的核心任务是判断英文单词在哪些位置可以换行（如 “hyphen-ation”）。一个完整的英文断字规则字典包含约 10 万条规则，每条规则形如 .hy3ph（表示在 “hy” 之后第 3 个字符处可断字）。如果将全部规则加载到内存的哈希表，需要数 MB 内存，这在 1960 年代末（典型计算机内存 64 KB - 256 KB）是不可接受的。

Bloom 的关键洞察是：

1. 断字器对误判率不敏感：若布隆过滤器误报某规则存在，只需在二级精确字典中再查一次即可，开销可接受
2. 断字器对漏报率绝对敏感：若某规则被漏报，则该位置无法正确断字，影响排版质量
3. 传统的哈希表占用 $O(n \log n)$ 位（存储完整元素），但若允许误判，可以仅占用 $O(n)$ 位

基于这一动机，Bloom 在 1970 年 Communications of the ACM 13(7):422-426 发表《Space/Time Trade-offs in Hash Coding with Allowable Errors》一文，提出用 $k$ 个独立哈希函数将元素映射到 $m$ 位的位数组。该论文的原始表述是：

“A new method for storing and retrieving information from a hash file is described. The method, termed hash coding with allowable errors, allows a small probability of error in retrieval in exchange for a substantial reduction in storage requirements.”

Bloom 原始论文给出的关键参数关系（在 $k$ 个哈希函数独立均匀的假设下）：

Bloom 1970 原论文给出的核心结论是：在 $m \gg n$ 的条件下，假阳性率 $\epsilon$ 可以被压低至任意小的常数，同时 $m/n$（每元素占用 bit 数）保持常数级。这一结论奠定了布隆过滤器作为”空间高效概率数据结构”的地位。

2.2 早期应用与网络协议时代（1990s）

布隆过滤器提出后的前 20 年（1970-1990）主要停留在学术研究阶段，工业应用较少。原因有二：

1. 1970-1980 年代内存稀缺，但布隆过滤器的主要应用场景（如 Web 缓存、P2P 网络）尚未出现
2. 哈希函数计算成本较高，$k$ 次哈希的开销在 1970 年代硬件上不可忽略

1990 年代 Web 兴起后，布隆过滤器迎来了第一次大规模工业应用浪潮：

Spafford 1992：口令字典过滤

Gene Spafford 在 1992 年 Purdue 大学技术报告中提出使用布隆过滤器存储常见弱口令字典，用户设置口令时先查布隆过滤器，若命中则拒绝（假阳性时再查精确字典）。这一方案后来被 Linux PAM 模块和 macOS 口令检查器采用。

Fan-Cao-Almeida-Broder 1998：Summary Cache

Li Fan、Pei Cao、Jussara Almeida、Andrei Broder 1998 年在 SIGCOMM 发表《Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol》（DOI: 10.1145/285237.285287），首次提出 Counting Bloom Filter（CBF）以解决 Web 缓存代理之间的缓存摘要共享问题。其核心场景是：

• 多个 Web 缓存代理（如 NLANR 缓存层次）之间希望共享缓存内容摘要
• 若代理 A 收到请求 R 但本地未命中，可以查询代理 B 的缓存摘要，若 B 可能有 R，则将请求转发至 B
• 标准布隆过滤器不支持删除，但缓存内容会过期，需要删除机制

Fan 等人将每个位替换为 4 位计数器（counter），从而支持删除操作。计数器溢出概率经证明为 $O(n^{-k})$，在典型工作负载下可忽略。Summary Cache 协议在 NLANR 缓存层次中实测将缓存命中率提升 30-50%。

Boldi-Vigna 1998：Web Graph 压缩

Paolo Boldi 和 Sebastiano Vigna 1998 年在 WWW 会议发表《The WebGraph Framework I: Compression Techniques》，使用布隆过滤器压缩 Web 图的邻接表表示，将 1.15 亿网页（2002 年基准）的链接图从 4 GB 压缩至 300 MB。

2.3 工业普及与变种涌现（2000s）

2000 年代是布隆过滤器工业普及的关键十年。多个重量级开源系统将其作为核心组件：

Google Bigtable（Chang et al. 2006）

Google Bigtable（OSDI 2006）使用布隆过滤器在每个 SSTable 上构建行键过滤器，查询时先检查布隆过滤器以避免无效的磁盘 I/O。Chang 等人指出，布隆过滤器将 Bigtable 的随机读延迟从 30 ms 降低至 6 ms（5 倍提升）。

Apache Cassandra（Lakshman-Malik 2010）

Apache Cassandra（最初由 Facebook 开发，2010 年成为 Apache 顶级项目）在每个 SSTable 上维护布隆过滤器，用于查询时快速判断行键是否可能存在。Lakshman-Malik 2010《Cassandra: A Decentralized Structured Storage System》ACM SIGOPS OSR 44(2):35-40 指出，布隆过滤器使 Cassandra 的负查询（查询不存在的行键）磁盘 I/O 减少 90%+。

Apache HBase

HBase（基于 Bigtable 设计的 Hadoop 生态系统数据库）支持两种布隆过滤器：

• ROW：基于行键的布隆过滤器，用于判断某行键是否可能存在于某 HFile
• ROWCOL：基于行键 + 列限定符的布隆过滤器，用于判断某单元格是否可能存在

HBase 的布隆过滤器默认假阳性率为 1%，存储在每个 HFile 的元数据中。

Google Chrome Safe Browsing（2007-）

Google Chrome 自 2007 年起使用布隆过滤器实现 Safe Browsing 功能：将恶意 URL 黑名单存储在本地布隆过滤器中，浏览器访问 URL 时先查布隆过滤器，仅在命中时才向 Google 服务器请求完整哈希校验。这一设计将浏览器的网络请求减少 99%+，绝大多数非恶意 URL 完全不需要联网校验。

Bitcoin SPV 节点（Nakamoto 2008）

Satoshi Nakamoto 在 Bitcoin 白皮书中提出 SPV（Simplified Payment Verification）节点的概念：轻客户端不需要下载完整区块链，只需下载区块头和与自身地址相关的交易。BIP 37（Bloom Filter P2P Messages）实现这一机制：

• SPV 节点构造一个布隆过滤器，包含自己关心的地址集合
• SPV 节点将布隆过滤器发送给全节点
• 全节点收到新区块时，用布隆过滤器筛选交易，仅发送匹配的 Merkle block
• 假阳性导致 SPV 节点收到一些不相关的交易，但隐私得到保护（因为布隆过滤器是概率性的，全节点无法精确推断 SPV 节点关心的地址）

2.4 学术演进：变种与理论深化（2000s-2020s）

2000 年代后，学术界提出了大量布隆过滤器变种以应对不同场景需求：

Mitzenmacher 2002：Compressed Bloom Filter

Michael Mitzenmacher 2002 年在 IEEE/ACM Transactions on Networking 10(5):604-612 发表《Compressed Bloom Filters》（DOI: 10.1109/TNET.2002.803864），解决了网络传输场景下布隆过滤器的优化问题。关键洞察是：

• 网络传输场景下，布隆过滤器在内存中保持未压缩状态，传输时压缩
• 最优的”内存中”参数与”传输后”参数不同
• 压缩后的布隆过滤器可以同时减小传输大小和假阳性率，最优设计使用比未压缩最优更少的哈希函数

Compressed Bloom Filter 是 Chrome Safe Browsing 和 Squid Cache Digests 的理论基础。

Chazelle-Kilian-Rubinfeld-Tal 2004：Bloomier Filter

Bernard Chazelle、Joe Kilian、Ronitt Rubinfeld、Ayal Tal 2004 年在 SIAM Journal on Computing 33(6):1306-1331 发表《The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables》（DOI: 10.1137/S0097539703429196），将布隆过滤器从”成员查询”推广至”关联值查询”：

• 标准布隆过滤器只能回答”是否在集合中”
• Bloomier Filter 可以回答”如果 $x$ 在集合中，其关联值 $v(x)$ 是什么”
• 利用 GF(2) 上的稀疏矩阵求解技术实现 $O(1)$ 查询，无假阳性

Bloomier Filter 在函数去重、静态字典等场景有应用。

Kirsch-Mitzenmacher 2006：Less Hashing, Same Performance

Adam Kirsch 和 Michael Mitzenmacher 2006 年在 ESA 06 发表《Less Hashing, Same Performance: Building a Better Bloom Filter》（DOI: 10.1007/11841036_42），证明一个关键工程优化：

• 用 2 个独立哈希函数 $h_1, h_2$ 可以生成 $k$ 个虚拟哈希函数 $g_i(x) = h_1(x) + i \cdot h_2(x) \bmod m$
• 这一构造在 $k$ 较小时与 $k$ 个独立哈希函数的假阳性率几乎相同
• 实践中将哈希计算数从 $k$ 降至 2，对 $k = 7$ 的典型配置速度提升 3-4 倍

这一技术被 Google Guava BloomFilter、Python pybloom、Apache Cassandra 等主流实现采用。

Fan-Andersen-Kaminsky-Kreitzberg-Plotnick 2014：Cuckoo Filter

Bin Fan、David G. Andersen、Michael Kaminsky、Mikhail D. Kreitzberg、Brian J. Plotnick 2014 年在 ACM CoNEXT 发表《Cuckoo Filter: Practically Better Than Bloom》（DOI: 10.1145/2674005.2674994），提出布谷鸟过滤器作为 Bloom Filter 与 Counting Bloom Filter 的替代方案：

• 基于 Cuckoo Hashing（Pagh-Pagh 2001）+ 指纹（fingerprint）机制
• 支持 $O(1)$ 平均插入/查询/删除
• 在 95% 装填因子下，1% 假阳性率仅需 4.48 bit/元素（Bloom 需 9.58 bit）
• 实测性能比 Counting Bloom Filter 快 2-5 倍

Cuckoo Filter 已被 Google Presto、Cloudera Impala、ScyllaDB 等系统采用。

Pang-Zhang-Wu-Liu 2009：Stable Bloom Filter

Stable Bloom Filter 专为无界数据流设计：通过持续衰减随机计数器为新元素腾出空间，达到稳定状态下的常数假阳性率，代价是非零假阴性率。适用于流式去重场景（如爬虫 URL 去重、网络流量统计）。

2.5 Mermaid 时间线

timeline
    title 布隆过滤器演进时间线
    1970 : Bloom 原始论文
         : CACM 13(7):422-426
         : 空间高效哈希编码
    1979 : Carter-Wegman
         : 通用哈希函数族
         : 独立性假设的理论基础
    1992 : Spafford
         : 口令字典过滤
         : 首次工业应用
    1998 : Fan-Cao-Almeida-Broder
         : Counting Bloom Filter
         : Summary Cache SIGCOMM
    2001 : Pagh-Pagh
         : Cuckoo Hashing
         : 后续 Cuckoo Filter 的基础
    2002 : Mitzenmacher
         : Compressed Bloom Filter
         : 网络传输优化
    2004 : Chazelle 等
         : Bloomier Filter
         : 关联值查询
    2006 : Google Bigtable
         : SSTable 布隆过滤器
         : 工业普及里程碑
    2006 : Kirsch-Mitzenmacher
         : 双哈希构造
         : 哈希计算数从 k 降至 2
    2007 : Chrome Safe Browsing
         : 恶意 URL 黑名单
         : 99%+ 网络请求减少
    2008 : Bitcoin BIP 37
         : SPV 节点布隆过滤器
         : 区块链轻客户端
    2010 : Apache Cassandra
         : SSTable 布隆过滤器
         : 负查询磁盘 I/O 减少 90%+
    2014 : Fan-Andersen-Kaminsky
         : Cuckoo Filter
         : 空间效率超越 Bloom
    2017 : Mitzenmacher-Upfal
         : 概率与计算教材
         : 理论系统化
    2020s : 现代演进
          : 学习索引 + 布隆过滤器
          : GPU 并行布隆过滤器
          : Persistent Memory 优化

2.6 知识图谱

graph TD
    A[Bloom 1970<br/>原始 Bloom Filter]
    A --> B[Counting Bloom Filter<br/>Fan 1998]
    A --> C[Compressed Bloom Filter<br/>Mitzenmacher 2002]
    A --> D[Bloomier Filter<br/>Chazelle 2004]
    A --> E[Spectral Bloom Filter<br/>Charikar 2004]
    A --> F[Stable Bloom Filter<br/>Pang 2009]
    A --> G[Counting Bloom Filter 变种<br/>Bonomi 2006]
    A --> H[Cuckoo Filter<br/>Fan 2014]

    B --> I[工业应用]
    C --> I
    H --> I

    I --> I1[Cassandra SSTable]
    I --> I2[HBase ROW/ROWCOL]
    I --> I3[Chrome Safe Browsing]
    I --> I4[Bitcoin SPV]
    I --> I5[Squid Cache Digests]
    I --> I6[PostgreSQL Bloom Index]
    I --> I7[Google Bigtable]
    I --> I8[Redis BF Module]

    A --> J[理论分析]
    J --> J1[Carter-Wegman 1979<br/>通用哈希]
    J --> J2[Kirsch-Mitzenmacher 2006<br/>双哈希构造]
    J --> J3[Pagh-Pagh-Ruzic 2005<br/>线性探测常数独立性]
    J --> J4[Mitzenmacher-Upfal 2017<br/>泊松近似框架]

3. 形式化定义

3.1 基本定义

定义 1（布隆过滤器）：给定参数 $(m, k, H)$，其中：

• $m \in \mathbb{N}^+$ 为位数组大小
• $k \in \mathbb{N}^+$ 为哈希函数个数
• $H = \{h_1, h_2, \ldots, h_k\}$ 为哈希函数族，每个 $h_i: U \to \{0, 1, \ldots, m-1\}$ 是从全域 $U$ 到 $\{0, 1, \ldots, m-1\}$ 的均匀独立哈希函数

布隆过滤器是元组 $(\mathbf{B}, H)$，其中 $\mathbf{B} \in \{0, 1\}^m$ 为位数组，初始时 $\mathbf{B}[i] = 0, \forall i \in [0, m-1]$。

定义 2（插入操作）：插入元素 $x \in U$ 的操作 $\texttt{insert}(x)$ 定义为：

$\texttt{insert}(x): \quad \forall i \in [1, k], \quad \mathbf{B}[h_i(x)] \leftarrow 1$

定义 3（查询操作）：查询元素 $y \in U$ 的操作 $\texttt{query}(y) \in \{\texttt{true}, \texttt{false}\}$ 定义为：

$\texttt{query}(y) = \bigwedge_{i=1}^{k} \mathbf{B}[h_i(y)]$

即”当且仅当 $y$ 的所有 $k$ 个哈希位置都为 1 时返回 true，否则返回 false”。

3.2 集合表示语义

给定插入集合 $S = \{x_1, x_2, \ldots, x_n\}$，插入所有元素后的位数组状态为：

$\mathbf{B}_S[j] = \bigvee_{i=1}^{n} \bigvee_{l=1}^{k} \mathbb{1}[h_l(x_i) = j], \quad \forall j \in [0, m-1]$

其中 $\mathbb{1}[\cdot]$ 为指示函数。即位数组位置 $j$ 为 1 当且仅当存在某个插入元素 $x_i$ 和某个哈希函数 $h_l$ 使得 $h_l(x_i) = j$。

3.3 假阳性率的形式化定义

定义 4（假阳性率）：给定插入集合 $S$（$|S| = n$）和查询元素 $y \notin S$，假阳性率 $\epsilon$ 定义为：

$\epsilon \triangleq \Pr[\texttt{query}(y) = \texttt{true} \mid y \notin S]$

定义 5（假阴性率）：假阴性率 $\eta$ 定义为：

$\eta \triangleq \Pr[\texttt{query}(y) = \texttt{false} \mid y \in S]$

定理 1（无假阴性）：对于标准布隆过滤器，$\eta = 0$。

证明：设 $x \in S$，则插入 $x$ 时已将 $\mathbf{B}[h_i(x)] = 1$ 对所有 $i \in [1, k]$ 成立。由于插入操作只置位不清位，查询 $x$ 时所有 $\mathbf{B}[h_i(x)]$ 仍为 1，故 $\texttt{query}(x) = \texttt{true}$。$\square$

3.4 哈希函数族的独立性假设

布隆过滤器的理论分析依赖于哈希函数族的独立性假设（independence assumption）：

假设 1（简单均匀性）：每个 $h_i$ 是简单均匀哈希函数，即对任意 $x \in U$ 和 $j \in [0, m-1]$：

$\Pr[h_i(x) = j] = \frac{1}{m}$

假设 2（k—wise 独立性）：哈希函数 $h_1, h_2, \ldots, h_k$ 是 $k$-wise 独立的，即对任意 $k$ 个不同的元素 $x_1, x_2, \ldots, x_k \in U$ 和任意 $k$ 个位置 $j_1, j_2, \ldots, j_k \in [0, m-1]$：

$\Pr\left[\bigwedge_{i=1}^{k} h_i(x_i) = j_i\right] = \prod_{i=1}^{k} \Pr[h_i(x_i) = j_i] = \frac{1}{m^k}$

实践中的哈希函数：

• MurmurHash3（mmh3）：非加密哈希，速度极快，广泛用于布隆过滤器实现（Google Guava、Apache Cassandra）
• FNV-1a：简单快速的位运算哈希，常用于字符串场景
• 双哈希构造（Kirsch-Mitzenmacher 2006）：用 $g_i(x) = h_1(x) + i \cdot h_2(x) \bmod m$ 生成 $k$ 个虚拟哈希函数，仅需 2 个基础哈希
• 加密哈希（SHA-1、MD5）：用于安全敏感场景（如 Bitcoin SPV），但性能开销是 mmh3 的 10-100 倍

理论上，Carter-Wegman 1979 通用哈希族（universal hash family）已足以保证布隆过滤器假阳性率上界；Pagh-Pagh-Ruzic 2005 证明 5-wise 独立性即可使线性探测达到 $O(1)$ 期望时间，对布隆过滤器分析同样适用。

3.5 符号约定

本章使用以下符号约定：

4. 理论推导

4.1 假阳性率的精确推导

考虑查询一个不在集合中的元素 $y \notin S$。假阳性发生当且仅当 $\mathbf{B}[h_1(y)], \mathbf{B}[h_2(y)], \ldots, \mathbf{B}[h_k(y)]$ 全为 1。

步骤 1：单个位为 0 的概率

考虑位数组的某个特定位置 $j \in [0, m-1]$。位置 $j$ 在插入 $n$ 个元素后仍为 0 的概率，等于”对每个元素 $x_i$ 和每个哈希函数 $h_l$，都有 $h_l(x_i) \neq j$“的概率。

对单个元素 $x_i$ 和单个哈希函数 $h_l$：

$\Pr[h_l(x_i) = j] = \frac{1}{m}$

故：

$\Pr[h_l(x_i) \neq j] = 1 - \frac{1}{m}$

由于 $k$ 个哈希函数独立，对单个元素 $x_i$ 的 $k$ 次哈希都不命中 $j$ 的概率为：

$\Pr\left[\bigwedge_{l=1}^{k} h_l(x_i) \neq j\right] = \left(1 - \frac{1}{m}\right)^k$

由于 $n$ 个元素互相独立，所有 $n$ 个元素的 $kn$ 次哈希都不命中 $j$ 的概率为：

$\Pr[\mathbf{B}[j] = 0] = \left(1 - \frac{1}{m}\right)^{kn}$

步骤 2：单个位为 1 的概率

$\Pr[\mathbf{B}[j] = 1] = 1 - \left(1 - \frac{1}{m}\right)^{kn}$

步骤 3：假阳性率

由于 $y \notin S$，且哈希函数对 $y$ 的输出独立于对 $S$ 中元素的输出，故 $h_1(y), h_2(y), \ldots, h_k(y)$ 这 $k$ 个位置（在 $y \notin S$ 的条件下）独立服从”位置为 1 的概率为 $1 - (1 - 1/m)^{kn}$“的伯努利分布。但这 $k$ 个位置可能重复（即 $h_i(y) = h_l(y)$ 对 $i \neq l$），独立性需要更细致的论证。

在实践中（$m \gg k^2$），$k$ 个位置重复的概率可忽略，故近似有：

$\epsilon = \Pr[\texttt{query}(y) = \texttt{true} \mid y \notin S] \approx \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k$

步骤 4：极限近似

当 $m$ 较大时，利用 $(1 - 1/m)^m \to e^{-1}$（$m \to \infty$），有：

$\left(1 - \frac{1}{m}\right)^{kn} = \left[\left(1 - \frac{1}{m}\right)^m\right]^{kn/m} \approx e^{-kn/m}$

故假阳性率的近似公式为：

$\boxed{\epsilon \approx \left(1 - e^{-kn/m}\right)^k}$

这是布隆过滤器最常用的假阳性率公式，由 Bloom 1970 原论文给出，后经 Broder-Mitzenmacher 2003《Network Applications of Bloom Filters: A Survey》Internet Mathematics 1(4):485-509 系统化推导。

4.2 最优哈希函数个数

给定 $m$ 和 $n$，如何选择 $k$ 使假阳性率 $\epsilon$ 最小？这是一个一元函数极值问题。

设 $x = kn/m$，则 $\epsilon = (1 - e^{-x})^k = (1 - e^{-x})^{xm/n}$。取对数：

$\ln \epsilon = \frac{xm}{n} \ln(1 - e^{-x})$

对 $x$ 求导并令其为 0：

$\frac{d \ln \epsilon}{dx} = \frac{m}{n} \left[\ln(1 - e^{-x}) + x \cdot \frac{e^{-x}}{1 - e^{-x}}\right] = 0$

化简得：

$\ln(1 - e^{-x}) + \frac{x e^{-x}}{1 - e^{-x}} = 0$

设 $y = e^{-x}$，则 $1 - y = 1 - e^{-x}$，方程变为：

$\ln(1 - y) + \frac{-y \ln y}{1 - y} = 0$

试 $y = 1/2$：

$\ln(1/2) + \frac{-(1/2) \ln(1/2)}{1/2} = -\ln 2 + \ln 2 = 0 \checkmark$

故 $y = 1/2$，即 $e^{-x} = 1/2$，$x = \ln 2$，亦即 $kn/m = \ln 2$。最终：

$\boxed{k_{\text{opt}} = \frac{m}{n} \ln 2 \approx 0.693 \cdot \frac{m}{n}}$

验证二阶导数：经计算 $\frac{d^2 \ln \epsilon}{dx^2} > 0$，故 $x = \ln 2$ 是极小值点。

代入最优 $k$ 后的假阳性率：

当 $k = k_{\text{opt}}$ 时，$kn/m = \ln 2$，$e^{-kn/m} = 1/2$，故：

$\epsilon_{\text{opt}} = (1 - 1/2)^{k_{\text{opt}}} = (1/2)^{k_{\text{opt}}} = (1/2)^{(m/n) \ln 2}$

利用 $a^b = e^{b \ln a}$：

$\epsilon_{\text{opt}} = e^{(m/n) (\ln 2)^2 \cdot (-1)} = e^{-(m/n) (\ln 2)^2} \approx 0.6185^{m/n}$

注意 $(1/2)^{\ln 2} = e^{-(\ln 2)^2} \approx e^{-0.4805} \approx 0.6185$，即黄金比例的倒数。

4.3 最优位数组大小

给定 $n$ 和目标假阳性率 $\epsilon$，如何选择 $m$？

利用最优 $k$ 下的 $\epsilon_{\text{opt}} = e^{-(m/n)(\ln 2)^2}$，解出 $m$：

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

$m = -\frac{n \ln \epsilon}{(\ln 2)^2} \approx -1.4427 \cdot n \ln \epsilon$

即：

$\boxed{m_{\text{opt}} = -\frac{n \ln \epsilon}{(\ln 2)^2} \approx -1.4427 \cdot n \ln \epsilon}$

每元素所需 bit 数：

$\frac{m_{\text{opt}}}{n} = -\frac{\ln \epsilon}{(\ln 2)^2} \approx -1.4427 \ln \epsilon$

代入常见 $\epsilon$：

可以看到：

• 每元素所需 bit 数与 $\log(1/\epsilon)$ 成正比
• 哈希函数个数与 $m/n$ 成正比
• 假阳性率每降低一个数量级，每元素仅需多约 4.8 bit

4.4 时间复杂度分析

插入复杂度：插入元素 $x$ 需要计算 $k$ 个哈希函数并执行 $k$ 次位数组写入，时间复杂度为：

$T_{\text{insert}} = O(k)$

查询复杂度：查询元素 $y$ 需要计算 $k$ 个哈希函数并执行最多 $k$ 次位数组读取，时间复杂度为：

$T_{\text{query}} = O(k)$

空间复杂度：位数组占用 $m$ bit 内存，空间复杂度为：

$S = O(m) \text{ bit}$

注意空间单位是 bit 而非 byte，1 亿元素 1% 假阳性率仅需 $9.585 \times 10^8 \text{ bit} \approx 120$ MB。

4.5 哈希函数独立性的影响

实际实现中哈希函数不可能完全独立，假阳性率会偏离理论值。Mitzenmacher-Upfal 2017《Probability and Computing》Chapter 5 给出严格上界：

定理 2：若哈希函数族 $H$ 是 $k$-wise 独立的，则假阳性率上界为：

$\epsilon \leq \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k + O\left(\frac{k^2}{m}\right)$

即 $k$-wise 独立性下假阳性率与理论值的偏差为 $O(k^2/m)$。当 $m \gg k^2$（典型场景下 $m = 10^8$，$k = 7$，$k^2/m \approx 5 \times 10^{-7}$），偏差可忽略。

定理 3（Carter-Wegman 1979）：2-wise 独立（即通用哈希族）已足以保证：

$\mathbb{E}[\epsilon] = \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k$

即假阳性率的期望与完全独立情形相同，但方差可能较大。实践中通常使用 3-wise 或 5-wise 独立哈希族以平衡性能与精度。

4.6 推论：假阳性率的 Chernoff 上界

利用 Chernoff 不等式可以证明假阳性率以高概率集中在其期望附近：

定理 4：对任意 $\delta > 0$，

$\Pr\left[\epsilon > (1 + \delta) \mathbb{E}[\epsilon]\right] \leq e^{-\Omega(n \delta^2)}$

即假阳性率以指数速度集中在其期望值附近，对 $n = 10^6$ 量级的实际应用，假阳性率与理论值的偏差可以忽略。

4.7 下界：空间最优性

定理 5（空间下界）：任何表示 $n$ 个元素集合、假阳性率为 $\epsilon$ 的数据结构至少需要：

$m \geq n \log_2(1/\epsilon) - O(n) \text{ bit}$

即每元素至少需要 $\log_2(1/\epsilon) - O(1)$ bit。

布隆过滤器在最优 $k$ 下使用 $m/n = -\ln \epsilon / (\ln 2)^2 \approx 1.44 \log_2(1/\epsilon)$ bit/元素，与下界相差常数因子 $1.44$。Cuckoo Filter（Fan et al. 2014）将这一因子降至接近 1.0，是空间更优的替代方案。

4.8 摊还分析视角

虽然单次插入/查询的时间复杂度是 $O(k)$，但 $k$ 的最优值由 $k_{\text{opt}} = (m/n) \ln 2$ 决定，与 $n$ 无关（在 $m/n$ 固定时）。因此布隆过滤器的操作时间是与元素数无关的常数，这一性质对大规模数据处理至关重要。

5. 代码示例

5.1 Python 实现：标准布隆过滤器

下面是一个生产级的布隆过滤器 Python 实现，使用 mmh3（MurmurHash3）作为基础哈希函数，并采用 Kirsch-Mitzenmacher 2006 双哈希构造以减少哈希计算开销：

import math
import mmh3
from typing import Any, Iterable


class BloomFilter:
    """布隆过滤器（Bloom Filter）

    基于 Bloom 1970 CACM 13(7):422-426 的设计，
    使用 Kirsch-Mitzenmacher 2006 ESA 06 双哈希构造以减少哈希计算数。

    参数:
        capacity: 预期插入元素数 n
        error_rate: 目标假阳性率 epsilon
    """

    def __init__(self, capacity: int, error_rate: float = 0.01) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        if not 0 < error_rate < 1:
            raise ValueError("error_rate must be in (0, 1)")

        self.capacity = capacity
        self.error_rate = error_rate

        # 计算最优位数组大小 m = -n*ln(epsilon) / (ln 2)^2
        self.bit_size = self._optimal_bit_size(capacity, error_rate)
        # 计算最优哈希函数个数 k = (m/n) * ln 2
        self.hash_count = self._optimal_hash_count(self.bit_size, capacity)
        # 使用 bytearray 存储，每个字节 8 位
        self.bit_array = bytearray(math.ceil(self.bit_size / 8))
        # 已插入元素计数（用于动态监控假阳性率）
        self.count = 0

    @staticmethod
    def _optimal_bit_size(n: int, p: float) -> int:
        """计算最优位数组大小 m = -n*ln(p) / (ln 2)^2"""
        return int(-n * math.log(p) / (math.log(2) ** 2))

    @staticmethod
    def _optimal_hash_count(m: int, n: int) -> int:
        """计算最优哈希函数个数 k = (m/n) * ln 2，至少为 1"""
        return max(1, int((m / n) * math.log(2)))

    def _double_hashing(self, item: Any, i: int) -> int:
        """Kirsch-Mitzenmacher 双哈希构造

        g_i(x) = (h1(x) + i * h2(x)) mod m

        仅需 2 次哈希计算即可生成 k 个虚拟哈希函数。
        """
        # mmh3.hash128 返回 128 位哈希，分为两个 64 位整数
        h1, h2 = mmh3.hash64(str(item), signed=False)
        return (h1 + i * h2) % self.bit_size

    def add(self, item: Any) -> None:
        """插入元素：将 k 个哈希位置全部置 1"""
        for i in range(self.hash_count):
            idx = self._double_hashing(item, i)
            byte_idx = idx >> 3
            bit_offset = idx & 7
            self.bit_array[byte_idx] |= (1 << bit_offset)
        self.count += 1

    def __contains__(self, item: Any) -> bool:
        """查询元素：检查 k 个哈希位置是否全为 1

        返回 False：元素一定不在集合中（无假阴性）
        返回 True：元素可能在集合中（有假阳性）
        """
        for i in range(self.hash_count):
            idx = self._double_hashing(item, i)
            byte_idx = idx >> 3
            bit_offset = idx & 7
            if not (self.bit_array[byte_idx] & (1 << bit_offset)):
                return False
        return True

    def estimated_false_positive_rate(self) -> float:
        """根据当前元素数估算实际假阳性率

        epsilon = (1 - e^(-k*n/m))^k
        """
        return (1 - math.exp(-self.hash_count * self.count / self.bit_size)) ** self.hash_count

    def __len__(self) -> int:
        return self.count

    def __repr__(self) -> str:
        return (
            f"BloomFilter(capacity={self.capacity}, "
            f"error_rate={self.error_rate}, "
            f"bit_size={self.bit_size}, "
            f"hash_count={self.hash_count}, "
            f"count={self.count})"
        )


# 使用示例
if __name__ == "__main__":
    # 创建 100 万元素容量、1% 假阳性率的布隆过滤器
    bf = BloomFilter(capacity=1_000_000, error_rate=0.01)
    print(bf)
    # 输出: BloomFilter(capacity=1000000, error_rate=0.01,
    #       bit_size=9585059, hash_count=6, count=0)

    # 插入元素
    bf.add("user:1001")
    bf.add("user:1002")
    bf.add("user:1003")

    # 查询存在的元素
    assert "user:1001" in bf  # True，一定在
    assert "user:1002" in bf  # True，一定在

    # 查询不存在的元素
    assert "user:9999" not in bf  # True，一定不在（无假阴性）

    print(f"估算假阳性率: {bf.estimated_false_positive_rate():.6f}")
    # 输出: 估算假阳性率: 0.000000（元素数远小于容量时假阳性率极低）

5.2 Python 实现：Counting Bloom Filter（支持删除）

import math
import mmh3
from typing import Any


class CountingBloomFilter:
    """Counting Bloom Filter（CBF）

    基于 Fan-Cao-Almeida-Broder 1998 SIGCOMM《Summary Cache》的设计。
    将每个位替换为 4 位计数器，支持元素删除操作。

    计数器溢出处理：采用饱和计数器（saturating counter），
    计数器达到最大值后不再增加，删除时若已达最大值则不减少。

    参数:
        capacity: 预期插入元素数 n
        error_rate: 目标假阳性率 epsilon
        counter_bits: 单个计数器位数（默认 4，最大支持 15）
    """

    def __init__(
        self,
        capacity: int,
        error_rate: float = 0.01,
        counter_bits: int = 4,
    ) -> None:
        if counter_bits not in (2, 4, 8, 16):
            raise ValueError("counter_bits must be 2, 4, 8, or 16")

        self.capacity = capacity
        self.error_rate = error_rate
        self.counter_bits = counter_bits
        self.max_counter = (1 << counter_bits) - 1

        # 计算最优参数
        m = self._optimal_bit_size(capacity, error_rate)
        k = max(1, int((m / capacity) * math.log(2)))

        self.bit_size = m
        self.hash_count = k
        # 使用整数列表存储计数器
        self.counters = [0] * m
        self.count = 0

    @staticmethod
    def _optimal_bit_size(n: int, p: float) -> int:
        return int(-n * math.log(p) / (math.log(2) ** 2))

    def _double_hashing(self, item: Any, i: int) -> int:
        h1, h2 = mmh3.hash64(str(item), signed=False)
        return (h1 + i * h2) % self.bit_size

    def add(self, item: Any) -> None:
        """插入元素：将 k 个哈希位置的计数器加 1（饱和）"""
        for i in range(self.hash_count):
            idx = self._double_hashing(item, i)
            if self.counters[idx] < self.max_counter:
                self.counters[idx] += 1
        self.count += 1

    def remove(self, item: Any) -> bool:
        """删除元素：将 k 个哈希位置的计数器减 1

        返回 True: 删除成功
        返回 False: 元素可能不在过滤器中（不应删除）
        """
        # 先检查元素是否存在，避免误删其他元素的计数
        if not self.__contains__(item):
            return False

        for i in range(self.hash_count):
            idx = self._double_hashing(item, i)
            if self.counters[idx] > 0 and self.counters[idx] < self.max_counter:
                self.counters[idx] -= 1
        self.count -= 1
        return True

    def __contains__(self, item: Any) -> bool:
        for i in range(self.hash_count):
            idx = self._double_hashing(item, i)
            if self.counters[idx] == 0:
                return False
        return True

    def __len__(self) -> int:
        return self.count


# 使用示例
if __name__ == "__main__":
    cbf = CountingBloomFilter(capacity=100_000, error_rate=0.01, counter_bits=4)

    cbf.add("apple")
    cbf.add("banana")
    assert "apple" in cbf

    # 删除元素
    assert cbf.remove("apple") is True
    assert "apple" not in cbf  # 删除后查询返回 False

5.3 C++ 实现：高性能布隆过滤器

#include <cstdint>
#include <vector>
#include <string>
#include <cmath>
#include <stdexcept>
#include <functional>
#include <iostream>

// 高性能布隆过滤器实现
// 使用 MurmurHash3 替代品：FNV-1a + std::hash 双哈希构造
class BloomFilter {
public:
    // 构造函数：根据预期容量与目标假阳性率自动计算最优参数
    // capacity: 预期插入元素数 n
    // error_rate: 目标假阳性率 epsilon
    BloomFilter(size_t capacity, double error_rate = 0.01)
        : capacity_(capacity), error_rate_(error_rate) {
        if (capacity == 0) throw std::invalid_argument("capacity must be positive");
        if (error_rate <= 0 || error_rate >= 1)
            throw std::invalid_argument("error_rate must be in (0, 1)");

        // 计算最优位数组大小 m = -n*ln(p) / (ln 2)^2
        bit_size_ = static_cast<size_t>(
            -static_cast<double>(capacity) * std::log(error_rate) /
            (std::log(2) * std::log(2))
        );
        // 计算最优哈希函数个数 k = (m/n) * ln 2
        hash_count_ = std::max(1UL, static_cast<size_t>(
            static_cast<double>(bit_size_) / capacity * std::log(2)
        ));
        // 分配位数组（按字节对齐）
        bit_array_.assign((bit_size_ + 7) / 8, 0);
        count_ = 0;
    }

    // 插入元素
    void add(const std::string& item) {
        uint64_t h1, h2;
        double_hashing_seed(item, h1, h2);
        for (size_t i = 0; i < hash_count_; ++i) {
            size_t idx = (h1 + i * h2) % bit_size_;
            bit_array_[idx >> 3] |= (1ULL << (idx & 7));
        }
        ++count_;
    }

    // 查询元素
    bool contains(const std::string& item) const {
        uint64_t h1, h2;
        double_hashing_seed(item, h1, h2);
        for (size_t i = 0; i < hash_count_; ++i) {
            size_t idx = (h1 + i * h2) % bit_size_;
            if (!(bit_array_[idx >> 3] & (1ULL << (idx & 7)))) {
                return false;
            }
        }
        return true;
    }

    // 估算当前假阳性率
    double estimated_fpr() const {
        double exponent = -static_cast<double>(hash_count_) * count_ / bit_size_;
        return std::pow(1.0 - std::exp(exponent), static_cast<double>(hash_count_));
    }

    size_t bit_size() const { return bit_size_; }
    size_t hash_count() const { return hash_count_; }
    size_t count() const { return count_; }

private:
    // 双哈希构造（Kirsch-Mitzenmacher 2006）
    // 使用 FNV-1a 与 std::hash 作为两个独立哈希函数
    void double_hashing_seed(const std::string& item,
                              uint64_t& h1, uint64_t& h2) const {
        // FNV-1a 64-bit
        const uint64_t FNV_OFFSET = 14695981039346656037ULL;
        const uint64_t FNV_PRIME = 1099511628211ULL;
        h1 = FNV_OFFSET;
        for (unsigned char c : item) {
            h1 ^= c;
            h1 *= FNV_PRIME;
        }
        // std::hash 作为第二哈希函数
        h2 = std::hash<std::string>{}(item);
    }

    size_t capacity_;
    double error_rate_;
    size_t bit_size_;
    size_t hash_count_;
    std::vector<uint8_t> bit_array_;
    size_t count_;
};

int main() {
    BloomFilter bf(1'000'000, 0.01);
    std::cout << "bit_size=" << bf.bit_size() << ", hash_count=" << bf.hash_count() << "\n";
    // 输出: bit_size=9585059, hash_count=6

    bf.add("user:1001");
    bf.add("user:1002");

    std::cout << "contains user:1001? " << bf.contains("user:1001") << "\n";  // 1
    std::cout << "contains user:9999? " << bf.contains("user:9999") << "\n";  // 0

    std::cout << "estimated FPR: " << bf.estimated_fpr() << "\n";
    return 0;
}

5.4 Java 实现：并发安全布隆过滤器

import java.util.BitSet;
import java.util.Objects;
import java.util.concurrent.atomic.AtomicLong;
import java.util.function.Function;

/**
 * 并发安全布隆过滤器实现
 * 使用 BitSet + ReadWriteLock 实现多线程安全的查询与插入。
 * 适用于高并发场景如缓存穿透防护。
 */
public class ConcurrentBloomFilter<T> {

    private final BitSet bitSet;
    private final int bitSize;
    private final int hashCount;
    private final AtomicLong count = new AtomicLong(0);
    private final Function<T, Long> hash1;
    private final Function<T, Long> hash2;

    /**
     * 构造布隆过滤器
     * @param capacity 预期元素数 n
     * @param errorRate 目标假阳性率 epsilon
     */
    public ConcurrentBloomFilter(long capacity, double errorRate) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        if (errorRate <= 0 || errorRate >= 1)
            throw new IllegalArgumentException("errorRate must be in (0, 1)");

        this.bitSize = (int) Math.ceil(
            -capacity * Math.log(errorRate) / (Math.log(2) * Math.log(2))
        );
        this.hashCount = Math.max(1, (int) Math.round(
            (double) bitSize / capacity * Math.log(2)
        ));
        this.bitSet = new BitSet(bitSize);

        // 使用 FNV-1a 与 String.hashCode 作为双哈希
        this.hash1 = item -> fnv1a64(item.toString());
        this.hash2 = item -> (long) item.hashCode() & 0xFFFFFFFFL;
    }

    /** 插入元素 */
    public synchronized void add(T item) {
        Objects.requireNonNull(item);
        long h1 = hash1.apply(item);
        long h2 = hash2.apply(item);
        for (int i = 0; i < hashCount; i++) {
            int idx = (int) ((h1 + i * h2) % bitSize);
            if (idx < 0) idx += bitSize;
            bitSet.set(idx);
        }
        count.incrementAndGet();
    }

    /** 查询元素（无锁读，可能读到部分写入的状态，但对 false 返回是保守的） */
    public boolean mightContain(T item) {
        Objects.requireNonNull(item);
        long h1 = hash1.apply(item);
        long h2 = hash2.apply(item);
        for (int i = 0; i < hashCount; i++) {
            int idx = (int) ((h1 + i * h2) % bitSize);
            if (idx < 0) idx += bitSize;
            if (!bitSet.get(idx)) {
                return false;
            }
        }
        return true;
    }

    public long count() { return count.get(); }
    public int bitSize() { return bitSize; }
    public int hashCount() { return hashCount; }

    /** FNV-1a 64-bit 哈希 */
    private static long fnv1a64(String s) {
        final long FNV_OFFSET = -3750763034362895579L;  // 0xcbf29ce484222325
        final long FNV_PRIME = 1099511628211L;
        long hash = FNV_OFFSET;
        for (int i = 0; i < s.length(); i++) {
            hash ^= s.charAt(i);
            hash *= FNV_PRIME;
        }
        return hash;
    }

    public static void main(String[] args) {
        ConcurrentBloomFilter<String> bf = new ConcurrentBloomFilter<>(1_000_000, 0.01);
        System.out.println("bitSize=" + bf.bitSize() + ", hashCount=" + bf.hashCount());

        bf.add("user:1001");
        bf.add("user:1002");

        System.out.println("contains user:1001? " + bf.mightContain("user:1001"));  // true
        System.out.println("contains user:9999? " + bf.mightContain("user:9999"));  // false
    }
}

5.5 Redis 布隆过滤器模块

Redis 4.0+ 通过 RedisBloom 模块提供原生布隆过滤器支持，适用于分布式场景：

# 创建布隆过滤器
# BF.RESERVE <key> <error_rate> <capacity>
BF.RESERVE my_filter 0.001 1000000
# OK

# 插入元素
# BF.ADD <key> <item>
BF.ADD my_filter "user:1001"
# (integer) 1   # 表示新增了元素

BF.ADD my_filter "user:1002"
# (integer) 1

BF.ADD my_filter "user:1001"
# (integer) 0   # 元素已存在，无新增

# 查询单个元素
# BF.EXISTS <key> <item>
BF.EXISTS my_filter "user:1001"
# (integer) 1   # 可能在

BF.EXISTS my_filter "user:9999"
# (integer) 0   # 一定不在

# 批量插入
BF.MADD my_filter "user:1003" "user:1004" "user:1005"
# 1) (integer) 1
# 2) (integer) 1
# 3) (integer) 1

# 批量查询
BF.MEXISTS my_filter "user:1001" "user:9999" "user:1002"
# 1) (integer) 1
# 2) (integer) 0
# 3) (integer) 1

# 查看过滤器信息
BF.INFO my_filter
# 1) Capacity
# 2) (integer) 1000000
# 3) Size
# 4) (integer) 2048072
# 5) FilterNum
# 6) (integer) 1
# 7) ItemsInserted
# 8) (integer) 5
# 9) ExpansionRate
# 10) (integer) 2

5.6 Google Guava BloomFilter（Java 生产级实现）

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.StandardCharsets;

public class GuavaBloomFilterExample {
    public static void main(String[] args) {
        // 创建预期 100 万元素、1% 假阳性率的布隆过滤器
        BloomFilter<String> filter = BloomFilter.create(
            Funnels.stringFunnel(StandardCharsets.UTF_8),
            1_000_000,
            0.01
        );

        // 插入元素
        filter.put("user:1001");
        filter.put("user:1002");

        // 查询
        System.out.println(filter.mightContain("user:1001"));  // true
        System.out.println(filter.mightContain("user:9999"));  // false

        // 估算假阳性率
        System.out.println("approximate FPR: " + filter.expectedFpp());
    }
}

Guava BloomFilter 内部使用 MurmurHash3 + Kirsch-Mitzenmacher 双哈希构造，是 Java 生态事实标准。

6. 对比分析

6.1 与同类数据结构的对比

布隆过滤器不是唯一的空间高效数据结构，需要根据具体场景选择：

6.2 Bloom Filter vs Cuckoo Filter

Cuckoo Filter（Fan et al. 2014 ACM CoNEXT）是布隆过滤器的主要竞争者，对比关键维度：

何时选 Bloom Filter：

• 不需要删除的场景（如静态集合查询）
• 实现简单性优先
• 已有 Redis BloomFilter、Guava BloomFilter 等成熟实现
• 集合大小固定，参数已知

何时选 Cuckoo Filter：

• 需要频繁删除的场景
• 空间敏感（如嵌入式设备、移动端）
• 高性能查询（缓存友好性影响实测性能 2-5 倍）
• 集合动态变化，需要扩容

6.3 Bloom Filter vs Hash Set

结论：Hash Set 适用于需要精确查询、删除、计数、枚举的场景；Bloom Filter 适用于空间敏感、可容忍假阳性、仅需要成员查询的预处理场景。

6.4 Bloom Filter vs HyperLogLog

结论：HyperLogLog 适用于”统计独立元素数量”的场景（如网站 UV 统计），而 Bloom Filter 适用于”查询特定元素是否在集合中”的场景。两者互补而非替代。

7. 常见陷阱

7.1 陷阱 1：哈希函数选择不当

错误示例：

# 错误：使用 Python 内置 hash() 作为布隆过滤器哈希函数
class BadBloomFilter:
    def __init__(self, m, k):
        self.m = m
        self.k = k
        self.bits = bytearray(m // 8)

    def add(self, x):
        for i in range(self.k):
            # 危险：hash() 在不同 Python 进程中返回不同值（PYTHONHASHSEED 随机化）
            # 同一进程内不同字符串的 hash() 分布也不均匀
            idx = hash(f"{x}_{i}") % self.m
            self.bits[idx // 8] |= (1 << (idx % 8))

错误原因：

1. hash() 在 Python 3 中默认启用 PYTHONHASHSEED 随机化，不同进程的哈希值不同，导致持久化布隆过滤器失效
2. hash(f"{x}_{i}") 不是独立哈希函数族，相邻 $i$ 的哈希值相关性高
3. hash() 设计目标是哈希表冲突最小化，不是密码学均匀分布

修正方案：使用 mmh3、FNV-1a 等确定性哈希函数，并采用 Kirsch-Mitzenmacher 双哈希构造：

import mmh3

class GoodBloomFilter:
    def __init__(self, m, k):
        self.m = m
        self.k = k
        self.bits = bytearray(m // 8)

    def _hashes(self, x):
        # 双哈希构造：仅需 2 次哈希计算
        h1, h2 = mmh3.hash64(str(x), signed=False)
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, x):
        for idx in self._hashes(x):
            self.bits[idx // 8] |= (1 << (idx % 8))

:::danger 警示：生产环境绝不要使用 hash()、Object.hashCode() 等语言内置哈希函数实现布隆过滤器。这些函数的分布质量、确定性和独立性均无法保证。 :::

7.2 陷阱 2：参数估算错误导致假阳性率激增

错误示例：

# 错误：用当前元素数而非容量计算假阳性率
bf = BloomFilter(capacity=1_000_000, error_rate=0.01)
# 实际插入了 500 万元素（远超容量）
for i in range(5_000_000):
    bf.add(f"user:{i}")

# 实际假阳性率已超过 50%（远超设计的 1%）

错误原因：

布隆过滤器的假阳性率公式 $\epsilon = (1 - e^{-kn/m})^k$ 中，$n$ 是实际插入元素数。当 $n$ 超过设计容量时，$kn/m$ 增大，$e^{-kn/m}$ 减小，$1 - e^{-kn/m}$ 接近 1，故 $\epsilon$ 接近 $1^k = 1$。

修正方案：

1. 预估容量时留 2 倍余量：若预期插入 100 万元素，按 200 万元素设计容量
2. 动态监控假阳性率：实时记录元素数，超过容量阈值时触发扩容或重建
3. 使用 Scalable Bloom Filter：自动扩容的布隆过滤器变种，见 Almeida et al. 2007

class SafeBloomFilter:
    def __init__(self, capacity, error_rate=0.01):
        # 预留 2 倍余量
        self.actual_capacity = capacity * 2
        self.bf = BloomFilter(self.actual_capacity, error_rate)
        self.warning_threshold = capacity  # 达到原始容量时报警

    def add(self, x):
        if self.bf.count >= self.warning_threshold:
            # 触发告警：实际假阳性率可能已超过设计值
            import logging
            logging.warning(
                f"BloomFilter 达到容量阈值 {self.warning_threshold}，"
                f"实际假阳性率约 {self.bf.estimated_false_positive_rate():.4f}"
            )
        self.bf.add(x)

7.3 陷阱 3：标准布隆过滤器误用于需要删除的场景

错误示例：

# 错误：直接清位实现"删除"
class UnsafeBloomFilter:
    def remove(self, x):
        for i in range(self.k):
            idx = self._hash(x, i)
            # 危险：清位会影响其他元素的哈希位置
            self.bits[idx // 8] &= ~(1 << (idx % 8))

错误原因：

布隆过滤器的一个位可能被多个元素的哈希函数同时命中。直接清位会导致假阴性——其他元素的查询返回 false，违反了布隆过滤器的核心保证。

修正方案：使用 Counting Bloom Filter：

class SafeCountingBloomFilter:
    def remove(self, x):
        # 先检查元素是否存在
        if x not in self:
            return False
        # 仅减少计数，不清零
        for i in range(self.hash_count):
            idx = self._double_hashing(x, i)
            if self.counters[idx] > 0:
                self.counters[idx] -= 1
        return True

:::danger 警示：标准布隆过滤器绝对不支持删除。需要删除功能时，必须使用 Counting Bloom Filter、Cuckoo Filter 等支持删除的变种。 :::

7.4 陷阱 4：哈希函数族不独立导致假阳性率偏离理论值

错误示例：

# 错误：用同一个哈希函数加 seed 模拟"独立"哈希函数
def bad_hash_family(x, k):
    return [mmh3.hash(str(x), seed=i) for i in range(k)]

错误原因：

mmh3 的 seed 参数只是改变初始状态，不同 seed 产生的哈希函数相关性较高，不满足 $k$-wise 独立性。实测假阳性率可能比理论值高 2-5 倍。

修正方案：使用 Kirsch-Mitzenmacher 双哈希构造，仅需 2 个独立基础哈希：

def good_hash_family(x, k, m):
    h1, h2 = mmh3.hash64(str(x), signed=False)
    return [(h1 + i * h2) % m for i in range(k)]

7.5 陷阱 5：并发场景下的竞态条件

错误示例：

# 错误：多线程下无同步的布隆过滤器
import threading

class UnsafeConcurrentBF:
    def __init__(self, m, k):
        self.bits = bytearray(m // 8)
        self.m = m
        self.k = k

    def add(self, x):
        # 竞态：多线程同时写同一位，可能丢失更新
        for idx in self._hashes(x):
            self.bits[idx // 8] |= (1 << (idx % 8))

错误原因：

bytearray[idx] |= value 不是原子操作，包含”读-改-写”三步，多线程下可能丢失更新。

修正方案：

1. 使用 ReadWriteLock（Java）或 threading.Lock（Python）
2. 使用分段锁（如 Java ConcurrentHashMap 的设计）
3. 使用原子操作（如 C++ std::atomic）

import threading

class SafeConcurrentBF:
    def __init__(self, m, k, segments=16):
        self.m = m
        self.k = k
        self.segments = segments
        self.segment_size = m // segments
        self.bits = [bytearray(self.segment_size // 8) for _ in range(segments)]
        self.locks = [threading.Lock() for _ in range(segments)]

    def add(self, x):
        for idx in self._hashes(x):
            seg = idx // self.segment_size
            local_idx = idx % self.segment_size
            with self.locks[seg]:
                self.bits[seg][local_idx // 8] |= (1 << (local_idx % 8))

7.6 陷阱 6：序列化与持久化时的字节序问题

错误示例：

# 错误：跨平台持久化布隆过滤器
bf = BloomFilter(capacity=100_000)
# ... 插入数据 ...

# 在大端机器上序列化
with open("filter.bin", "wb") as f:
    f.write(bf.bit_array)

# 在小端机器上加载，哈希位置错乱
with open("filter.bin", "rb") as f:
    bf.bit_array = bytearray(f.read())