参数输入
插入元素数 n
item
插入过滤器的元素数量。
位数组大小 m
bit
位数组长度。
哈希数 k
-
每个元素使用的哈希函数数。
查询数
query
估算误命中所用查询次数。
计算结果
—
误判率
—
位占用率
—
最优哈希数
—
期望误命中
位数组占用
误判率曲线
哈希数敏感性
物理模型与主要公式
$$p=\left(1-e^{-kn/m}\right)^k,\quad k_{opt}=\frac{m}{n}\ln 2$$
Bloom过滤器不会产生假阴性，但允许假阳性。若需要删除或计数，应考虑Counting Bloom filter等变体。