想象你是快递仓库的管理员老王，手头有一排储物柜，每来一个快递，你就根据快递单号算出三个柜门号，在对应柜门上贴一张标签。这样，以后有人来问“某个快递到过没”，你只要查那三个柜门：只要有一个柜门空着，就能肯定地说“没到过”；如果三个柜门都有标签，你只能说“可能到过”。问题来了——不同快递单号算出的柜门可能会重叠，标签越贴越多，最后连一个从没寄到过的快递，它的三个柜门也都被别的标签占满了，于是你给出了错误答案：“到过”。这个“明明没有却说有”的错误，就叫误判，也叫假阳性。 布隆过滤器（Bloom Filter）就是这排储物柜的数字化版本，而“误判率有多高、柜子要准备多少、每个快递该贴几个标签”是三个核心问题。本文就用这个快递柜的故事，带你一步步推导布隆过滤器的误判率公式，学会像老手一样挑选参数，最后看看它在真实系统里怎么用。

岗位关联

掌握误判率公式意味着你能在缓存穿透、黑名单过滤、海量去重等场景里，用千分之一的内存完成近似查询，并精准回答面试官最爱的“为什么误判、误判率多少、参数怎么定”——这是后端与大数据岗的高频考点。

目录
  1. 可视化演示
  2. 误判率公式
  3. 哈希函数个数
  4. 位数组大小
  5. 空间权衡
  6. 计数过滤器
  7. 工程实践
  8. AI 应用场景
  9. Python 演示
  10. 常见误区
  11. 面试题

可视化演示

通过位阵列插入查询演示布隆过滤器工作原理，展示误判率公式P=(1-e^(-kn/m))^k随参数变化曲线及最优k选择。

本节配有交互动效（进入视口后自动加载，约 3KB）。

布隆过滤器位阵列 绿色=已置位，3个哈希函数映射元素到12位阵列 FP=误判：元素不存在但所有位均为1 P = (1 - e^(-kn/m))^k 插入3元素后查询演示TP/FP/TN三种结果

误判率公式

老王最近很头疼：仓库里明明没收到过快递 A，可查柜门时三个柜门都贴着标签，他只能答复“可能到了”。为什么会这样？因为不同快递单号算出的柜门号会凑巧重叠，你贴的标签不知不觉盖在别人家柜门上。这种“根本没插入过、查询却返回存在”的错误，专业术语叫假阳性（False Positive）。与之相对的是假阴性（False Negative）——明明存在却说不在，布隆过滤器永远不会有这种错误，因为只要柜门空着，就说明从未有快递映射到它。

把故事翻译成数学语言：位数组有 m 个柜门，放入了 n 个快递，每个快递由 k 个哈希函数算出 k 个柜门号并置位。查询一个快递时，看它对应的 k 个柜门是否全为 1。误判发生的条件是：这 k 个柜门恰好都被其他快递“顺手”置位了。每个柜门在一次哈希中被选中的概率是 1/m，经过 k 次哈希和 n 个快递的“轮番轰炸”，某一位仍为 0 的概率可以用指数近似表示，从而推导出经典误判率公式：

老王明白了：误判率本质上就是“不该贴的标签恰好把目标柜门盖满”的概率。柜门越多、快递越少、标签越稀疏，误判就越低。但柜门数量要花钱租，标签数量要花力气贴，接下来两节就解决“怎么花最少的钱”。

f=(1−e−kn/m)k\displaystyle f = \left(1 - e^{-kn/m}\right)^{k}
这个公式告诉我们：误判率不是玄学，而是“某个柜门被意外占满”的概率，只要知道柜门数 m、哈希函数数 k、插入元素数 n，就能精确算出误判风险。
  1. 单次哈希不命中某个柜门一次哈希从 m 个柜门里挑一个，没挑中指定柜门的概率：
    1−1m\displaystyle 1 - \frac{1}{m}
  2. 一次插入后仍为空一个快递要算 k 个哈希，每个都没命中这个柜门：
    (1−1m)k\displaystyle \left(1 - \frac{1}{m}\right)^{k}
  3. n 次插入后仍为空n 个快递轮番来，这个柜门始终没被贴标签，用自然对数的底 e 做近似（m 很大时成立）：
    (1−1m)kn≈e−kn/m\displaystyle \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m}
  4. 某位被置为 1 的概率就是上面的补事件：
    1−e−kn/m\displaystyle 1 - e^{-kn/m}
  5. 查询时 k 个柜门全为 1这 k 个位置恰好都被人占过的概率相乘，得到整体误判率：
    f=(1−e−kn/m)k\displaystyle f = \left(1 - e^{-kn/m}\right)^{k}

哈希函数个数

老王现在纠结：每个快递到底贴几张标签？贴 1 张？那不同快递很容易撞在同一个柜门上，误判自然高。贴 20 张？每个快递占的柜门太多，仓库很快就会“满溢”，结果随便查什么都像存在。聪明的老王意识到，这里存在一个“恰到好处”的中间值。

用数学语言说，在 m 和 n 固定时，误判率 f 是关于 k 的 U 形曲线：k 太小，哈希碰撞剧烈，误判率高；k 太大，位数组迅速被填满，误判率也会反弹升高。求这条曲线的最低点需要对 f 取对数后求导，令导数为 0，解出最优的标签数量：

老王终于不纠结了：柜门总数除以快递总数，再乘以 0.693，取个最近的整数就是最佳标签数。他还发现一个细节：哈希函数必须足够“均匀”，否则某些柜门永远被冷落，另一些被挤爆，实际误判率会比公式算出的高——就像老王手写的单号映射规则设计得歪，标签全堆在入口处的柜门上。

kopt=mnln⁡2≈0.693×mn\displaystyle k_{\text{opt}} = \frac{m}{n} \ln 2 \approx 0.693 \times \frac{m}{n}
最优 k 只和“平均每个元素分到多少个柜门”有关。直觉上它让位数组的填充率恰好维持在 1/2，此时“空位被意外占用”和“柜门被占满”两种风险达到均衡。
  1. 取对数便于求导误判率公式两边取自然对数，乘积变求和：
    ln⁡f=kln⁡(1−e−kn/m)\displaystyle \ln f = k \ln\left(1 - e^{-kn/m}\right)
  2. 对 k 求导并令导数为 0寻找曲线的极小值点，令 g = ln f，对其求导：
    g′(k)=ln⁡(1−e−kn/m)+k⋅nm⋅e−kn/m1−e−kn/m=0\displaystyle g'(k) = \ln\left(1 - e^{-kn/m}\right) + \frac{k \cdot \frac{n}{m} \cdot e^{-kn/m}}{1 - e^{-kn/m}} = 0
  3. 换元化简令 p = e^{-kn/m}，代入后方程变为关于 p 的简洁形式：
    ln⁡(1−p)+pln⁡p1−p=0\displaystyle \ln(1-p) + \frac{p \ln p}{1-p} = 0
  4. 解出最优条件化简得到 p = 1/2，即位数组填充率恰好一半时最优：
    e−kn/m=12⇒kopt=mnln⁡2\displaystyle e^{-kn/m} = \frac{1}{2} \Rightarrow k_{\text{opt}} = \frac{m}{n} \ln 2
  5. 代回求最低误判率把 p = 1/2 代回原公式：
    fmin⁡=(12)k=0.6185 m/n\displaystyle f_{\min} = \left(\frac{1}{2}\right)^{k} = 0.6185^{\,m/n}

位数组大小

仓库租金要涨了，老王想知道：到底租多少个柜门才够用？直觉告诉他，快递越多，柜子就得越多，否则柜门很快被标签塞满。更关键的是，柜门数量和误判率之间有明确的数学关系：想要更低的误判，就得按比例增加柜门。把最优 k 代回误判率公式，反解出 m：

老王记得，这个公式背后还有一个重要规律：最优状态下的位数组填充率恒为 1/2，也就是说高效利用的柜门只有一半。如果哪天发现标签已经盖满了三分之二的柜门，说明参数需要重新调整——要么柜门少了，要么标签贴多了。

m=−nln⁡f(ln⁡2)2≈−2.08×n×ln⁡f\displaystyle m = -\frac{n \ln f}{(\ln 2)^2} \approx -2.08 \times n \times \ln f
这个公式是“预算公式”：先定下有多少快递 n、能接受多高的误判率 f，就能算出最少需要多少位内存。例如误判率 1% 时，每个元素大约需要 9.6 位——比存原始数据省太多。
  1. 代入最优 k把 k = (m/n)ln2 代回最低误判率公式：
    f=(12)mnln⁡2\displaystyle f = \left(\frac{1}{2}\right)^{\frac{m}{n} \ln 2}
  2. 两边取对数把指数挪到前面，便于解出 m：
    ln⁡f=−mn(ln⁡2)2\displaystyle \ln f = -\frac{m}{n} (\ln 2)^2
  3. 反解出 m整理等式，得到位数组大小的解析式：
    m=−nln⁡f(ln⁡2)2\displaystyle m = -\frac{n \ln f}{(\ln 2)^2}
  4. 算出常数1/(ln2)² ≈ 2.08，于是得到工程速算式：
    m≈2.08×n×(−ln⁡f)\displaystyle m \approx 2.08 \times n \times (-\ln f)
  5. 代入典型值验证误判率 1% 时 -ln f ≈ 4.6，m ≈ 9.6n 位，即每个元素约 1.2 字节：
    mn≈9.6 bit/元素\displaystyle \frac{m}{n} \approx 9.6 \text{ bit/元素}

空间权衡

老王算了一笔账：现在误判率是 1%，业务方要求降到 0.1%，也就是降低 10 倍。他下意识觉得柜门数量也得翻 10 倍，预算会爆掉。但翻出公式一算，发现远没那么夸张——误判率降低 10 倍，只在原来的基础上多加约 4.8n 个柜门。这是因为误判率对 m 是对数关系：空间增加是线性的，误判率下降却是指数的。用差量公式可以精确表达：

老王把这个结论记在小本本上：m、k、n 三个参数像三根联动的水管——拧紧误判率，空间就得放大；元素增多，空间也得按比例放大；而 k 永远跟随 m/n 的比值变化，不需要单独反复试验。实践中他先问业务“能接受多高的误判”，再问“有多少元素”，最后用公式一步算出 m 和 k，全程不超过五分钟。

m2−m1=n(ln⁡f1−ln⁡f2)(ln⁡2)2=4.8n 位（当 f1/f2=10）\displaystyle m_2 - m_1 = \frac{n\left(\ln f_1 - \ln f_2\right)}{(\ln 2)^2} = 4.8n \text{ 位（当 } f_1/f_2 = 10\text{）}
“误判率降一个数量级”的价格是每个元素多花 4.8 位内存。这让参数选择变成一门成本生意：误判率要求越苛刻，单价越贵，而且是指数级的贵。
  1. 写出两位数组的差用上节的 m 公式分别表示两个误判率对应的空间：
    m1=−nln⁡f1(ln⁡2)2,m2=−nln⁡f2(ln⁡2)2\displaystyle m_1 = -\frac{n \ln f_1}{(\ln 2)^2}, \quad m_2 = -\frac{n \ln f_2}{(\ln 2)^2}
  2. 相减得到增量两个式子做差，对数之差决定空间之差：
    m2−m1=n(ln⁡f1−ln⁡f2)(ln⁡2)2\displaystyle m_2 - m_1 = \frac{n(\ln f_1 - \ln f_2)}{(\ln 2)^2}
  3. 代入“降低 10 倍”f₁/f₂ = 10，则 ln f₁ - ln f₂ = ln 10：
    Δm=nln⁡10(ln⁡2)2≈4.8n\displaystyle \Delta m = \frac{n \ln 10}{(\ln 2)^2} \approx 4.8n

计数过滤器

一天，老王收到通知：有批快递送错了仓库，得从记录里删掉。他正要撕标签，突然傻眼了——同一张柜门上叠着好几个快递的标签，撕掉一张，底下别人的快递也跟着“消失”了。普通布隆过滤器的致命伤就在这里：只存 0/1 的柜门无法区分“贴了 1 张”还是“贴了 3 张”，所以不能删除。解决之道是给每个柜门装一个计数器，快递来了加 1，快递取走减 1，这就是 Counting Bloom Filter（计数布隆过滤器）。每位不再是一个 bit，而是一个小计数器，常用 4 bit 表示 0~15。

每个计数器到底会累计到多大？这取决于平均每个柜门被多少个快递命中。总共 n 个快递、每个贴 k 张标签，一共产生 kn 次计数，平均到 m 个柜门上：

计数器解决了删除问题，但引入了新麻烦：万一某个柜门被贴上 16 张标签，4 bit 计数器溢出怎么办？工程上有三种回退方案：一是直接拒绝继续加 1（可能漏报，但概率极低）；二是把溢出的计数器“冻结”在最大值 15，删除时不再减；三是改用 8 bit 或 16 bit 计数器，用空间换安心。老王笑了笑：“宁可多花点内存，也不愿把柜门记录搞坏。”这提醒我们，计数布隆过滤器适合“边插边删”的场景，比如网页链接的爬取队列去重、会话记录管理，而不适合那些只增不减的静态数据。

E[c]=knm\displaystyle E[c] = \frac{k n}{m}
平均计数 = 总贴标签次数 ÷ 柜门数。当参数取最优时会发现 E[c] ≈ ln2 ≈ 0.69，离 4 bit 上限 15 非常远，所以大多数业务场景下 4 bit 足够用。
  1. 总计数次数n 个快递、每个贴 k 张标签，总共产生的计数值：
    T=kn\displaystyle T = kn
  2. 平均到每个柜门总计数除以柜门数，即每个计数器的期望值：
    E[c]=Tm=knm\displaystyle E[c] = \frac{T}{m} = \frac{kn}{m}
  3. 代入最优参数验证k = (m/n)ln2 时，期望值恒为常数 ln2：
    E[c]=mln⁡2m≈0.693\displaystyle E[c] = \frac{m \ln 2}{m} \approx 0.693

工程实践

老王干腻了仓库，把柜子搬进了互联网公司当架构师。他遇到的第一件事是缓存穿透：某个不存在的商品 ID 被大量请求，每次都绕过缓存直击数据库，数据库快被打挂了。老王在缓存前面加了一个布隆过滤器：商品 ID 来查询时，先过过滤器——返回“不存在”就直接拒绝，不再放行到数据库；返回“存在”才继续查缓存和数据库。因为过滤器从不漏报，所以真实存在的商品绝不会被误杀，只有极少数不存在的 ID 会“混过去”，数据库压力骤降。

第二个场景是黑名单过滤：浏览器的安全组件需要检查访问的 URL 是否在恶意网址黑名单里。完整黑名单有几百万条，每次请求都拉取并精确匹配太慢太费内存，于是用布隆过滤器保存黑名单的指纹。查询结果是“存在”的 URL 再回源做二次精确校验，既保证零漏报，又把大部分安全请求就地放行。类似的还有搜索引擎爬虫的 URL 去重：几十亿条链接，用哈希表存太奢侈，布隆过滤器用约每 URL 10 bit 的成本完成“是否爬过”的判断。实践中最常用的经验公式是一步到位的估算：

老王最后总结道：布隆过滤器从不撒谎说“不在”，只在说“在”的时候偶尔犯错，而犯错概率你可以亲手拿捏。快递柜前那排贴满标签的柜门，如今成了分布式系统里最省内存的守望者——它牺牲了一点点的准确性，换来了十几倍的内存节约和常数级的查询速度。只要记住“先定 n 和 f、再算 m 和 k”这套流程，你也能像老王一样，把误判率算得清清楚楚。

k≈0.7×mn\displaystyle k \approx 0.7 \times \frac{m}{n}
工程调参的标准流程是：先定 n 和可接受的 f，用 m = -2.08n·ln f 算出位数组大小，再用 k = 0.7(m/n) 取整得到哈希函数个数。全流程不需要试错，只需要一个计算器。
  1. 最优 k 的近似把 ln2 ≈ 0.693 写成工程上顺手的 0.7：
    kopt=mnln⁡2≈0.7×mn\displaystyle k_{\text{opt}} = \frac{m}{n} \ln 2 \approx 0.7 \times \frac{m}{n}
  2. 取整规则k 是整数，采用四舍五入或就近取整，误差对误判率影响很小：
    k=round(0.7×mn)\displaystyle k = \text{round}\left(0.7 \times \frac{m}{n}\right)
  3. 实例化计算比如 n = 100 万、目标误判 1% 时，m ≈ 960 万位 ≈ 1.2 MB，k ≈ 7：
    m≈9.6×106 bit,k=round(6.7)=7\displaystyle m \approx 9.6 \times 10^6 \text{ bit}, \quad k = \text{round}(6.7) = 7

AI 应用场景

缓存穿透防护：AI 特征服务的守门员

阶段：在线推理前的数据查询加速

解决的问题：推荐系统的特征服务里，用户请求的特征 ID 若不存在于数据库，每次查询都会穿透 Redis 直达 MySQL，导致延迟飙升、数据库过载。传统做法是查询结果为空后短时间缓存空值，但攻击者可以伪造海量不存在的 ID，缓存空值也架不住。布隆过滤器先在内存里拦截“必定不存在”的请求，只有“可能存在”的请求才放行到后端。

具体案例：某新闻推荐系统的曝光去重服务，维护着一个包含 5000 万条已曝光新闻 ID 的布隆过滤器，位数组大小设为 4.8 亿位（约 57 MB），k 取 7，理论误判率约 0.8%。每次用户刷新推荐流时，先用过滤器判断新闻是否已推给该用户，误判的新闻最多只是少推一次，完全不影响体验，而内存开销仅为精确 HashSet 的十分之一。

黑名单过滤：安全风控的第一道闸门

阶段：安全检测的数据预处理与快速筛除

解决的问题：风控系统需要判断 IP、设备指纹、URL 是否在历史黑名单中。黑名单规模达千万级，精确匹配需要加载全量数据且耗时不可控。布隆过滤器用极小的内存把“绝大概率不在名单”的请求快速放行，只有命中的少数请求才进入精确匹配模块复核，实现两级过滤。

具体案例：Chromium 浏览器的 Safe Browsing 功能正是这一思路的经典案例：浏览器本地保存一个压缩的布隆过滤器，访问 URL 时先查本地过滤器，命中后再向远程服务器发起精确匹配。由于本地过滤器“只在'在'的时候可能误报，从不把'危险'报成'安全'”，因此安全性有保证，而绝大多数正常浏览请求无需联网校验，延迟几乎为零。

爬虫 URL 去重：海量数据清洗的节约大师

阶段：数据采集与清洗阶段的去重

解决的问题：训练语料收集阶段，爬虫需要判断一个 URL 是否已抓取。用哈希表存储几十亿条 URL 原始字符串需要几百 GB 内存，而布隆过滤器按每 URL 约 10 bit 计算，仅需几 GB。代价是极小概率“重复抓取”同一页面，多抓一次比漏抓要好得多——这正是布隆过滤器的容错方向与业务需求完美匹配的典型。

具体案例：某开源搜索引擎的爬虫每天新增约 2 亿 URL，团队设定 n = 20 亿、f = 1%，算出 m ≈ 192 亿位（约 2.4 GB）位数组，k = 7。相比用 Redis Set 存储 URL 要消耗 120 GB+ 内存，成本降了 98%，抓取队列的判重吞吐量提升了 5 倍。

Python 演示

python42 行
import hashlib  class BloomFilter:    def __init__(self, m, k):        self.m = m        self.k = k        self.bits = [0] * m     def _hashes(self, item):        for i in range(self.k):            digest = hashlib.sha256((item + str(i)).encode()).hexdigest()            yield int(digest[:8], 16) % self.m     def add(self, item):        for h in self._hashes(item):            self.bits[h] = 1     def contains(self, item):        return all(self.bits[h] for h in self._hashes(item))  def measure_false_positive(m, n, k):    bf = BloomFilter(m, k)    for i in range(n):        bf.add("user" + str(i))    fp = 0    for i in range(n):        if bf.contains("spam" + str(i)):            fp += 1    return fp / n  if __name__ == "__main__":    n = 5000    m = 50000    best_k = round(m / n * 0.693)    print("best k =", best_k)    for k in [1, 3, best_k, 10, 20]:        actual = measure_false_positive(m, n, k)        theory = (1 - 2.718281828 ** (-k * n / m)) ** k        print("k=%2d  theory=%.4f  actual=%.4f" % (k, theory, actual))
目的：用纯 Python 实现一个带 k 个哈希函数的布隆过滤器，插入 5000 个元素后查询 5000 个未插入的元素，对比实际误判率与理论公式 f = (1-e^{-kn/m})^k 的吻合程度，并验证最优 k 附近的误判率最低。
  1. self.bits = [0] * m用列表模拟位数组，m 个柜门全部初始化为空。
  2. for i in range(self.k)生成器循环 k 次，每次派生出第 i 个哈希函数。
  3. int(digest[:8], 16) % self.m取 SHA-256 摘要的前 8 位十六进制转整数，再对 m 取模，得到 0 到 m-1 的柜门号。
  4. yield int(...)生成器逐次吐出 k 个柜门号，避免一次性开辟大列表。
  5. self.bits[h] = 1将算出的柜门贴标签，相当于插入操作。
  6. return all(self.bits[h] for h in self._hashes(item))查询时 k 个柜门全部为 1 才返回存在，只要有一个是 0 就返回不存在。
  7. best_k = round(m / n * 0.693)用最优 k 公式 k = (m/n)·ln2 取整得到推荐参数。
  8. for k in [1, 3, best_k, 10, 20]故意取偏离最优值的一组 k，观察误判率先降后升的 U 形曲线。
  9. theory = (1 - 2.718281828 ** (-k * n / m)) ** k用 e 的指数近似复现理论误判率公式，与实测对照。

常见误区

误区布隆过滤器既然有误判，那查询返回“不存在”的时候，元素可能其实已经被插入过了，所以我不能完全相信“不存在”的结论。

正解恰恰相反——布隆过滤器的误判是单向的。它只有假阳性（没插入却说存在），绝无假阴性（插入了却说不存在）。回到快递柜的比喻：只要有一个柜门空着，就说明没有任何快递映射到这个柜门，目标快递一定没来过。也就是说，“不在”是绝对可靠的，“在”才需要怀疑。这也是布隆过滤器能放心用来挡缓存穿透的原因：真实存在的 key 永远不会被误杀。

为何常见：很多人把“有误判”笼统理解为“结果不可靠”，忽略了误判的方向性。面试中主动说出“假阴性率为 0”会立刻让面试官眼前一亮。

误区既然哈希碰撞导致误判，那多算几个哈希函数、多贴几张标签，碰撞的机会不就分散了吗？k 越大肯定越安全。

正解误判率随 k 的变化是一条先降后升的 U 形曲线。k 太小，标签稀疏但碰撞剧烈；k 超过最优值后，每个元素占用的柜门太多，位数组迅速被填满，查询任何元素都容易“全命中”，误判率反而反弹。最优 k 是 (m/n)·ln2，它让位数组恰好保持半满——这就是那个让两种风险达到平衡的“甜蜜点”。

为何常见：直觉上“多一道校验更保险”，但布隆过滤器的多道校验共用同一个位数组，校验多到一定程度等于把位数组全涂满，校验形同虚设。

误区误判率当然是越低越好，直接把位数组设成超大，比如每个元素分 100 bit，误判率不就趋近于零了吗？

正解位数组每增加 4.8n 位，误判率才降低 10 倍，这是指数级的“价格”。对千万级数据来说，每降一个数量级要多花数十 MB 内存，收益却微乎其微。工程上应依据业务接受度设定阈值：可容忍 1% 就绝不追求 0.1%，把内存留给更需要的地方。布隆过滤器的价值恰恰在于“用可接受的误判换取内存优势”，丢掉这个权衡就本末倒置了。

为何常见：人们习惯用“精确性”衡量算法优劣，忽略了布隆过滤器是近似数据结构，它的存在意义就是“恰到好处地省”。

误区插入就是把位设为 1，那删除自然就是把位设为 0，这不就实现删除功能了吗？

正解普通布隆过滤器把位设为 0 会误删其他元素——同一个位可能被多个元素共享，撕掉一张标签会让所有蹭到这个位的元素集体“消失”，造成漏报，这比误判严重得多。要支持删除必须改用 Counting Bloom Filter：每个位升级为计数器，删除时减 1 而不是清 0。但计数器也可能溢出（常用 4 bit 上限 15），需要配套溢出回退策略。

为何常见：把“位数组”误解为每个元素独享一个位置的集合，忽略了哈希映射的共享性。

面试题

Q1. 布隆过滤器查询返回“该元素不存在”时，以下说法正确的是？

单选题 · easy

  • A.该元素一定不存在← 正确答案
  • B.该元素可能不存在
  • C.该元素一定存在
  • D.无法判断是否被误判

答案：A。布隆过滤器只有假阳性、没有假阴性。像快递柜一样，只要有一个柜门为空，就能断定该快递从未插入过。所以“不存在”是 100% 可靠的，“存在”才可能是误判。

Q2. 位数组大小 m 和元素个数 n 固定时，误判率随哈希函数个数 k 的变化趋势是？

单选题 · mid

  • A.单调下降，k 越大误判越低
  • B.单调上升，k 越大误判越高
  • C.先降后升，存在最优 k← 正确答案
  • D.与 k 完全无关

答案：C。k 太小，哈希碰撞剧烈；k 太大，位数组被快速填满，查询任何元素都容易全命中。误判率曲线是 U 形，最优 k = (m/n)·ln2 时位数组约半满，这也是 f = 0.6185^(m/n) 成立的条件。

Q3. 普通布隆过滤器最突出的两大局限是什么？

单选题 · easy

  • A.查询速度慢、内存占用大
  • B.只能存整数、不支持字符串
  • C.有误判、不支持删除← 正确答案
  • D.需要额外存储原始数据

答案：C。布隆过滤器的查询是 O(k) 哈希计算，非常快；内存按位存储，非常省。真正的代价是假阳性误判，以及普通版无法删除（删除一位可能误伤其他元素）。Counting Bloom Filter 通过计数器缓解删除问题。

Q4. 已知位数组大小 m 与元素个数 n 的比值为 10，最优哈希函数个数 k 约为多少？

单选题 · mid

  • A.5
  • B.6
  • C.7← 正确答案
  • D.8

答案：C。k = (m/n)·ln2 ≈ 10 × 0.693 ≈ 6.93，四舍五入取 7。这也是工程上最常见的参数之一：m/n = 10、k = 7 时理论误判率约 0.82%。

Q5. 下列哪些因素会影响布隆过滤器的误判率？

多选题 · mid

  • A.位数组大小 m← 正确答案
  • B.插入的元素个数 n← 正确答案
  • C.哈希函数的个数 k← 正确答案
  • D.插入元素值本身的长度

答案：ABC。误判率公式 f = (1-e^{-kn/m})^k 只包含 m、n、k 三个变量。元素值本身先经过哈希函数映射成固定长度的哈希值，值的长度大小不会进入公式。哈希函数的均匀性会影响实际值与理论值的偏差，但均匀性不等于元素长度。

Q6. 关于误判率公式 f = (1-e^{-kn/m})^k，下列说法正确的有？

多选题 · hard

  • A.当 n = 0 时，误判率为 0← 正确答案
  • B.当 m 远大于 kn 时，误判率接近 0← 正确答案
  • C.哈希函数个数增加，误判率一定下降
  • D.k 取最优值 (m/n)·ln2 时，误判率约为 0.6185^(m/n)← 正确答案

答案：ABD。n=0 时没有任何插入，位数组全空，误判率为 0；m 远大于 kn 时每位几乎不会被置位，查询很难命中全部 k 位。k 对误判率的影响是 U 形而非单调，所以 C 错误。最优 k 代入后可得 f = (1/2)^k = 0.6185^(m/n)。

Q7. 某系统需插入 100 万个元素，要求误判率不超过 1%，位数组 m 至少约为多少位？

单选题 · hard

  • A.约 96 万位
  • B.约 480 万位
  • C.约 958 万位← 正确答案
  • D.约 1916 万位

答案：C。m = -n·ln f / (ln2)² = -10⁶ × ln(0.01) / 0.48 ≈ 10⁶ × 4.605 / 0.48 ≈ 9.58×10⁶ 位，即约 958 万位，折合约 1.2 MB。误判率 1% 时每元素约 9.6 bit 是高频考点。

Q8. Counting Bloom Filter 与普通布隆过滤器的核心区别是什么？

单选题 · easy

  • A.使用更快的哈希函数
  • B.每个位升级为计数器，支持删除← 正确答案
  • C.误判率降为零
  • D.不需要位数组

答案：B。普通布隆过滤器的位只有 0/1，无法区分一个位被多少元素共享，删除任意一位都可能误伤其他元素。Counting Bloom Filter 把每位变成计数器，插入加 1、删除减 1，从而支持删除操作，但误判依然存在，计数器还有溢出风险。

Q9. 关于 Counting Bloom Filter，下列说法正确的有？

多选题 · mid

  • A.删除元素时对应计数器减 1← 正确答案
  • B.计数器归零表示该位不再被任何元素占用← 正确答案
  • C.常用 4 bit 计数器，上限为 15← 正确答案
  • D.可以完全消除误判

答案：ABC。计数器的加 1/减 1 机制精确记录共享次数，减到 0 才真正释放该位。4 bit 能表示 0~15，最优参数下平均计数约 0.69，距离上限很远。但误判来自哈希碰撞的本质，计数器只是支持删除，并不能消除误判，D 错误。

Q10. 已知 n = 100000，m = 1000000（m/n = 10），k 取最优值 7，理论误判率约为多少？

单选题 · extreme

  • A.约 0.82%← 正确答案
  • B.约 8.2%
  • C.约 0.082%
  • D.约 82%

答案：A。最优 k 下误判率 f = 0.6185^(m/n) = 0.6185¹⁰ ≈ 0.0082，即 0.82%。也可以直接代入公式 f = (1-e^{-kn/m})^k = (1-e^{-0.7})⁷ 验证。这个数值远低于常见的 5% 业务阈值，说明 m/n = 10、k = 7 是一组非常经济的默认参数。