位图、布隆过滤器与前缀树：海量数据的判存与过滤

「40 亿个 QQ 号，1GB 内存，判断某个号码在不在」——这类问题的解法都指向同一件事：放弃存原始数据，只存足够回答问题的信息。实测在 2000 万的范围内标记 1000 万个整数，HashSet 占 522MB，位图只占 2.4MB。

本文实测三种判存结构的内存与误判率，以及敏感词过滤中前缀树相对逐词匹配的差距。实验在 JDK 21 上完成，内存用 JOL 按对象图统计，见文末配套实验。

一、三种判存结构

图 1 · 位图适合连续整数且要求精确；布隆过滤器用可控的误判率换极小的空间；哈希表精确但最占内存

1.1 位图：一个整数一个 bit

BitSet bits = new BitSet(20_000_000);
bits.set(qqNumber);                  // 标记存在
boolean exists = bits.get(qqNumber); // 判断
int count = bits.cardinality();      // 有多少个

实测 2000 万范围内标记 1000 万个整数：

结构	内存	倍数
BitSet(20_000_000)	2,441 KB	1×
HashSet<Integer>	534,286 KB	219×

差距来自存储方式：HashSet 每个元素都要存 Integer 对象（16 字节）、Node 对象（32 字节）和数组槽位，而位图每个数字只占 1 bit。

40 亿个 QQ 号：位图需要 4,000,000,000 / 8 = 500MB（实际 0.47GB），1GB 内存放得下；如果用 long[] 存原始值则需要 29.8GB。

位图的限制也很明确：

• 键必须能映射成有限范围的整数。 字符串 ID、UUID 要先映射，映射表本身可能比位图还大。
• 稀疏数据浪费严重。 只标记 1000 个用户但 ID 分布在 40 亿范围内，位图仍然要 500MB。这时用 RoaringBitmap：它把整数空间分块，稠密块用位图、稀疏块用有序数组，在稀疏场景下能省几个数量级。
• 只能回答「在不在」，不能存额外信息。

1.2 布隆过滤器：用误判率换空间

布隆过滤器用 k 个哈希函数把元素映射到位数组的 k 个位置并置 1。查询时如果 k 个位置都是 1，说明「可能存在」；只要有一位是 0，说明「一定不存在」。

实测 100 万个 URL：

目标误判率	位数组	哈希函数个数	实测误判率	漏判
1%	9,585,059 bit（1,170 KB）	7	1.011%	0
0.1%	14,377,588 bit（1,755 KB）	10	0.104%	0

对比：同样 100 万个 URL（约 40 字节）放进 HashSet<String>，实测占 117,567KB，约 115MB。实测的误判率用另外 100 万个没有加入的 URL 统计。

两个关键性质：

• 不会漏判（no false negative）：实测 100 万个已加入元素，判断为「不存在」的有 0 个。所以它适合做「快速排除」。前提是没有删除元素、没有重建过滤器，写入和查询用的是同一组哈希函数与参数。
• 会误判（false positive）：判断为「存在」的可能实际不存在，误判率与位数组大小和哈希个数有关。

参数怎么定（n 是元素数量，p 是目标误判率）：

位数组大小 m = -n × ln(p) / (ln2)²
哈希个数   k = (m / n) × ln2

实际工程中直接用 Guava 的 BloomFilter 或 Redis 的布隆过滤器模块，不用自己实现。

标准布隆过滤器不支持删除（把某一位清零会影响其他元素）。需要删除时用 Counting Bloom Filter（每位换成计数器，空间翻几倍），或者定期重建。

误判率只能趋近 0，不能等于 0：要求越低，位数组越大，大小随 -ln(p) 线性增长。

1.3 组合使用：黑名单网址过滤

实际系统通常是三层：

请求 → 本地布隆过滤器（1MB，挡住 99% 的正常网址）
     → Redis 精确集合（命中布隆后再查，排除误判）
     → 数据库（Redis 未命中时兜底，并回填）

这样既控制了内存，又保证了结果准确：布隆过滤器说「不存在」就直接放行（不会漏判），说「可能存在」才继续查精确存储。

1.4 「一定不存在」的前提：元素真的被加入过

「不会漏判」有一个前提：要判断的元素已经被加入了过滤器。过滤器只知道自己被告知过什么，它和数据库之间的同步是另一件事：

过滤器由 10000 个已有邮箱构建：已加入的邮箱里被判为不存在的 0 个
构建之后又写入 100 个，写路径没有更新过滤器：这 100 个已存在的邮箱，被判为「一定不存在」的 100 个
重建到一半就切换：已存在的 10100 个邮箱里，被判为不存在的 5100 个

过滤器由某个时刻的快照构建，之后写入的数据如果没有同步加入，过滤器对它们说的「一定不存在」就是错的；重建过滤器时，新的过滤器加载完之前也不能切换。上面黑名单的例子里，这意味着新加入黑名单的网址会被直接放行。

另一类问题出在并发上。用过滤器做「注册前查重」时，两个请求同时到达：

没有唯一约束的表：两个请求都查到「一定不存在」，结果：插入成功 2 个；表里同一邮箱 2 行
有唯一约束的表：两个请求的结果：插入成功 1 个，被唯一约束拒绝（UNIQUE constraint failed: users.email） 1 个；表里同一邮箱 1 行

两个请求都在对方插入之前查了过滤器，都得到「一定不存在」。这和先查后插在数据库里的问题一样：检查和写入之间有窗口。所以布隆过滤器只能作为减少查询的前置过滤，唯一性必须由数据库的唯一约束保证，冲突时按约束错误处理。

二、敏感词过滤

图 2 · 逐词匹配要把整篇文本扫 N 遍；前缀树沿着文本走一遍，每个位置最多向下走词的长度

2.1 逐词匹配为什么慢

for (String word : words) {          // 1 万个敏感词
    if (text.contains(word)) { ... } // 每次都要扫描整篇文本
}

文本长度 L、词数 N，复杂度是 O(N × L)——文本被扫描了 1 万遍。

2.2 前缀树（DFA）

把所有敏感词构建成一棵树，公共前缀共享节点。扫描时沿文本走一遍，每个位置最多向下走「最长词的长度」：

static class Node {
    Map<Character, Node> next = new HashMap<>();
    boolean end;
}

static int countHits(Node root, String text) {
    int hits = 0;
    for (int i = 0; i < text.length(); i++) {
        Node cur = root;
        for (int j = i; j < text.length(); j++) {
            cur = cur.next.get(text.charAt(j));
            if (cur == null) break;             // 这个起点走不下去了
            if (cur.end) hits++;                // 命中一个词，继续向下找更长的词
        }
    }
    return hits;
}

实测 1 万个敏感词、20 万字文本：

方式	耗时	命中次数
前缀树扫描	4.9ms	226
逐词 indexOf	788.1ms	226

两种方法都统计所有出现位置，结果一致，速度相差 160 倍。耗时是预热 2 次后 5 次的中位数；词和文本随机生成（每个词 3—5 字，平均每千字埋一个词）。

2.3 实际系统还要处理什么

前缀树只解决了「精确匹配」，真实的内容过滤还要应对对抗：

• 变形词：拼音、同音字、繁体、字符间插入符号（敏*感*词）。常见做法是先归一化（转小写、去除非字母数字、繁转简、全角转半角），再匹配。
• 误伤：正常词汇包含敏感词片段时要有白名单。
• 词库更新：前缀树需要重建，可以用「双缓冲」——后台构建新树，构建完原子替换引用。
• 分级处理：不同级别的词对应不同动作（替换、拦截、人工审核），而不是一刀切。

如果需求复杂，成熟的开源实现（如 Aho-Corasick 自动机的各种 Java 实现）比自己写更可靠——它在匹配失败时能跳到最长公共后缀继续，避免回退，复杂度更优。

三、怎么选

问题	结构
连续整数，要求精确，数据稠密	位图
整数稀疏	RoaringBitmap
任意键，能接受少量误判	布隆过滤器
任意键，要求精确且数据量不大	HashSet / Redis Set
大量关键词的文本匹配	前缀树 / Aho-Corasick
只要基数（有多少个不同的）	HyperLogLog，见 Redis 数据结构与编码

选择的依据是三个问题：键能不能变成整数、能不能接受误判、数据稠不稠密。

四、思路是统一的

这类问题的思路是统一的：先想清楚要回答什么问题，再选择「只够回答这个问题」的结构。判断「在不在」不需要存原始值——位图用一个 bit，布隆过滤器用几个 bit 换一点误判率；匹配大量关键词不需要逐个比较——前缀树把公共前缀合并，一遍扫描就够。内存和时间的数量级差距，往往就来自这一次选择。

---

配套实验

• codesphere-labs/system-design/dedup-and-filter：位图与 HashSet 的内存、布隆过滤器的误判率与漏判、前缀树与逐词 indexOf 的耗时（验证记录）
• codesphere-labs/system-design/bloom-not-a-constraint：Python 3.14.8、SQLite：快照构建后未同步的写入、重建期间切换、并发先查再插与唯一约束（验证记录）

参考资料

• JDK 21：BitSet
• Guava：BloomFilter
• RoaringBitmap
• Redis：Bloom filter（Redis Open Source 模块）