直接用bitarray因内存省两个数量级且速度快5–10倍；add()须用多个独立哈希函数；m、k需按n和p反推；__contains__必须检查全部k位才能避免假阴性。
为什么直接用 bitarray 而不是 Python 自带的 list[bool]
因为布隆过滤器核心是位级操作，list[bool] 每个元素实际占 24–28 字节（Python 对象开销），而 bitarray 真正按位存储，100 万个 bit 仅约 125 KB。内存差两个数量级，插入/查询速度也快 5–10 倍。不换 bitarray 就不是生产可用的布隆过滤器。
bloom_filter.add() 必须用多个独立哈希函数，不能只调一个再加偏移
常见错误是写成 hash(x) % m、(hash(x) + 1) % m、(hash(x) + 2) % m —— 这本质是线性探测，一旦 hash(x) 碰撞，所有位置都连带失效。正确做法是用不同种子或不同哈希算法生成真正独立的值：
- 推荐：用
mmh3.hash(x, seed)配 3–5 个不同seed（如 0, 1, 2, 3, 4） - 次选：用
hashlib.sha256(x.encode()).intdigest() & 0x7FFFFFFF配不同前缀（b"0"+x,b"1"+x…） - 绝对避免：对同一哈希结果做
+i或*i取模——相关性太强，误判率飙升
误判率计算和 m、k 参数怎么定
布隆过滤器不是“设了就行”，m（位数组长度）和 k（哈希函数个数）必须按预期容量 n 和容忍误判率 p 反推：
-
m = -n * ln(p) / (ln(2) ** 2)→ 比如n=100_000,p=0.01，算出来m ≈ 958506bit（约 117 KB） -
k = (m / n) * ln(2) ≈ 6.64→ 向上取整为 7 个哈希函数 - 用错参数的典型现象：
m太小 → 插入几千条就几乎全为 1 → 查询全返回True；k太大 → 单次插入翻倍写入，但收益递减，还拖慢速度
示例初始化片段：
macOS UI 自动化技能包 —— 用 Python 控制你的 Mac
下载
让 macOS 自动化像说话一样简单 —— 用代码控制你的 Mac，无需学习 AppleScript 系统要求 macOS 14+ (Sonoma) Python 3.9+ 需要开启：辅助功能 + 屏幕录制权限
import mmh3
from bitarray import bitarray
<p>class BloomFilter:
def <strong>init</strong>(self, n, p=0.01):
self.n = n
self.p = p
self.m = int(-n * <strong>import</strong>('math').log(p) / (<strong>import</strong>('math').log(2) *<em> 2))
self.k = int((self.m / n) </em> <strong>import</strong>('math').log(2))
self.bit_array = bitarray(self.m)
self.bit_array.setall(0)</p><pre class="brush:python;toolbar:false;">def add(self, item):
for i in range(self.k):
idx = mmh3.hash(item, i) % self.m
self.bit_array[idx] = 1
为什么 __contains__ 不能提前 return False？必须检查全部 k 个位置
布隆过滤器的“不存在”结论只在所有 k 个哈希位置都是 0 时才成立。只要有一个是 0，就不能断言存在；但只要有一个是 0，就必须继续查完剩下的——否则漏掉某个位置是 1 的情况，会把真实存在的元素误判为不存在（假阴性），这违反布隆过滤器“只允许假阳性，不允许假阴性”的设计前提。
所以这个逻辑是刚性的：
- 任意一个位置是 0 → 立即返回
False - 全部
k个位置都是 1 → 返回True（可能是真，也可能假） - 没有“查到一半发现是 1 就返回 True”的捷径——那会破坏确定性
容易被忽略的是：当 k 较大（比如 >10）、且数据局部性高（大量 key 共享前缀）时，CPU 缓存未命中会变多，此时把 idx 预先算好再批量访问 bit_array，比边算边查略快一点。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
