如果一个接口被大量查询不存在的数据，比如用户不断请求不存在的商品 ID、缓存里没有的用户 ID，系统很容易被拖进一个尴尬局面：缓存没命中，请求继续打到数据库；数据库查不到，下一次同样的请求又会重复发生。

这类问题的关键不是“如何更快地查到数据”，而是先回答一个更便宜的问题：这个东西是不是一定不存在？

布隆过滤器解决的正是这个问题。它不能像哈希集合那样给出完全精确的答案，但它能用很少的内存，在极快的时间内告诉你：

  • 如果结果是“不存在”，那它一定不存在。
  • 如果结果是“存在”，那它只是可能存在。

这个“可能”就是布隆过滤器最重要的取舍。它用少量误判，换来了很高的空间效率。

先从一个普通集合说起

假设我们要记录 1 亿个已经注册过的用户 ID，最直接的做法是把这些 ID 放进一个集合：

registered_users = set()

registered_users.add("user:10086")

if "user:10086" in registered_users:
    print("exists")

这个方案很好理解，也很精确。但问题是：集合为了支持快速查询，通常不只存储原始元素，还要维护哈希表、桶、指针、扩容状态等额外结构。数据量一大，内存会明显上去。

如果我们的目标只是提前过滤掉明显不存在的请求，真的需要保存完整的字符串吗？

布隆过滤器的答案是：不需要。它只保存一些 bit。

布隆过滤器的直觉

可以把布隆过滤器想成一个很大的位图，也就是一串只包含 0 和 1 的数组：

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

普通位图通常要求元素能直接映射成整数位置，比如数字 13 就对应第 13 个 bit。但现实里的元素可能是字符串、URL、邮箱、订单号，不一定能直接当数组下标。

布隆过滤器在中间加了一层哈希函数。

对于一个元素，它不用一个位置表示，而是用多个哈希函数算出多个位置：

element = "user:10086"

hash1(element) -> 3
hash2(element) -> 9
hash3(element) -> 14

插入这个元素时，就把这些位置都置为 1：

0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0
      ↑           ↑         ↑

查询时也做同样的计算。如果这几个位置中只要有一个还是 0，就说明这个元素一定没插入过。因为只要插入过，当时就一定会把这些位置都置为 1。

如果这几个位置全部都是 1，就只能说明它可能插入过。因为这些 1 也可能是其他元素碰巧设置出来的。

看到这里，布隆过滤器的核心就出来了：

  • 用一个 bit 数组保存状态。
  • 用多个哈希函数把一个元素映射到多个 bit。
  • 插入时把这些 bit 置为 1。
  • 查询时检查这些 bit 是否全为 1。

为什么会误判

假设我们已经插入了两个元素：

A -> 2, 5, 9
B -> 1, 5, 12

位图里被置为 1 的位置大概是：

0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0
  ↑ ↑     ↑       ↑     ↑

现在查询一个从来没有插入过的元素 C：

C -> 1, 9, 12

这三个位置刚好都已经是 1。于是布隆过滤器会回答“可能存在”，但实际上 C 并不存在。

这就是误判，也叫 false positive。

但布隆过滤器不会误判成“不存在”。只要一个元素真的插入过，它对应的那些 bit 一定被置为 1；查询时不可能突然看到其中某个 bit 是 0，除非你的实现里发生了清空、并发写错、数据损坏，或者使用了不支持删除的布隆过滤器却强行删除。

所以它的语义要记牢：

查询结果含义
不存在一定不存在
存在可能存在

这个语义决定了它适合做“提前拦截”，不适合单独做“最终判定”。

插入和查询流程

假设布隆过滤器有三个哈希函数，底层 bit 数组长度是 m。

插入元素 x：

h1 = hash1(x) % m
h2 = hash2(x) % m
h3 = hash3(x) % m

bits[h1] = 1
bits[h2] = 1
bits[h3] = 1

查询元素 x：

h1 = hash1(x) % m
h2 = hash2(x) % m
h3 = hash3(x) % m

if bits[h1] == 1 and bits[h2] == 1 and bits[h3] == 1:
    return "可能存在"
else:
    return "一定不存在"

它的时间复杂度是 O(k)，其中 k 是哈希函数数量。实际工程里 k 通常是一个很小的常数，比如 4、7、10，所以查询速度非常稳定。

空间复杂度是 O(m)，只和 bit 数组长度有关，不直接保存元素本身。

用 Python 写一个最小布隆过滤器

下面实现一个最小可用版本。为了避免依赖 Python 内置 hash() 的随机化行为，这里用 hashlib.blake2b 生成稳定哈希值。

from hashlib import blake2b


class BloomFilter:
    def __init__(self, bit_size: int, hash_count: int):
        if bit_size <= 0:
            raise ValueError("bit_size must be positive")
        if hash_count <= 0:
            raise ValueError("hash_count must be positive")

        self.bit_size = bit_size
        self.hash_count = hash_count
        self.bits = bytearray((bit_size + 7) // 8)

    def _hashes(self, value: str):
        data = value.encode("utf-8")

        for seed in range(self.hash_count):
            digest = blake2b(
                data,
                digest_size=8,
                person=seed.to_bytes(4, "little"),
            ).digest()
            number = int.from_bytes(digest, "little")
            yield number % self.bit_size

    def _set_bit(self, position: int) -> None:
        byte_index = position // 8
        bit_offset = position % 8
        self.bits[byte_index] |= 1 << bit_offset

    def _get_bit(self, position: int) -> bool:
        byte_index = position // 8
        bit_offset = position % 8
        return (self.bits[byte_index] & (1 << bit_offset)) != 0

    def add(self, value: str) -> None:
        for position in self._hashes(value):
            self._set_bit(position)

    def contains(self, value: str) -> bool:
        return all(self._get_bit(position) for position in self._hashes(value))

使用方式：

bloom = BloomFilter(bit_size=1_000_000, hash_count=7)

bloom.add("user:10086")
bloom.add("user:10087")

print(bloom.contains("user:10086"))  # True，可能存在
print(bloom.contains("user:99999"))  # False，一定不存在

这里的 True 不能直接翻译成“存在”，更准确的含义是“没有被过滤掉，需要继续查真正的数据源”。这也是工程里最常见的用法。

哈希函数不一定真的要写 k 个

前面的代码为了直观，用不同的 seed 生成多个哈希结果。实际工程里经常会用“双重哈希”来模拟多个哈希函数。

先算出两个基础哈希：

h1 = hash_a(x)
h2 = hash_b(x)

然后构造第 i 个位置：

position_i = (h1 + i * h2) % m

这样只需要两次真正的哈希计算，就能得到 k 个位置。很多成熟实现都会采用类似思路，因为哈希计算往往比 bit 操作贵得多。

关键点不是“必须有 k 个完全独立的哈希函数”，而是这些位置要足够分散，不能大量挤在同一片 bit 上。哈希分布越差，误判率越容易偏离预期。

为什么需要无偏哈希

布隆过滤器的误判率公式有一个隐含前提：哈希结果要尽量均匀，也就是每个 bit 位置被选中的概率大致相同。

如果哈希函数有偏，问题会很快出现。比如 bit 数组长度是 1000，但某个哈希函数总是更容易落在前 100 个位置，那么这些位置会被很快打满，后面的 900 个位置却很少使用。这样即使 bit 数组整体看起来还没满，查询时也更容易碰到一组已经被置为 1 的位置，实际误判率会比公式估算高。

所以这里说的“无偏”不是指哈希值不能冲突。冲突一定会发生。它指的是：对大量不同输入来说，哈希结果落到 0..m-1 每个位置的机会应该尽量接近。

工程里通常要注意三点：

  • 使用分布质量可靠的哈希算法，不要随手拼接字符串长度、ID 后几位这类弱规则。
  • 如果用 hash(value) % m 映射位置，要确认原始哈希值已经足够均匀。严格来说，取模可能带来一点 modulo bias；如果使用 64 位哈希且 m 远小于 2^64，这点偏差通常可以忽略。
  • 不要只依赖低位 bit，除非你确定哈希算法的低位质量也足够好。有些哈希在低位上的分布比高位更差，直接用 hash & (m - 1) 可能会放大偏斜。

前面提到的双重哈希也建立在这个前提上：h1 和 h2 本身要有足够好的分布。如果基础哈希已经偏了，后面构造出来的多个位置也会跟着偏。

误判率怎么估算

布隆过滤器最容易被问到的问题是：bit 数组开多大？哈希函数用几个？

我们先定义几个变量：

变量含义
n预计插入的元素数量
mbit 数组长度
k哈希函数数量
p目标误判率

插入 n 个元素，每个元素设置 k 个 bit。一个特定 bit 在一次哈希后仍然是 0 的概率是：

1 - 1 / m

一共发生 k * n 次设置之后，它仍然是 0 的概率近似为：

(1 - 1 / m)^(k * n) ≈ e^(-k * n / m)

所以一个 bit 为 1 的概率大约是：

1 - e^(-k * n / m)

查询一个不存在的元素时，k 个位置都刚好为 1，就会误判。因此误判率近似为：

p ≈ (1 - e^(-k * n / m))^k

这个公式不用每次手算，但它能帮我们理解三个事实：

  • m 越大，bit 越不容易被填满，误判率越低。
  • n 越大，写入越多，误判率越高。
  • k 不是越大越好，太少不够区分，太多会更快把 bit 数组打满。

在给定 m 和 n 时，比较合适的哈希函数数量是：

k ≈ (m / n) * ln(2)

如果反过来，已经知道预计元素数量 n 和目标误判率 p，可以估算需要的 bit 数：

m ≈ -(n * ln(p)) / (ln(2)^2)

再用上面的公式算出 k。

一个容量估算例子

假设我们预计要放入 1000 万个用户 ID，希望误判率大约是 1%。

代入公式：

n = 10,000,000
p = 0.01

m ≈ -(n * ln(p)) / (ln(2)^2)
  ≈ 95,850,584 bit

换算成内存：

95,850,584 bit ÷ 8 ÷ 1024 ÷ 1024 ≈ 11.43 MB

合适的哈希函数数量：

k ≈ (m / n) * ln(2)
  ≈ 6.64

实际可以取 k = 7。

也就是说，用大约 12 MB 内存，就能为 1000 万个元素提供约 1% 误判率的存在性过滤。换成普通哈希集合，内存通常会高很多，因为它要保存完整 key 和哈希表结构。

它适合放在哪里

布隆过滤器最适合放在“昂贵查询”之前，先挡掉确定不存在的数据。

缓存穿透保护

一个常见链路是：

请求 -> 布隆过滤器 -> 缓存 -> 数据库

如果布隆过滤器判断 ID 一定不存在，直接返回空结果，不再访问缓存和数据库。

如果判断可能存在，再继续查缓存；缓存没命中时，再查数据库。

这能缓解大量无效 key 把数据库打穿的问题。注意它只是保护层，不是数据源。对于布隆过滤器判断“可能存在”的请求，后面仍然要查真正的数据。

爬虫 URL 去重

爬虫抓取页面时，需要判断某个 URL 是否已经见过。URL 数量可能非常大，如果全部放进精确集合，内存压力会很高。

布隆过滤器可以用来快速过滤“很可能见过”的 URL。代价是少量新 URL 可能被误判成已经见过，从而被跳过。

这个代价是否能接受，要看业务目标。如果是搜索引擎核心抓取链路，可能需要更复杂的去重系统；如果是日志分析、监控采样、内容发现任务，少量漏抓通常可以接受。

数据库和存储引擎

很多存储系统会在底层文件或数据块旁边放布隆过滤器。查询某个 key 时，先问布隆过滤器：

  • 如果它说一定不存在，就不用读磁盘文件。
  • 如果它说可能存在，再去读对应的数据块。

这种场景下，布隆过滤器节省的不是业务内存，而是昂贵的磁盘 IO。

黑名单和风控预过滤

如果有一批恶意 IP、设备 ID、账号 ID，可以用布隆过滤器做第一层快速判断。

但风控场景要特别小心：布隆过滤器会误判。它适合用来触发后续精确检查，不适合单独作为封禁依据。否则正常用户可能因为误判被拦截。

为什么它通常不支持删除

普通布隆过滤器没有办法安全删除一个元素。

原因是多个元素可能共享同一个 bit。比如：

A -> 2, 5, 9
B -> 5, 8, 13

位置 5 同时被 A 和 B 使用。如果删除 A 时直接把 2、5、9 都清零，就会影响 B。之后查询 B 时，发现位置 5 是 0，布隆过滤器会错误地回答“不存在”。

这会破坏布隆过滤器最重要的保证：不存在就一定不存在。

如果业务确实需要删除，可以使用 Counting Bloom Filter。它不再用一个 bit 表示位置，而是用一个小计数器：

  • 插入时，对应计数器加 1。
  • 删除时，对应计数器减 1。
  • 查询时，所有计数器都大于 0 才算可能存在。

代价是内存会增加，而且要处理计数器溢出、并发更新、重复删除等问题。很多场景会选择另一种更简单的办法：按时间窗口重建布隆过滤器。

比如每天生成一个新的过滤器，旧过滤器保留几天后丢弃。这样不需要单条删除，系统也更容易保持可控。

容量超过预期会发生什么

布隆过滤器创建时就隐含了一个前提：预计插入 n 个元素。

如果实际写入远远超过这个数量，bit 数组会越来越满。满到一定程度后，大部分位置都是 1，查询任何不存在的元素都很容易得到“可能存在”。

极端情况下，如果 bit 数组几乎全是 1，布隆过滤器就退化成了“永远放行”。它不会产生错误的“不存在”，但过滤效果基本没了。

所以线上使用时最好监控两个指标：

  • 已插入元素数量的估计值。
  • bit 位被置为 1 的比例。

当填充率过高时，可以扩容、重建，或者切换到可伸缩布隆过滤器。可伸缩布隆过滤器的思路是：旧过滤器满了以后，再挂一个新的过滤器；查询时依次检查多个过滤器。

工程实现里的几个坑

不要把 True 当成最终存在

这是最常见的错误。

if bloom.contains(user_id):
    return user

这样写是有问题的。布隆过滤器返回 True 只表示“可能存在”，后面必须继续查缓存、数据库或精确集合。

更合理的链路是：

if not bloom.contains(user_id):
    return None

return load_user_from_cache_or_db(user_id)

初始化数据要和真实数据对齐

如果用布隆过滤器保护数据库查询，过滤器里的数据必须来自可信数据源。常见做法是服务启动时从数据库或离线快照加载一遍，之后新增数据时同步写入过滤器。

这里要考虑一个时间窗口：新数据刚写入数据库，但还没写入布隆过滤器。如果这时查询新 key，过滤器会说“不存在”，请求就被错误拦掉。

解决方式可以是：

  • 写数据库成功后同步写布隆过滤器。
  • 通过消息队列异步更新，但查询链路要能容忍短暂延迟。
  • 对刚创建的数据走旁路策略，不完全依赖过滤器。

具体选哪种，取决于业务能不能接受短时间内查不到新数据。

哈希函数要稳定

布隆过滤器经常需要持久化、跨进程共享，或者在服务重启后继续使用。这个时候哈希结果必须稳定。

一些语言的默认哈希函数可能会为了安全原因在进程启动时加入随机种子。比如 Python 的内置 hash() 就不适合直接拿来做持久化布隆过滤器。

更稳妥的做法是使用明确的哈希算法，比如 MurmurHash、xxHash、SipHash、BLAKE 系列，并固定编码方式和种子。

分布式场景要先想清楚一致性

如果每个服务实例都有自己的本地布隆过滤器，就要考虑它们什么时候加载、什么时候更新、是否可能不一致。

如果使用 Redis 这类集中式组件保存布隆过滤器，一致性更简单，但每次查询都要多一次网络访问。这个访问成本是否值得，要看它能替你省掉多少数据库或远程存储压力。

布隆过滤器很小，不代表它在架构上没有状态。只要它影响请求是否继续往下走，就必须把更新、重建、回滚、热加载这些问题想清楚。

误判率不是固定不变的魔法数字

“1% 误判率”只在容量和哈希分布符合预期时成立。

如果元素数量超了、哈希分布差、bit 数组复用太久，实际误判率都会上升。线上最好把它当成一个需要维护的结构，而不是一次创建后永久正确的配置。

和哈希集合怎么选

如果你需要精确判断，或者要遍历元素、删除元素、取出原始 key，哈希集合更合适。

如果你只需要在昂贵查询前做一次快速过滤，并且能接受少量误判，布隆过滤器通常更划算。

可以用下面这张表快速判断：

问题更适合
必须 100% 精确判断存在哈希集合
查询“不存在”后要直接拦截布隆过滤器
需要保存并取回原始元素哈希集合
数据量很大，内存紧张布隆过滤器
需要频繁删除单个元素哈希集合或 Counting Bloom Filter
少量误判可以接受布隆过滤器

布隆过滤器不是哈希集合的替代品，而是一个更靠前的过滤层。它最好的位置通常不是“数据结构的终点”，而是“昂贵操作的入口”。

总结

布隆过滤器的设计非常克制：它不保存元素本身，只保存多个哈希位置对应的 bit。这个设计让它可以用很少的内存处理很大的数据量。

它的核心价值也来自这个取舍：

  • 查询结果为不存在时，可以相信。
  • 查询结果为存在时，只能继续验证。
  • 误判率可以通过 m、n、k 估算和控制。
  • 不适合直接删除，删除需求要换 Counting Bloom Filter 或按时间窗口重建。

如果你在系统里遇到的问题是“太多不存在的 key 正在消耗后端资源”，布隆过滤器往往值得考虑。它不能替你查到数据，但能用很便宜的方式告诉你：这个查询根本不该继续往下走。