位图、布隆过滤器与前缀树：海量数据的判存与过滤
「40 亿个 QQ 号，1GB 内存，判断某个号码在不在」——这类问题的解法都指向同一件事：放弃存原始数据，只存足够回答问题的信息。实测在 2000 万的范围内标记 1000 万个整数，
HashSet占 522MB，位图只占 2.4MB。
本文实测三种判存结构的内存与误判率，以及敏感词过滤中前缀树相对逐词匹配的差距。实验在 JDK 21 上完成，内存用 JOL 按对象图统计，见文末配套实验。
一、先说结论
- 键是连续整数、要求精确 → 位图。 实测 2000 万范围的位图占 2.4MB，是同样数据的
HashSet的 1/219；40 亿个整数的位图约 0.47GB，能放进 1GB 内存。 - 键是任意字符串、能接受误判 → 布隆过滤器。 实测 100 万个 URL，目标误判率 1% 时占 1.1MB，实际误判率 1.011%，且已加入的元素不会被判为不存在。
- 数据稀疏时位图很浪费，改用 RoaringBitmap 这类压缩位图。
- 敏感词过滤用前缀树（DFA），实测 1 万个词、20 万字文本：前缀树 4.9ms，逐词
indexOf788.1ms，相差 160 倍。 - 组合使用最实用：布隆过滤器挡住绝大多数不存在的请求，剩下的再查精确存储。
二、三种判存结构
2.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：它把整数空间分块，稠密块用位图、稀疏块用有序数组，在稀疏场景下能省几个数量级。
- 只能回答「在不在」，不能存额外信息。
2.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（每位换成计数器，空间翻几倍），或者定期重建。
2.3 组合使用：黑名单网址过滤
实际系统通常是三层：
请求 → 本地布隆过滤器（1MB，挡住 99% 的正常网址）
→ Redis 精确集合（命中布隆后再查，排除误判）
→ 数据库（Redis 未命中时兜底，并回填）这样既控制了内存，又保证了结果准确：布隆过滤器说「不存在」就直接放行（不会漏判），说「可能存在」才继续查精确存储。
三、敏感词过滤
3.1 逐词匹配为什么慢
for (String word : words) { // 1 万个敏感词
if (text.contains(word)) { ... } // 每次都要扫描整篇文本
}文本长度 L、词数 N，复杂度是 O(N × L)——文本被扫描了 1 万遍。
3.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 字，平均每千字埋一个词）。
3.3 实际系统还要处理什么
前缀树只解决了「精确匹配」，真实的内容过滤还要应对对抗：
- 变形词：拼音、同音字、繁体、字符间插入符号（
敏*感*词）。常见做法是先归一化（转小写、去除非字母数字、繁转简、全角转半角），再匹配。 - 误伤：正常词汇包含敏感词片段时要有白名单。
- 词库更新：前缀树需要重建，可以用「双缓冲」——后台构建新树，构建完原子替换引用。
- 分级处理：不同级别的词对应不同动作（替换、拦截、人工审核），而不是一刀切。
如果需求复杂，成熟的开源实现（如 Aho-Corasick 自动机的各种 Java 实现）比自己写更可靠——它在匹配失败时能跳到最长公共后缀继续，避免回退，复杂度更优。
四、怎么选
| 问题 | 结构 |
|---|---|
| 连续整数，要求精确，数据稠密 | 位图 |
| 整数稀疏 | RoaringBitmap |
| 任意键，能接受少量误判 | 布隆过滤器 |
| 任意键，要求精确且数据量不大 | HashSet / Redis Set |
| 大量关键词的文本匹配 | 前缀树 / Aho-Corasick |
| 只要基数（有多少个不同的） | HyperLogLog，见 Redis 数据结构与编码 |
选择的依据是三个问题：键能不能变成整数、能不能接受误判、数据稠不稠密。
五、常见误区
- 「布隆过滤器会漏判」：不会。它只会把不存在的判成存在，实测已加入元素的漏判数为 0。
- 「误判率可以调到 0」：不能，只能趋近；代价是位数组线性增长。
- 「位图一定省内存」：数据稀疏时非常浪费，要用压缩位图。
- 「敏感词过滤就是遍历词库」：实测慢 160 倍，且真实场景还要处理变形词。
- 「用了布隆过滤器就不用查数据库」：命中「可能存在」时仍然要查精确存储。
小结
这类问题的思路是统一的：先想清楚要回答什么问题，再选择「只够回答这个问题」的结构。判断「在不在」不需要存原始值——位图用一个 bit，布隆过滤器用几个 bit 换一点误判率；匹配大量关键词不需要逐个比较——前缀树把公共前缀合并，一遍扫描就够。内存和时间的数量级差距，往往就来自这一次选择。
配套实验
- codesphere-labs/system-design/dedup-and-filter：位图与
HashSet的内存、布隆过滤器的误判率与漏判、前缀树与逐词indexOf的耗时（验证记录）
参考资料