布隆过滤器 Bloom Filter

数据结构 · 概率型「在不在」判断

什么是布隆过滤器

要判断「这个元素在不在一个海量集合里」，用哈希表存全部元素又费内存。布隆过滤器换个思路：只用一个位数组 + 几个哈希函数，不存原始元素，空间省到极致。代价是——它会「误判」。

加入元素：用 k 个哈希算出 k 个位置，把这些位都置 1。查询元素：算出同样 k 个位置，只要有一位是 0，就一定不在；如果全是 1，那「可能在」（也可能是别的元素把这些位凑成了 1——误判）。

这里是 m=16 位、k=3 个哈希的布隆过滤器。先「加入」几个数（比如 3、7、11），再「查询」：试试查 7（加过，命中）、查 5（有 0，一定不存在）、再查 2（没加过，但 3 个位恰好都被占了——误判！）。

布隆过滤器的铁律：说「不在」就一定不在（绝不漏判），说「在」只是可能（会误判）。位数组越大、元素越少，误判率越低。标准布隆不支持删除（清一位可能影响别的元素），要删得用「计数布隆」。

布隆过滤器在哪里用

它用「一点误判」换来「极省空间」——这趟结构之旅的最后一站，也是工程里最实用的近似数据结构之一。