布隆过滤器原理#

原理： 插入时 k 个哈希置 1；查询时全 1 可能存在，有 0 一定不存在

特点： 空间高效 / 有假阳性无假阴性 / 不支持删除

应用： 缓存穿透防护 / URL去重 / HBase避免无效读

布隆过滤器是一个空间效率极高的概率型数据结构，底层是一个位数组加 k 个哈希函数。插入元素时用 k 个哈希函数计算出 k 个位置并置为 1；查询时检查这 k 个位置是否全为 1，全为 1 表示”可能存在”（有误判即假阳性），只要有一个为 0 就”一定不存在”（无漏判）。这个特性使它特别适合做缓存穿透防护：查询前先过布隆过滤器，一定不存在的请求直接拦截不打到数据库。误判率可以通过增大位数组长度和哈希函数个数来控制，通常设置在 1% 以下就能满足业务需求。布隆过滤器的局限是不支持删除，因为多个元素可能共享同一个 bit 位，置 0 会影响其他元素。如果需要删除可以用 Counting Bloom Filter，每个位置用计数器替代单 bit。和 HashSet 相比，布隆过滤器用极少内存就能判断海量数据的存在性。

追问方向：

• “布隆过滤器能删除吗？”→ 标准布隆过滤器不支持删除，因为多个元素可能共享同一个 bit 位，置 0 会影响其他元素的判断；需要删除功能可用 Counting Bloom Filter，每个位置用计数器替代单 bit
• “误判率怎么控制？”→ 增大位数组长度和哈希函数个数可降低误判率；通常根据预期元素数量和可接受误判率（如 1%）计算最优参数；Redis 的 BF.RESERVE 命令可直接指定误判率和容量
• “和 HashSet 比优势？”→ 布隆过滤器空间效率极高，存储 1 亿个元素仅需约 100MB（1% 误判率），HashSet 存同样数据可能需要数 GB；缺点是有误判且不支持删除，只适合判断存在性的场景

易错点：

• ❌ 布隆过滤器 100% 准确——有假阳性
• ❌ 可以替代缓存——只能判断存在性