一句话速记：布隆过滤器利用长度为 m 的位数组与 k 个独立哈希函数进行集合成员判断。查询时若对应位存在 0 则元素必定不存在，全为 1 则元素可能存在（不存在假阴性，存在假阳性）。理论误判率公式为 $p \approx (1 - e^{-kn/m})^k$，最优哈希函数个数为 $k = \frac{m}{n}\ln 2$；在 1% 误判率要求下单元素约需占用 9.6 个比特并计算 7 次哈希；标准布隆过滤器原生不支持元素删除。
数据结构