随机化与近似结构
布隆过滤器
它解决的那个问题
「这个 URL 爬过吗」「这个手机号注册过吗」「这个 key 在数据库里吗」—— 共同形状是海量集合的存在性判断，而且答「不在」时希望立刻返回、不要去查后端。
用 Set 存全部键当然可以，但键本身要占空间。100 万个短字符串（key-0…），
Node v22 上实测 50.45 MB。布隆过滤器做同样的事，按位存只要 1.19 MB，约 1/42。
⭐ 代价写在名字里：它是个过滤器，不是集合。
查询返回「不在」 → 一定不在 ✅ 可以信
查询返回「在」 → 可能在，也可能是误判📌 所以典型用法是挡在慢查询前面：布隆说不在就直接返回， 布隆说在才去查数据库。误判只会让你多查一次库，不会给出错误答案。
结构：一个位数组 + k 个哈希
function createBloom(m, k) { // m 位，k 个哈希函数
const bits = new Uint8Array(m);
// 用一个哈希函数配不同的种子，省掉实现 k 个独立哈希
const h = (s, i) => {
let x = (2166136261 ^ Math.imul(i + 1, 2654435761)) >>> 0;
for (let j = 0; j < s.length; j++) {
x ^= s.charCodeAt(j);
x = Math.imul(x, 16777619);
}
x ^= x >>> 16; x = Math.imul(x, 2246822507); // ⭐ 这三行是关键，别省
x ^= x >>> 13; x = Math.imul(x, 3266489909); // 省掉它 k 个哈希就不独立
return ((x ^ (x >>> 16)) >>> 0) % m;
};
return {
add(s) { for (let i = 0; i < k; i++) bits[h(s, i)] = 1; },
has(s) { for (let i = 0; i < k; i++) if (!bits[h(s, i)]) return false; return true; },
};
}⭐ 全部逻辑就这两行：加入时把 k 个位置全置 1；查询时只要有一位是 0 就一定没加过。
⚠️ 那三行收尾混合看着像装饰，其实是这个结构能不能用的分水岭 —— 省掉它，误判率会系统性地高出一到两成，见下面「k 个哈希真的独立吗」一节。
「有一位是 0 就一定没加过」这句是它不会漏判的全部依据。这一条是结构性的， 实测把位数组灌到 100% 全满也不漏判：
n= 800 m=10000 k=7 位填充 43% 漏判 0
n= 800 m= 1000 k=7 位填充 100% 漏判 0
n= 800 m= 100 k=7 位填充 100% 漏判 0
n=50000 m= 1000 k=7 位填充 100% 漏判 0 合计 57400 次查询，漏判 0📌 位填充 100% 时它对所有键都说「在」—— 完全没用，但依然不漏判。 ⭐ 这正是布隆的保证的形状：它只会变得更没用，不会变得不正确。
🚨 上面那份代码占 9.54 MB，不是 1.19 MB
new Uint8Array(m) 里的 m 是位数，而 Uint8Array 一个格子是一个字节 ——
这份代码是一个字节存一位，白白多用 8 倍。100 万键、m/n=10 时实测：
Set 存一百万个短字符串 50.45 MB （三次测量完全一致）
上面那份 Uint8Array(m) 9.54 MB ← 一字节一位，8 倍浪费
真按位存 Uint8Array(m >> 3) 1.19 MB ← 开头那个数字说的是它⭐ 上面那份留成一字节一位是为了讲清楚逻辑。真要省空间，改三处就行：
const bits = new Uint8Array(m >> 3); // 位数 / 8
add(s) { for (let i=0;i<k;i++){ const p=h(s,i); bits[p>>3] |= 1 << (p&7); } },
has(s) { for (let i=0;i<k;i++){ const p=h(s,i); if(!(bits[p>>3] & 1<<(p&7))) return false; } return true; },⚠️ 顺带一个量内存时的坑：TypedArray 算在 external 里，不进 heapUsed。
只看 heapUsed 会量出布隆「占 0.01 MB」，看着像天大的胜利，其实是量具没读到。
误判率：能算，也对得上
误判发生在「k 个位置恰好都被别的键置过 1」。概率是：
p_误判 = (1 - e^(-k·n/m))^k n = 已插入元素数，m = 位数，k = 哈希个数⚠️ 公式好看不算数，实测才算。换 20 组不同前缀的 key 各测一遍，每组查 20 万个 不存在的键（只测一组毫无意义，原因见下一节）：
n m k m/n 理论 实测中位数 最小~最大 位填充率(实测/理论)
1000 10000 7 10.0 0.82% 0.81% 0.78 ~ 0.94 50% / 50%
1000 8000 6 8.0 2.16% 2.19% 1.96 ~ 2.32 53% / 53%
1000 4000 3 4.0 14.69% 14.69% 13.68 ~ 15.73 53% / 53%
2000 10000 7 5.0 13.78% 13.70% 13.00 ~ 14.53 75% / 75%
5000 10000 7 2.0 80.68% 80.63% 79.45 ~ 82.22 97% / 97%⭐ 五行的中位数都落在理论值上（相对偏差最大 1.6%），这个公式是真的能用来定参数的。
⭐ 最后一行是这张表的重点：m/n 从 10 掉到 2，误判率从 0.8% 飙到 81%。
位填充率也从 50% 涨到 97% —— 位数组几乎全是 1，那 has 自然什么都说「在」。
🚨 所以布隆过滤器必须按预估的元素总量提前把 m 算好。 它不像哈希表能扩容 —— 位数组一旦装满，唯一的办法是新建一个更大的重新灌一遍。 ⚠️ 「先小点，不够再说」在这里是行不通的，因为没有报错， 只是误判率悄悄从 1% 变成 81%，而调用方完全感觉不到。
🚨 k 个哈希真的独立吗：病根不在种子，在出口
「用一个哈希配 k 个种子」这个省事办法是对的。最容易写出来的版本是
let x = 2166136261 ^ i，配上裸的 FNV-1a 循环，跑起来一切正常 ——
但它有一个可以精确证明的毛病：
FNV-1a 每轮做 x = (x ^ c) * 16777619，乘数是奇数
→ 乘法的进位只往高位走，异或不跨位
→ 最终 bit0 = 种子的 bit0 ⊕ 各字符的 bit0，一条线性式子
而种子的 bit0 随 i 变（2166136261 ^ i 是这样，i 乘个奇数也是这样）
再加上 m=10000 是偶数，x % m 与 x 同奇偶
→ k 个位置的奇偶被 i 的奇偶完全锁死不是推测。实测 2000 个键 × k=7，位置奇偶严格交替，零反例：
key-0 的 7 个位置 8857 6286 2043 5184 525 9746 7503
奇偶 1 0 1 0 1 0 1
key-1 的 7 个位置 1238 3905 4424 2803 2906 7365 9884
奇偶 0 1 0 1 0 1 0⭐ 修哪儿？直觉会说「种子太弱，换个散一点的」—— 实测这条路是错的。 把「种子打散」和「出口加收尾混合」拆开各测一遍（每格 20 组 key 的中位数）：
n=1000 n=1000 n=2000 n=5000
m=10000 m=4000 m=10000 m=10000
理论 0.82% 14.69% 13.78% 80.68%
① ^i 种子 + 无混合 0.99% +21% 16.35% +11% 15.33% +11% 82.59% +2%
② ^i 种子 + 有混合 0.81% -1% 14.66% -0% 13.64% -1% 80.28% -0%
③ 打散种子 + 无混合 0.88% +8% 16.39% +12% 15.73% +14% 82.44% +2%
④ 两处都做 0.81% -1% 14.69% -0% 13.70% -1% 80.63% -0%🚨 只换种子（③）几乎没用，只加收尾混合（②）就完全修好了。
奇偶锁死的检出率也一样：①③ 都是 100%，②④ 掉到 1.7% / 1.5%（随机水平）。
📌 原因是上面那条线性式子 —— Math.imul(i+1, 2654435761) 乘的还是奇数，
bit0 照样随 i 变。种子怎么换都躲不开，只有在出口把位彻底搅一遍才行。
🚨 除了均值偏高，更要命的是散布：① 的第三行在 20 组 key 上从 13.20% 跳到 19.44%，而抽样噪声只有 ±0.079%。换一批 key 就换一个误判率， 公式失去预测力。加了混合之后同一行是 13.68~15.73%，中位数精确等于理论值。
⭐ 判据：实测误判率系统性高于公式（而不是围着公式上下抖），就是哈希在结块。
📌 最省事的自测：m 取质数（比如 10007）再跑一遍。奇偶那个结构会消失
（实测符合率从 100% 掉到 1.4%），如果误判率跟着降了，问题就在哈希不在参数。
⭐ k 取多少：一条 U 形曲线
固定 m/n = 10，k 从 1 试到 14（20 组 key，每组查 10 万次）：
k 理论 实测中位数 最小~最大 k 理论 实测中位数
1 9.52% 9.52% 9.36~9.65 7 0.82% 0.81% ← 最低
2 3.29% 3.25% 3.17~3.42 8 0.85% 0.83%
3 1.74% 1.71% 1.64~1.85 9 0.91% 0.91%
4 1.18% 1.16% 1.09~1.32 10 1.02% 1.00%
5 0.94% 0.92% 0.88~1.02 12 1.36% 1.35%
6 0.84% 0.82% 0.77~0.90 14 1.90% 1.85%两头都差：k 太小，位用得不够，随便撞上；k 太大，位数组填得太满，
反而更容易全中。最优值在 k = (m/n)·ln2 —— 这里是 10 × 0.693 ≈ 6.93，
实测最低点正是 k=7。
⚠️ 但 k=6、7、8 的实测区间（0.770.90 / 0.760.91 / 0.780.96）几乎完全重叠，
理论值也只差 0.03 个百分点。曲线在最低点附近是平的，纠结 6 还是 7 没有意义 ——
真正要避开的是 k=13 和 k≥12 那两头。
📌 记这一条就够：先按能接受的误判率定 m/n，再用 (m/n)·ln2 算 k。
常用档位（同样 20 组 key，每组 50 万次）：
m/n=10 k=7 理论 0.819% 实测中位数 0.812% （区间 0.746~0.912%）
m/n=15 k=10 理论 0.074% 实测中位数 0.076% （区间 0.068~0.091%）🚨 为什么不能删除
很自然的想法是「删除就把那 k 位置回 0」。不行。
位是共享的：某一位可能同时属于好几个键。置 0 会把那些键一起删掉。
del(s) { for (let i = 0; i < k; i++) bits[h(s, i)] = 0; } // ❌ 会误伤别人实测：m=10000、k=7、装入 500 个键，随机删掉其中 1 个，重复 2000 次 —— 剩下 499 个里中位数有 2 个查不到，最坏一次伤了 11 个：
m k 被误伤的键数：中位数 p10~p90 2000 次里最坏 理论期望 499·(1-(1-k/m)^k)
10000 7 2 1~ 5 11 2.44
5000 7 5 2~ 8 14 4.87
2000 7 12 8~17 25 12.10
1000 7 24 18~30 37 23.94⚠️ 报 p10p90 而不报「最小最大」是有原因的：极值不稳定，重复次数一变就变。
换 8 个随机种子各跑 2000 次，中位数与 p10/p90 逐格一模一样（只有最后一行的
p90 在 29 和 30 之间摆），而「最坏一次」每个种子都不同。
⭐ 报统计量之前，先换几个种子看它稳不稳 —— 稳的才配写进正文。
⚠️ 位数组越挤，一次删除的杀伤面越大 —— 而这正是你会想删东西的场景。 ⚠️ 更糟的是这个错破坏了布隆唯一的保证：本来「说不在就一定不在」， 删除之后连这条都不成立了 —— 上游代码正是靠这条才敢直接返回。
⭐ 真要删除，用计数布隆过滤器：每个位置从 1 位换成 4 位计数器， 加入时 +1、删除时 -1。代价是空间变成 4 倍，也就退掉了布隆一半的优势。
面试怎么答
被问「海量数据判断是否存在」，一个完整的回答包含四段：
- 结构：位数组 + k 个哈希，加入置 1、查询全查
- 保证：说「不在」一定对，说「在」可能错 —— 所以只能做前置过滤
- 定参：按可接受误判率定 m/n，
k = (m/n)·ln2；1% 大约 10 bit/键 - 限制：不能删除（位共享）、不能扩容（要重建）、装填过量会静默劣化
⭐ 第 4 点最能体现有没有真用过 —— 前三点背得到， 「误判率会悄悄从 1% 变成 81% 而不报错」这种话只有量过的人才说得出。
📌 还想再加一层就说第 5 点：k 个哈希必须真的独立。 拿 FNV-1a 配 k 个种子直接用，k 个位置的奇偶会被锁死，误判率系统性高出一到两成、 而且换批 key 就变 —— 公式还在，预测力没了。 ⭐ 加一句「而且换种子修不好，得在出口做一遍收尾混合」，就说明是真量过的。
⚠️ 关于配套题
力扣上没有布隆过滤器的题 —— 它是面试问答题，不是判题器上的题。 下面那两道是「最接近的思路题」：设计哈希集合是它的确定性版本， 对照着写一遍能想清楚「省掉键本身」到底省了什么。
下一步
布隆用误判率换空间。下一篇的一致性哈希 换的是另一样东西：它放弃「绝对均匀」，换来扩容时只迁移少量数据 —— 实测简单取模要搬 83.3%，一致性哈希只搬 16.6%，恰好是理论下界。 ⭐ 那一篇会撞上同一个坑的另一面：哈希不够散，虚拟节点加多少个都没用。
练习
勾选记录做过哪些，0 / 2 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。
- 705. 设计哈希集合简单布隆的确定性版本；对照着看能想清楚「省掉键本身」省了什么
- 1396. 设计地铁系统中等哈希做多键索引；工程里这类统计常配布隆做前置过滤
⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。