真实面经题目 · 原创解析
如何在大文件中找出出现频率最高的前100个内容？
大文件中找出现频率最高的前 100 个内容，本质是大数据 TopK 频次统计：先统计每个内容出现次数，再从频次结果中选 Top100。答案要根据内存是否能容纳全部去重内容，选择 HashMap 计数、小根堆、哈希切分、外部排序、分布式聚合或流式近似算法。
出现于：阿里巴巴 · 后端开发
01
60 秒回答模板
我会先确认文件大小、内存限制、内容粒度、是否要求精确、是否单机处理。如果内存能放下所有不同内容，最直接做法是顺序读取文件，用 HashMap 统计每个内容的出现次数，然后用容量为 100 的小根堆维护当前最高频的 100 个内容。遍历 HashMap 时堆未满就插入，堆满后只有当前频率大于堆顶时才替换，复杂度约为 O(N + M log 100)，N 是总记录数，M 是不同内容数。如果内存放不下，精确方案是哈希切分：按内容 hash 把原始数据分到多个小文件，保证相同内容一定落到同一个分片；逐个分片在内存中统计并得到分片 Top100，最后合并所有分片候选，再用小根堆得到全局 Top100。若切分不方便，也可以外部排序，让相同内容连续出现后顺序扫描计数。规模更大时可用 MapReduce，Map 输出内容和 1，Combiner 本地聚合，Reduce 得到全局频次，最终合并各 Reduce 的 Top100。若允许近似，流式场景可以用 Space-Saving、Misra-Gries 或 Count-Min Sketch，但必须说明误差边界。
考点 拆成计数和 TopK
主线 内存足够的单机方案
易错点 直接把整个文件读进内存排序，没有考虑大文件内存限制。
02
深入解析
拆成计数和 TopK
这道题应先拆成两个阶段：第一阶段统计每个内容出现了多少次，第二阶段从所有频次里选出最高的 100 个。很多人会直接说排序，但题目只要前 100 个，不需要完整排序所有内容。HashMap 解决计数，小根堆解决固定大小 TopK，是最基础的精确思路。
内存足够的单机方案
如果不同内容数量能放进内存，顺序读文件并用 HashMap 计数即可。读完后遍历 HashMap，用容量 100 的小根堆保存候选答案。堆顶是当前 Top100 中频率最低的元素，新候选只有频率超过堆顶才进入。这种方案简单、精确、易实现，适合去重内容规模可控的场景。
内存不足的哈希切分
当不同内容太多，HashMap 放不下时，可以先按 hash(content) 取模写入多个分片文件。相同内容 hash 相同，因此一定进入同一个分片。只要分片数量足够，每个分片就能单独放入内存统计。之后每个分片产生 Top100，最终合并候选得到全局 Top100。
分片 Top100 为什么不漏
按内容哈希切分后，一个内容只存在于一个分片中，它在分片内的频次就是全局频次。全局 Top100 的任意内容如果属于某个分片，却排不进该分片 Top100，就说明该分片至少有 100 个内容频次不低于它，那么它也不可能进入全局 Top100。这个结论依赖相同内容不被拆散。
外部排序方案
外部排序是另一种精确方案。先把大文件拆成能放入内存的小块，对每块按内容排序，再多路归并成整体有序结果。相同内容连续出现后，顺序扫描即可统计频次，再用小根堆维护 Top100。它通用但磁盘 I/O 和归并成本更高，适合已有排序基础设施或哈希分布不易控制的场景。
分布式和近似方案
如果单机处理能力不足，可以用 MapReduce 或类似分布式聚合：Map 读取数据，Combiner 本地合并，Shuffle 保证相同内容进入同一 Reduce，Reduce 汇总频次并输出局部 Top100，最后合并。若数据是实时流且允许误差，可以用 Space-Saving、Misra-Gries、Count-Min Sketch 等固定内存近似算法。
工程细节
工程实现要考虑分片数量估算、文件句柄、缓冲区、临时文件清理、数据倾斜、超长内容、编码和分隔符、同频排序规则、计数溢出、失败重试和结果可复现。热点内容可能导致某个分片或 Reduce 压力过大，需要二次切分、本地聚合或热点单独处理。
03
易错点
- 直接把整个文件读进内存排序，没有考虑大文件内存限制。
- 只说使用 HashMap，没有说明不同内容数量超过内存时怎么办。
- 使用全量排序找前 100，却没有解释为什么不使用小根堆降低成本。
- 按行数或文件大小切分后分别取 Top100，没有保证相同内容落在同一分片。
- 把每个分片的 Top100 直接拼接当答案，没有做最终合并。
- 混淆精确算法和近似算法，在要求精确结果时直接使用 Count-Min Sketch。
04
面试官追问
如果文件 100GB，内存只有 1GB，怎么做？
优先用哈希切分。顺序读取文件，按内容 hash 写入足够多的分片，让单个分片能在 1GB 内完成 HashMap 统计。每个分片取 Top100 后，再合并候选得到最终 Top100。
为什么不用大根堆？
这里要维护固定大小的 Top100，需要快速淘汰当前候选中最小的频次。小根堆堆顶正好是最弱候选，大根堆不方便判断和淘汰候选集合里的最小值。
按文件大小平均切分可以吗？
不能直接这样做。按大小或行数切分会让相同内容分散到多个分片，各分片只能得到局部频次。除非后续再按内容汇总频次，否则结果会错误。
外部排序和哈希切分怎么选？
只为统计高频内容时，哈希切分通常更直接，避免全量排序。若已有排序链路、哈希分布不可控，或希望通过顺序扫描聚合，外部排序也可行，但 I/O 成本更高。
如果数据是实时流，不能回放文件怎么办？
要求精确时需要维护持久化计数状态；允许近似时可以用 Space-Saving、Misra-Gries 或 Count-Min Sketch。实时流方案必须说明窗口策略、误差边界和状态恢复。
