图 1：本文封面，点明题目与「哈希切分加小顶堆」的组合拳。
先说明属性：这是一篇历史题目复盘，题目出自本地历史面试资料（见文末来源说明），与任何公司的当前招聘无关。海量数据题的内核都一样：内存装不下，就不能把问题整体搬进内存，只能想办法把它切成装得下的若干份——难点从不在「切」，而在「切完之后结果还能不能正确合并」。
想象面试现场，面试官说：「有 10 个 1G 的文件，每行一个搜索词，内存只有几百 MB。按词频从高到低排序，输出 Top-N，怎么做？」
第一步，审题：瓶颈在哪。
10G 数据、几百 MB 内存，直接全量计数不可能。但注意一个松动之处：我们不需要同时处理全部数据，只需要保证「同一个词的所有出现被统计在一起」。如果能把数据切成每份都装得下的小块，且同词不拆散，问题就退化成逐块统计再合并。
第二步，核心招式：哈希切分。
逐行读每个文件，对每行的词计算 hash(词) mod 50，把词追加写进对应编号的小文件——10G 切成 50 份，每份约 200MB，可以装入内存。这一步的关键不变式是：同一个词哈希值固定，它的所有出现必然落进同一个小文件，一次都不会漏、也不会重。正确性就靠这一条不变式撑着，它成立，后面所有步骤才合法。
第三步，逐桶统计加小顶堆取 Top-K。
每个小文件装进内存，用哈希表做词频计数；然后对计数结果过一遍容量为 K 的小顶堆——比堆顶大就替换堆顶再下滤。堆的容量恒为 K，每个桶只花 O(词数 log K) 时间、O(K) 额外内存，就筛出该桶的局部 Top-K。要 Top-N 全局榜时，把 50 份局部 Top-K 归并再排序即可。为什么局部 Top-K 可以代表全局？一个词若进得了全局 Top-K，它在自己桶里的计数等于它的全局计数，必然也在桶内前 K——反证即得，这个推导面试时要主动讲。
图 2：五步流水线，以及它与 MapReduce 的对应关系。
第四步，跑一遍可运行的缩微版。
下面这份代码用小样数据走完全流程，并与直接全量统计交叉复核，用 Node.js 22.15.0 直接运行（node word-freq.js）即可：
'use strict';
function hashWord(word) {
let h = 0;
for (const ch of word) h = (h * 31 + ch.charCodeAt(0)) >>> 0;
return h;
}
// 容量 K 的小顶堆：比堆顶大就替换，始终保存「目前见过的前 K 大」
class MinHeap {
constructor(k) {
this.k = k;
this.a = []; // 元素为 [词, 频次]
}
push(item) {
const a = this.a;
if (a.length < this.k) {
a.push(item);
for (let i = a.length - 1; i > 0 && a[i][1] < a[(i - 1) >> 1][1]; i = (i - 1) >> 1) {
[a[i], a[(i - 1) >> 1]] = [a[(i - 1) >> 1], a[i]];
}
} else if (item[1] > a[0][1]) {
a[0] = item;
for (let i = 0; ; ) {
let s = i;
const l = 2 * i + 1;
const r = 2 * i + 2;
if (l < a.length && a[l][1] < a[s][1]) s = l;
if (r < a.length && a[r][1] < a[s][1]) s = r;
if (s === i) break;
[a[i], a[s]] = [a[s], a[i]];
i = s;
}
}
}
entries() {
return [...this.a];
}
}
// —— 造数据：模拟 10 个 1G 文件的小样（真实场景逐行流式读取，这里用内存数组代替）——
const corpus = [
['apple', 30], ['banana', 22], ['cherry', 15], ['date', 12],
['elderberry', 9], ['fig', 7], ['grape', 5], ['honeydew', 3],
];
const files = Array.from({ length: 3 }, () => []);
for (const [w, c] of corpus) for (let i = 0; i < c; i++) files[i % 3].push(w);
// 第一步：哈希切分——同一个词的所有出现必然落进同一编号的小文件
const BUCKET_COUNT = 8;
const buckets = Array.from({ length: BUCKET_COUNT }, () => []);
for (const file of files) for (const w of file) buckets[hashWord(w) % BUCKET_COUNT].push(w);
const appleBuckets = new Set();
for (const file of files) for (const w of file) if (w === 'apple') appleBuckets.add(hashWord(w) % BUCKET_COUNT);
console.log(`apple 散布在 3 个文件中，切分后落进的桶号 -> ${[...appleBuckets]}（必然只有 1 个）`);
// 第二步：每个小文件装入内存，用哈希表计数；第三步：过容量 K 的小顶堆取局部 Top-K
const K = 3;
const partials = buckets.map((bucket) => {
const counts = new Map();
for (const w of bucket) counts.set(w, (counts.get(w) ?? 0) + 1);
const heap = new MinHeap(K);
for (const entry of counts) heap.push(entry);
return heap.entries();
});
// 第四步：归并 8 份局部 Top-K，再按频次降序排列得全局榜
const merged = partials.flat().sort((x, y) => y[1] - x[1]).slice(0, K);
console.log(`全局 Top-3 -> ${merged.map(([w, c]) => `${w}(${c})`).join(', ')}`);
// 正确性复核：小样数据直接全量计数对比
const direct = new Map();
for (const f of files) for (const w of f) direct.set(w, (direct.get(w) ?? 0) + 1);
const expected = [...direct.entries()].sort((x, y) => y[1] - x[1]).slice(0, K);
console.log(`直接全量统计复核 -> ${expected.map(([w, c]) => `${w}(${c})`).join(', ')}`);
if (JSON.stringify(merged) !== JSON.stringify(expected)) throw new Error('分治结果与全量统计不一致');
实测输出如下：
apple 散布在 3 个文件中，切分后落进的桶号 -> 2（必然只有 1 个）
全局 Top-3 -> apple(30), banana(22), cherry(15)
直接全量统计复核 -> apple(30), banana(22), cherry(15)
三行输出分别验证了「同词同桶」的不变式、分治流水线结果、以及与全量统计的一致性。
易错点清单。
一，按文件平均分而不是按词哈希切分——同一个词被拆进不同桶，计数残缺，合并出来的榜是错的，这是最致命的错误。二，桶数拍脑袋——桶的大小要按内存反推，10G 配几百 MB 内存就切 50 到 100 份。三，用大顶堆或全排序取 Top-K——容量 K 的小顶堆才是 O(n log K) 的关键。四，讲不出局部 Top-K 能代表全局的反证，方案停在「大概是对的」。
回到面试现场，建议的答题节奏：先点破瓶颈是内存不是计算，再给哈希切分加不变式，然后逐桶计数加小顶堆，最后归并全局榜并补一句「这就是 MapReduce 的单机版」——切分对应 Map 侧分片、单文件统计对应 Reduce、归并对应最终聚合。
语料词频统计是训练数据清洗的第一步。如果题目追问「某个词恰好在两个桶边界上哈希倾斜怎么办」，你会怎么应对？欢迎写出你的思路。
参考资料
- Node.js v22.x 官方 API 文档（文中代码运行环境为 Node.js 22.15.0，
Map、Set、数组排序等行为以此为准） — https://nodejs.org/docs/latest-v22.x/api/