布隆过滤器

使用方式：本篇是概率型数据结构的参考深水篇，适合带着具体问题来查；哈希基础见主线篇目（哈希表 070）。

爬虫调度器要判断 10 亿个 URL 是否抓取过，缓存层要挡住对不存在 key 的穿透查询，内存预算却只有几百 MB——哈希表装不下，代价太高。布隆过滤器的答案：用 k 个哈希函数把每个元素映射到 m 位位数组上，查询「一定不存在或可能存在」，假阳性率可控（比如 1%），空间比精确结构省一个数量级。本篇讲清它的数学保证（误判率公式与参数选择）、五种语言实现与 Cassandra、Chrome、Bitcoin 等工业案例，读完后你能算出自己的场景该用多大数组、几个哈希函数，以及什么时候该换布谷鸟过滤器。

前置知识#

建议先阅读以下内容再进入本文：

• 算法分析基础与学习路线

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
    }
}