图 1：本文封面——一大一小两个集合的交集区域。
先说明属性：这是一篇历史题目复盘，题目出自本地历史面试资料（见文末来源说明），与任何公司的当前招聘无关。海量数据求交集是数据处理面试的经典题型，面试官想看的不是某个数据结构，而是你「先问规模、再选方案」的决策路径。
想象面试现场，面试官给出两个集合：一个 5000 万个 URL，一个 500 个 URL，如何快速找出交集？
第一步，审题：先问两个问题。
问题一：较小的那个集合装得下内存吗？问题二：业务上能不能容忍小概率误判？这两个问题的答案决定方案，而不是反过来先想一个方案再往题目上套。这也是所有海量数据题的通用开场。
第二步，基础回答：装得下，就用哈希集合。
本题里 500 个 URL 毫无内存压力。做法是把小集合建成哈希集合，然后流式扫大集合——逐个 URL 查「在不在集合里」，在就是交集成员。哈希查询近似 O(1)，全程一遍扫描，时间 O(n)，结果精确，零误判。大集合甚至不需要装进内存，按行流式读取即可，这才是「5000 万」这个数字该被处理的方式。
第三步，进阶回答：两边都海量怎么办。
把题目改一改：如果是 5000 万对 5000 万，小集合也装不下了呢？两条路。
方案 A，布隆过滤器。它是一个位数组加 k 个哈希函数：加入元素时把 k 个哈希位置的比特置 1；查询时若 k 个位置有任何一个为 0，则元素一定不在；全为 1 则可能在——有小概率误判（把不在的报成在），但绝不漏判。内存占用极小，代价是误判率与不支持标准删除。判为「可能在」的候选，再回源确认一次，就得到了精确结果。
方案 B，哈希切分。两个集合按同一规则 hash(url) mod N 切成 N 个小文件，同一个 URL 在两个集合里的哈希值相同，必然落进同一编号的小文件。然后对应编号两两求交——每个小文件都装得下内存了，问题退化回第二步。精确、无误判，代价是多轮磁盘读写。
图 2：按「装不装得下、容不容误判」两问展开的决策路径。
第四步，用代码把两种方案都跑一遍。
下面这份代码同时实现哈希集合精确求交与布隆过滤器粗筛，用 5 万个 URL 对 500 个 URL 实测，Node.js 22.15.0 直接运行（node url-intersection.js）：
'use strict';
// 方案一：小集合装得下内存 → 哈希集合精确求交
function intersectBySet(big, small) {
const set = new Set(small);
return big.filter((url) => set.has(url));
}
// 方案二：两边都海量 → 布隆过滤器粗筛，判「可能在」的回源确认
class BloomFilter {
constructor(bitCount, hashCount) {
this.bits = new Uint8Array(bitCount);
this.bitCount = bitCount;
this.hashCount = hashCount;
}
#hash(str, seed) {
// FNV-1a 变体：不同 seed 充当 k 个独立哈希函数
let h = (0x811c9dc5 ^ seed) >>> 0;
for (let i = 0; i < str.length; i++) {
h ^= str.charCodeAt(i);
h = Math.imul(h, 0x01000193) >>> 0;
}
return h % this.bitCount;
}
add(str) {
for (let k = 0; k < this.hashCount; k++) {
this.bits[this.#hash(str, (k + 1) * 0x9e3779b1)] = 1;
}
}
mightContain(str) {
for (let k = 0; k < this.hashCount; k++) {
if (!this.bits[this.#hash(str, (k + 1) * 0x9e3779b1)]) return false; // 有位为 0 → 一定不在
}
return true; // 所有位都是 1 → 可能在（可能误判）
}
}
// 造数据：大集合 5 万个，小集合 500 个，其中 120 个与大集合重叠
const big = [];
for (let i = 0; i < 50000; i++) big.push(`https://example.com/page/${i}`);
const small = [];
for (let i = 0; i < 120; i++) small.push(`https://example.com/page/${i * 100}`); // 真交集
for (let i = 0; i < 380; i++) small.push(`https://other.com/item/${i}`); // 不重叠
const exact = intersectBySet(big, small);
console.log(`方案一 哈希集合：交集 ${exact.length} 个，零误判`);
const bloom = new BloomFilter(200000, 3); // 约 2.5 万字节装 5 万元素（故意压紧，让误判显现）
for (const url of big) bloom.add(url);
const candidates = small.filter((url) => bloom.mightContain(url));
const falsePositives = candidates.filter((url) => !big.includes(url));
const truth = new Set(exact);
const missed = small.filter((url) => !bloom.mightContain(url) && truth.has(url));
console.log(
`方案二 布隆过滤器：粗筛候选 ${candidates.length} 个，其中误判 ${falsePositives.length} 个，漏判 ${missed.length} 个`
);
console.log('误判需回源确认，漏判恒为 0——布隆过滤器只会把「不在」误报成「可能在」，绝不漏掉真正在的');
if (missed.length !== 0) throw new Error('布隆过滤器不允许漏判');
实测输出如下：
方案一 哈希集合：交集 120 个，零误判
方案二 布隆过滤器：粗筛候选 149 个，其中误判 29 个，漏判 0 个
误判需回源确认，漏判恒为 0——布隆过滤器只会把「不在」误报成「可能在」，绝不漏掉真正在的
2.5 万字节装下 5 万元素，120 个真交集一个不漏，代价是 29 个误判候选需要回源剔除。加大位数组或调整哈希个数，误判率还能继续往下压——内存与误判率的交换旋钮就在你手里。
易错点清单。
一，不看规模就答布隆过滤器——500 个元素的集合用哈希集合又准又简单。二，以为布隆过滤器给出精确答案——它只给「一定不在」和「可能在」，后者必须回源。三，哈希切分时两个集合用了不同切分规则，同一 URL 落进不同编号，交集直接算错。四，把大集合整个读进内存再处理——流式扫描才是海量数据的默认姿势。
回到面试现场，建议的答题节奏：先问规模与误判容忍度两个问题，再给哈希集合的基础解，然后主动把题目推向「两边都海量」并给出布隆过滤器与哈希切分两条路。训练语料去重、黑名单过滤、已见样本判定，用的都是这套决策路径。
你的业务里有用到布隆过滤器的场景吗？误判率是怎么定下来的？欢迎分享。
参考资料
- Node.js v22.x 官方 API 文档（文中代码运行环境为 Node.js 22.15.0，
Set、Uint8Array、Math.imul等行为以此为准） — https://nodejs.org/docs/latest-v22.x/api/