图 1：内存装不下之后，方法沿「精确到近似」的光谱排开。
这是一篇知识延伸文章：此前一篇真题解析讲了内存装得下时的 Top-K——扫一遍数据、维护一个 K 大小的小顶堆，O(N log K) 收工。本文换主轴：当数据量远超内存，堆解法的前提不复存在，此时有哪些方法、各自的精度代价是什么？堆解法的细节不再重复。
问题先变形：瓶颈从 CPU 变成 IO 和内存。
数据装不进内存，意味着不能假设「每个元素想读几次读几次」。新问题变成两道选择题：结果必须精确吗？数据能扫几遍？两个答案组合起来，唯一确定该用哪类方法——这也是面试里被追问时的破题顺序。
精确派第一招：分治加小顶堆。
思路是把「装不下」切成「装得下」：按哈希把数据分片到若干个小文件，同一关键词必然落在同一片（哈希分片保证了这一点，这是正确性的关键）；逐片读入内存，用单机堆解法算出每片的 Top-K；最后把各片的候选归并，全局 Top-K 出炉。精度 100%，代价是多趟磁盘 IO 和一次归并。工程上这个模式就是 MapReduce 里 map 端预聚合的思想，日志热词统计类任务天天在用。
精确派第二招：外部归并排序。
如果连「每片装得下」都不成立，或者下游本来就要全量有序的结果，就上外排序：分段读入、段内排序、写回磁盘，再多路归并成全局有序，取前 K 即可。精度同样 100%，但 IO 代价是谱系里最重的——全量数据至少读写两趟。只有当「排序结果还有其他用途」时它才划算，单纯为 Top-K 上外排序是拿大炮打蚊子。
近似派：用一点点精度换数量级的代价。
很多场景根本不需要精确答案——实时监控大屏、热词趋势，第 10 名和第 11 名交换一下无伤大雅。这时近似算法的性价比碾压精确派。
代表是 Count-Min Sketch：一张 d 行 w 列的计数表，每个词来了用 d 个哈希函数各戳一格加一；查询时取该词 d 个格子的最小值作为频次估计。因为哈希碰撞只会把别的词的计数撞进来、永远不会漏掉自己的，所以估计只高估、不低估，且误差有概率界。内存是固定的几 KB 到几 MB，与数据量无关，一趟流式扫完。要求更松的场景连计数都省了——直接采样，在样本上跑小顶堆，误差随采样率波动。
实测 Count-Min 的误差脾气。
用 Node.js 22.15.0 模拟 10 万条流、5000 个不同词的 Zipf 型分布（node topk.js），sketch 只用 5×1024 个计数器：
class CountMin {
constructor(w, d) {
this.w = w; this.d = d;
this.t = Array.from({ length: d }, () => new Array(w).fill(0));
this.salts = Array.from({ length: d }, (_, i) => i * 2654435761);
}
#hash(x, i) {
let h = this.salts[i];
for (const ch of x) h = Math.imul(h ^ ch.charCodeAt(0), 16777619) >>> 0;
return h % this.w;
}
add(x) { for (let i = 0; i < this.d; i++) this.t[i][this.#hash(x, i)]++; }
est(x) { return Math.min(...Array.from({ length: this.d }, (_, i) => this.t[i][this.#hash(x, i)])); }
}
对 10 万条流逐条 add，与精确计数表对照，输出摘要：
w0: 真实 6468 估计 6495 偏高 +27
w1: 真实 1357 估计 1385 偏高 +28
w9: 真实 540 估计 596 偏高 +56
sketch Top10 命中真实 Top10: 9/10，最大偏差 +56，低估次数 0
sketch 内存 ≈ 20KB，精确计数表 4003 个键
三个观察全部兑现：所有估计都偏高、没有一例低估；最热的词偏差相对值极小（6468 只差 27）；Top10 命中 9 个。20 KB 内存换掉一张几千键还会无限增长的哈希表，这就是近似派的账本。
图 2：两个问题的答案组合，唯一落到一种方法上。
决策口诀与经验边界。
先问能不能错，再问能扫几遍：必须精确且能分片归并，选分治加堆；必须精确且要全量有序，选外排序；允许近似，流式场景选 Count-Min，一次性粗看选采样。经验上的分工也稳定：涉及结算、榜单、对外公示的数字走精确派，宁可多跑一趟；实时监控、趋势观察、粗粒度告警走近似派，省下来的机器和时间远比那一点偏差值钱。
你的工作流里 Top-K 出现在哪一环？有没有从精确方案迁到近似方案的经历，迁移的触发点是什么？欢迎分享。