Skip to content

介绍一下布隆过滤器，以及优化措施

1. 什么是布隆过滤器

布隆过滤器（Bloom Filter）是一种空间效率很高的概率型数据结构，主要用来回答一个问题：

某个元素“是否可能存在于一个集合中”。

它的结论有两个特点：

  • 如果它判断不存在，那这个元素就一定不存在。
  • 如果它判断存在，那这个元素只是可能存在，也可能是误判。

所以布隆过滤器的经典结论是：

  • 没有漏判（False Negative）
  • 可能误判（False Positive）

这也是它能节省大量空间的根本原因，因为它不存元素本身，只存“是否命中过某些位置”的信息。

2. 布隆过滤器的基本原理

2.1 核心结构

一个标准布隆过滤器通常由两部分组成：

  • 一个长度为 m 的位数组（bit array）
  • k 个哈希函数

位数组初始时全为 0。

2.2 插入过程

假设要插入一个元素 x：

  1. 用 k 个哈希函数分别对 x 做哈希。
  2. 得到 k 个位置。
  3. 把位数组中这 k 个位置都置为 1。

2.3 查询过程

假设要查询元素 x 是否存在：

  1. 同样用 k 个哈希函数算出 k 个位置。
  2. 检查这 k 个位置是否都为 1。

查询结果有两种：

  • 只要有一个位置是 0，说明这个元素一定不存在。
  • 如果所有位置都是 1，说明这个元素可能存在。

2.4 为什么会误判

误判的根本原因是：

  • 不同元素经过哈希后，可能会落到相同的位置。

例如：

  • 元素 A 把位置 1、5、8 置为 1
  • 元素 B 把位置 2、5、9 置为 1
  • 元素 C 虽然从未插入，但它哈希后恰好命中了已经被别人置 1 的位置

那么查询 C 时就会得到“可能存在”的结果，这就是误判。

3. 布隆过滤器的优缺点

3.1 优点

  • 空间占用小：相比 HashSet 存完整元素，布隆过滤器只存 bit。
  • 查询快：插入和查询时间复杂度通常都是 O(k)。
  • 适合海量数据粗过滤：特别适合做“先挡掉明显不存在的数据”。

3.2 缺点

  • 有误判率
  • 标准布隆过滤器不支持安全删除
  • 元素数量持续增长时，误判率会上升
  • 无法枚举集合内容，因为它根本不存原始元素

4. 布隆过滤器适合解决什么问题

布隆过滤器最适合做的不是“精确集合管理”，而是：

  • 存在性快速预判
  • 大规模粗去重
  • 挡掉大量无效请求

典型思路是：

先用布隆过滤器做低成本初筛，再用数据库 / 缓存 / 精确集合做最终确认。

5. 标准布隆过滤器为什么很难做删除

这是面试里最常见的追问。

5.1 标准布隆过滤器的删除问题

假设元素 A 插入后，把位置 3、8、11 置为 1。

但此时另一个元素 B 可能也命中了位置 8。

如果你要删除 A，把 3、8、11 重新置为 0，就会有风险：

  • 位置 8 其实还被 B 依赖
  • 你一旦把它清零，查询 B 时就可能误判成不存在

这就会产生：

  • 漏判（False Negative）

而标准布隆过滤器最重要的性质就是“不能漏判”，所以它不能简单地通过“把 bit 置 0”来删除。

5.2 一个核心结论

标准布隆过滤器一旦插入，只能继续加，不能安全删除。

所以如果业务里存在：

  • 元素频繁过期
  • 元素频繁移除
  • 要求严格更新集合内容

那么标准布隆过滤器通常就不是最合适的选择。

6. 布隆过滤器怎么更新内容

6.1 先澄清：更新分两种

“更新”这个词在布隆过滤器里要分两种情况：

  1. 逻辑更新但 key 不变
  2. 集合成员发生变化，需要删旧加新

6.2 如果 key 不变，通常不需要更新

如果布隆过滤器只关心“这个 key 是否存在”，例如：

  • 用户 ID 是否存在
  • 商品 ID 是否存在
  • 短链短码是否存在

那么业务字段变化并不影响布隆过滤器。

例如：

  • 用户昵称改了
  • 商品价格改了

只要主键 userId / productId 没变，布隆过滤器根本不需要更新。

6.3 如果是“删旧加新”，标准布隆过滤器本质上做不了真正更新

比如：

  • 原来集合里有 oldKey
  • 现在要把它替换成 newKey

这件事从集合语义上看，本质就是：

  1. 删除 oldKey
  2. 插入 newKey

而标准布隆过滤器不支持删除，所以：

  • 它只能插入 newKey
  • 但无法安全移除 oldKey

这会带来两个结果：

  • 旧 key 仍可能被误判为存在
  • 过滤器会越来越“脏”，误判率逐渐升高

所以标准布隆过滤器里的“更新”，通常只能理解为：

  • 增量追加
  • 不能精确替换

7. 如果业务需要删除或更新，有哪些实现思路

这一部分才是面试追问的重点。

7.1 方案一：计数布隆过滤器（Counting Bloom Filter）

7.1.1 核心思路

把原来的 bit 数组：

  • 0 / 1

改成计数器数组，例如：

  • 4 bit
  • 8 bit
  • 16 bit

插入元素时：

  • 对应位置计数器加 1

删除元素时：

  • 对应位置计数器减 1

查询元素时：

  • 只要某个位置计数器是 0，就说明元素一定不存在

7.1.2 为什么它能支持删除

因为它不再只知道“这个位置是否被置过 1”，而是知道：

  • 这个位置被多少个元素共享

所以删除时不会粗暴清零，而是做引用计数减一。

7.1.3 伪代码示意

class CountingBloomFilter {
    int[] counters;

    void add(String key) {
        for (int idx : hashIndexes(key)) {
            counters[idx]++;
        }
    }

    void remove(String key) {
        for (int idx : hashIndexes(key)) {
            if (counters[idx] > 0) {
                counters[idx]--;
            }
        }
    }

    boolean mightContain(String key) {
        for (int idx : hashIndexes(key)) {
            if (counters[idx] == 0) {
                return false;
            }
        }
        return true;
    }
}

7.1.4 注意点

  • 删除前最好确认这个元素确实曾经插入过，否则可能造成误删计数。
  • 计数器要防止溢出。
  • 空间占用会明显高于标准布隆过滤器。

7.1.5 适用场景

适用于：

  • 元素需要删除
  • 集合是动态变化的
  • 能接受比标准布隆过滤器更高的内存成本

例如：

  • 黑名单集合
  • 动态订阅关系
  • 短周期活动用户集合

7.2 方案二：分片重建 / 周期重建

7.2.1 核心思路

如果业务里的删除不是“必须实时反映”，那不一定要硬上计数布隆过滤器。

更常见、更工程化的做法是：

  • 标准布隆过滤器继续只做追加
  • 到一定周期后，全量重建

例如：

  1. 每天凌晨从数据库全量导出当前有效 key
  2. 重新构建一份新的布隆过滤器
  3. 原子切换新旧过滤器

7.2.2 优点

  • 结构简单
  • 查询性能高
  • 没有计数器额外空间成本

7.2.3 缺点

  • 删除不能实时生效
  • 重建期间需要额外计算和切换机制

7.2.4 适用场景

适用于：

  • 全量数据可重建
  • 删除实时性要求不高
  • 数据变更节奏相对可控

例如：

  • 商品库主键集合
  • 用户 ID 集合
  • 每日更新的白名单 / 黑名单

7.3 方案三：双层布隆过滤器

7.3.1 核心思路

把“新增”和“删除”拆开管理。

例如：

  • 一个主 Bloom Filter 存全量有效数据
  • 一个增量 Bloom Filter 存最近新增
  • 一个删除集合单独记录最近删除的数据

查询时按下面逻辑：

  1. 先查删除集合，如果命中则认为不存在
  2. 再查增量 Bloom Filter
  3. 再查主 Bloom Filter

7.3.2 这个方案的本质

它并不是让 Bloom Filter 自己变得可删除，而是：

  • 用旁路数据结构弥补删除能力

7.3.3 适用场景

适用于：

  • 删除量不大
  • 可以接受多一步查询
  • 希望主过滤器保持标准 Bloom Filter 的高空间效率

例如：

  • 商品下线不频繁
  • 用户注销比例很低
  • URL 去重主集合大、增删局部变化小

7.4 方案四：删除走精确集，布隆过滤器只做前置挡板

这是一种非常实用的设计。

布隆过滤器不要承担“最终真相”，而是只承担：

  • 挡住一定不存在的数据

真正的删除和更新，仍由：

  • 数据库
  • Redis Set / Hash
  • 唯一索引
  • 精确 KV

来保证。

典型查询链路：

  1. 先查 Bloom Filter
  2. 如果 Bloom 判断不存在，直接返回
  3. 如果 Bloom 判断可能存在，再查精确存储

这种设计下：

  • 即使布隆过滤器因为旧数据没删掉而更“宽松”
  • 最终结果仍由精确存储兜底

7.4.1 适用场景

最常见场景：

  • 缓存穿透防护
  • 大规模 URL 去重的粗筛
  • 数据库或 KV 之前的低成本过滤

7.5 方案五：换数据结构，用布谷鸟过滤器（Cuckoo Filter）

7.5.1 为什么有时不该硬改 Bloom Filter

如果业务天然要求：

  • 支持删除
  • 查询仍要快
  • 空间仍要省

那有时更合理的选择不是继续改布隆过滤器，而是直接换成：

  • Cuckoo Filter

7.5.2 它的特点

  • 支持删除
  • 在某些误判率区间，空间效率优于 Counting Bloom Filter
  • 更适合动态集合

7.5.3 代价

  • 实现更复杂
  • 插入逻辑复杂度更高
  • 接近满载时插入性能会下降

7.5.4 适用场景

适用于：

  • 动态集合
  • 高频插入删除
  • 对空间效率仍然敏感

例如：

  • 动态黑名单
  • 动态 URL 集
  • 高并发风控规则集

8. 布隆过滤器的“删除”到底应该怎么选

可以直接按业务来分：

业务特征 推荐方案
几乎只增不删 标准布隆过滤器
可接受周期性修正 标准布隆过滤器 + 定时重建
需要删除，但删除量不大 主 Bloom + 删除精确集
需要频繁增删 Counting Bloom Filter 或 Cuckoo Filter
必须绝对准确 不要用 Bloom Filter，直接用精确集合

这个表比死记“布隆过滤器能不能删”更有工程意义。

9. 布隆过滤器有哪些优化方向

布隆过滤器的优化，本质上围绕三个目标：

  1. 降低误判率
  2. 支持动态更新
  3. 适配特定业务场景

9.1 参数优化：m、n、k

这是最基础也最重要的优化。

三个核心参数分别是：

  • n：预计插入元素数量
  • m：位数组大小
  • k：哈希函数个数

常见结论：

  • n 越大，误判率越高
  • m 越大，误判率越低，但占用空间更多
  • k 太少，分布不充分；k 太多，计算成本上升，且过度置位也会增加误判

工程上通常根据目标误判率 p 来反推：

  • 位数组大小 m
  • 哈希函数数量 k

常用公式：

m = -(n * ln p) / (ln 2)^2
k = (m / n) * ln 2

9.1.1 适用场景

适用于所有使用布隆过滤器的场景，是通用优化。

9.2 哈希函数优化

哈希函数的要求一般是：

  • 分布均匀
  • 速度快
  • 冲突低

工程上常见做法：

  • 用一个高质量哈希生成两个基哈希值
  • 再通过双重哈希构造出 k 个位置

这样可以减少多次独立哈希的 CPU 开销。

常见选择：

  • MurmurHash
  • xxHash

9.2.1 适用场景

适用于：

  • 高 QPS 查询
  • CPU 成本敏感场景

例如：

  • 网关前置过滤
  • Redis / 缓存前置过滤

9.3 分层或分片 Bloom Filter

9.3.1 核心思路

不要把所有数据都塞到一个巨大 Bloom Filter 里，而是：

  • 按业务维度拆分
  • 按时间维度拆分
  • 按 hash 分桶拆分

例如：

  • 按租户拆
  • 按天拆
  • 按业务线拆

9.3.2 优点

  • 降低局部误判率
  • 便于局部重建
  • 更易于做热数据和冷数据隔离

9.3.3 适用场景

适用于：

  • 多租户系统
  • 日志 / 风控 / URL 去重这类时间分片明显的系统

9.4 可扩展布隆过滤器（Scalable Bloom Filter）

9.4.1 核心问题

标准布隆过滤器有一个前提：

  • 要预估 n

如果实际数据量持续增长并远超预估值，误判率就会明显恶化。

9.4.2 核心思路

Scalable Bloom Filter 的做法是：

  • 当当前过滤器接近容量上限时，再追加新的一层 Bloom Filter

查询时：

  • 按层依次查询

这样可以动态扩容，而不需要一次性重建全部数据。

9.4.3 适用场景

适用于：

  • 数据规模难以准确预估
  • 数据持续增长

例如：

  • 注册用户持续增长
  • 爬虫 URL 集持续增长
  • 在线去重平台

9.5 压缩 / 稀疏优化

如果位图非常大且稀疏，可以考虑：

  • 压缩位图
  • 稀疏位图表示

不过这类优化通常会牺牲一部分查询速度。

9.5.1 适用场景

适用于：

  • 内存极度敏感
  • 查询吞吐不是第一优先级

9.6 与精确结构结合：Bloom + HashSet / KV / DB

这是一类非常重要的工程优化。

Bloom Filter 不一定单独使用，很多时候更合理的做法是：

  • 用 Bloom 做“第一层挡板”
  • 用精确存储做“最终确认”

这种组合能同时兼顾：

  • 空间效率
  • 查询吞吐
  • 最终准确性

9.6.1 适用场景

适用于：

  • 缓存穿透
  • 大规模去重
  • 数据库存在性预过滤

10. 针对不同业务场景，布隆过滤器可以怎么优化

这一部分建议直接背。

10.1 缓存穿透防护

10.1.1 场景特征

  • 大量请求查询不存在的 key
  • 不希望无效请求打到数据库

10.1.2 适合的方案

  • 标准 Bloom Filter
  • 周期重建
  • Bloom + 空值缓存

10.1.3 为什么

因为这里的核心目标是：

  • 快速挡掉明显不存在的 key

而不是对集合做强一致删除。

即使布隆过滤器里的旧 key 没有及时删除，也只是会放行少量无效请求，不会影响最终正确性。

10.2 爬虫 URL 去重

10.2.1 场景特征

  • 数据量巨大
  • 去重要求高吞吐
  • 可接受少量误判

10.2.2 适合的方案

  • 标准 Bloom Filter 做粗去重
  • 最终以数据库唯一键或 KV 去重兜底

10.2.3 为什么

URL 去重里最怕的是：

  • 存完整集合太占内存

而 Bloom Filter 很适合做大规模粗筛。

10.3 黑名单 / 风控集合

10.3.1 场景特征

  • 元素动态变化快
  • 需要频繁增删

10.3.2 适合的方案

  • Counting Bloom Filter
  • Cuckoo Filter
  • Bloom + 精确删除集

10.3.3 为什么

因为这类场景对“删除能力”要求更高。

10.4 数据库 / LSM 存储系统中的存在性预判

10.4.1 场景特征

  • 查询一个 key 是否在某个 SSTable / 数据文件中
  • 希望减少无效磁盘访问

10.4.2 适合的方案

  • 标准 Bloom Filter

10.4.3 为什么

这里通常是：

  • 文件一旦生成基本不改
  • 删除通过 compaction / merge 解决

所以标准 Bloom Filter 已经足够好。

10.5 大规模用户或商品主键集合

10.5.1 场景特征

  • 主键规模大
  • 新增多，删除少
  • 可接受延迟修正

10.5.2 适合的方案

  • 标准 Bloom Filter + 定时全量重建

10.5.3 为什么

这是最省心、最常见的工程实践。

11. 布隆过滤器落地时的实现建议

11.1 不要把它当作最终真相

布隆过滤器通常应该作为：

  • 前置挡板
  • 粗过滤层

而不是唯一数据来源。

11.2 明确误判率预算

上线前就要先回答：

  • 允许多高的误判率？
  • 每天多少请求量？
  • 误判多出来的数据库查询是否可接受？

因为误判率不是数学游戏，而是直接影响后端成本。

11.3 预估数据规模，不要让过滤器无限老化

如果实际元素数远超设计上限，误判率会越来越差。

所以要么：

  • 预留足够容量

要么：

  • 做可扩展 Bloom Filter
  • 做周期重建

11.4 删除要求高时，不要强行用标准布隆过滤器

这类场景通常应该优先考虑：

  • Counting Bloom Filter
  • Cuckoo Filter
  • 精确集辅助

11.5 多机场景注意一致性和重建策略

如果是分布式系统，还要考虑：

  • 各节点布隆过滤器如何同步
  • 增量写入如何传播
  • 重建时如何无损切换

常见做法：

  • 后台任务重建后发布新版本
  • 各节点热切换
  • 双 buffer 切换

12. 面试里怎么回答“布隆过滤器怎么更新和删除”

可以直接这样回答：

  • 标准布隆过滤器只能做插入和查询，不能安全删除，因为多个元素可能共享同一个 bit，直接清零会导致别的元素被误判为不存在，产生漏判。
  • 所谓“更新”如果只是业务字段变化但 key 不变，通常不需要更新；如果是删旧加新，本质还是删除加插入，而标准布隆过滤器做不了精确删除。
  • 如果业务确实需要删除，可以用 Counting Bloom Filter，把位数组改成计数器数组，插入时加一，删除时减一。
  • 如果删除不是强实时要求，更常见的工程做法是标准 Bloom Filter 配合周期重建，或者外加一个精确删除集。
  • 如果集合动态增删非常频繁，也可以考虑直接用 Cuckoo Filter 代替。

13. 一句话总结

布隆过滤器最擅长的是“低成本判断一个元素大概率是否存在”，标准版本只适合增量追加和粗过滤；一旦业务需要精确删除、频繁更新或动态集合管理，就要用计数型变种、分层重建，或者直接换成更适合的数据结构。