图 1：本文封面，四件工具各管一段。
上一篇真题解析用位图解了「40 亿个整数里判断某个数在不在」这一道题，本文不再重复单题解法，而是把镜头拉远：海量集合问题在工程里有一整个工具箱，位图只是第一件。四件工具各自回答一个不同的问题，选错工具比不会用工具更常见。
第一件：位图，用值域换内存。
一个整数占一位，40 亿个位置只要约 500MB。它精确、支持交并差的位运算，天然适合用户标签、签到记录这类稠密整数集合。代价写在公式里：内存跟着值域上限走，不跟实际元素个数走——值域 40 亿但只存 100 个数，照样要 500MB。稀疏场景用它就是浪费。
第二件：布隆过滤器，允许小概率说错「在」。
不存元素本身，只把每个元素用 k 个哈希函数打到 k 个位上。查询时 k 个位全亮才说「可能在」，任何一个位没亮就敢说「一定不在」。误判只有单向：说「在」可能错，说「不在」永远对。内存账可以算得很细：目标误判率 p 时，每元素需要 -ln(p)/(ln2)² 位，按 Redis 官方文档给出的换算，1% 误判率约 9.6 位、0.1% 约 14.4 位——存 1 亿个元素、容忍 1% 误判，只要约 120MB。代价是不能删元素（位被多个元素共享），也不能回答「到底有哪些」。
第三件：Roaring Bitmap，稀疏数据的压缩位图。
裸位图的死穴是稀疏，Roaring 的解法是把 32 位整数按高 16 位分桶：值域被切成 65536 个桶，每个桶管 65536 个值，桶内按稠密度自动选容器——稀疏桶用有序数组，稠密桶用 8KB 位图，连续区间用行程编码。空桶根本不占空间。结果是：稀疏数据下比裸位图省几个数量级的内存，同时保留精确的交并运算和随机访问能力。这也是它被 Lucene、Druid、ClickHouse 等系统普遍采用的原因。
第四件：HyperLogLog，只数个数，不记成员。
前面三件都在回答「在不在」，HyperLogLog 回答的是另一个问题：「有多少个不同的」。它利用哈希值中前导零的分布估计基数，Redis 的实现固定至多 12KB 内存、标准误差约 0.81%，就能估算亿级 UV。代价同样鲜明：只能给估算值，且完全无法回答存在性——它连「某个用户来没来过」都不知道。
图 2：四种结构的能力边界与选型坐标系。
亲手验证一次误判率公式。
公式听起来抽象，跑一遍就实了。下面这份代码实现一个迷你布隆过滤器，按公式配位数组与哈希数，再用 10 万个没存过的元素实测误判率。用 Node.js 22.15.0 直接运行（node bloom.js）即可：
'use strict';
// 迷你布隆过滤器：验证「误判率目标 -> 每元素位数」换算公式
// 公式：每元素位数 m/n = -ln(p) / (ln2)^2；最优哈希数 k = (m/n) * ln2
import { createHash } from 'node:crypto';
function bloomParams(n, p) {
const bitsPerItem = -Math.log(p) / (Math.LN2 ** 2);
const m = Math.ceil(n * bitsPerItem);
const k = Math.ceil((m / n) * Math.LN2);
return { m, k };
}
class Bloom {
constructor(m, k) { this.m = m; this.k = k; this.bits = new Uint8Array(Math.ceil(m / 8)); }
#hashes(item) {
// 双哈希派生 k 个位址
const h1 = createHash('md5').update(item).digest().readUInt32LE(0);
const h2 = createHash('md5').update('salt:' + item).digest().readUInt32LE(0);
const out = [];
for (let i = 0; i < this.k; i++) out.push((h1 + i * h2) % this.m);
return out;
}
add(item) { for (const pos of this.#hashes(item)) this.bits[pos >> 3] |= 1 << (pos & 7); }
maybeHas(item) { return this.#hashes(item).every((pos) => (this.bits[pos >> 3] >> (pos & 7)) & 1); }
}
const n = 10000; // 计划存入 1 万个元素
for (const p of [0.01, 0.001]) {
const { m, k } = bloomParams(n, p);
const bf = new Bloom(m, k);
for (let i = 0; i < n; i++) bf.add(`user-${i}`);
let falsePos = 0;
const probes = 100000;
for (let i = 0; i < probes; i++) if (bf.maybeHas(`ghost-${i}`)) falsePos++;
const actual = falsePos / probes;
console.log(`目标误判率 ${(p * 100).toFixed(1)}%：位数组 ${m} 位（每元素 ${(m / n).toFixed(2)} 位），哈希数 ${k}，实测误判率 ${(actual * 100).toFixed(2)}%`);
}
// 「一定不存在」的保证：已存入元素绝不会误报不存在
const { m, k } = bloomParams(100, 0.01);
const bf = new Bloom(m, k);
bf.add('hello');
console.log(`已存入的 hello：maybeHas=${bf.maybeHas('hello')}（布隆过滤器对已存入元素永不说「不在」）`);
console.log(`没存过的 world：maybeHas=${bf.maybeHas('world')}（说「在」可能错，说「不在」一定对）`);
实测输出：
目标误判率 1.0%：位数组 95851 位（每元素 9.59 位），哈希数 7，实测误判率 1.04%
目标误判率 0.1%：位数组 143776 位（每元素 14.38 位），哈希数 10，实测误判率 0.09%
已存入的 hello：maybeHas=true（布隆过滤器对已存入元素永不说「不在」）
没存过的 world：maybeHas=false（说「在」可能错，说「不在」一定对）
实测值与公式预测几乎重合：9.59 位对 1.04%、14.38 位对 0.09%，「不在一定对、在可能错」的单向性也在最后两行得到验证。
选型两步走与常见误区。
先问业务要精确答案还是估算，再看值域稠密度：要精确且稠密，位图；要精确但稀疏，Roaring；只要存在性且能容忍误判，布隆过滤器；只要去重计数，HyperLogLog。常见误区三个：拿布隆过滤器当权威数据源用，忘了它的误判是单向的、说「在」必须回查一次真实存储；给稀疏大值域上裸位图，内存跟着值域爆炸；拿 HyperLogLog 回答存在性，它根本不记录成员。你的业务里这四件工具用对位置了吗？欢迎聊聊你的选型经历。