含100万整数的大文件求众数：内存受限下的高效方案探讨

你提到的外部排序后逐块统计的思路是可行的，但确实存在更高效的实现方式，根据你的场景需求（是否允许近似、是否可以并行处理），可以参考以下几种方案：

1. 哈希分桶+分布式统计（最通用的高效方案） #

这个思路本质是MapReduce的核心思想，比外部排序的O(n log n)时间复杂度更优，能达到O(n)的线性时间：

• 分桶阶段：遍历整个数据集，用一个均匀的哈希函数把每个整数映射到对应的小文件（桶）里。关键要保证相同的整数一定会落到同一个桶，同时尽量让每个桶的大小都能被加载进主内存。
• 本地统计：对每个桶单独加载到内存中，用普通的HashMap统计每个数的出现频率，记录下该桶内频率最高的数及其计数。
• 全局合并：把所有桶的候选众数收集起来，对比它们的全局总频率，最终得到整个数据集的众数。
  这个方法的优势在于可以并行处理所有桶（比如用多线程或者分布式集群），磁盘IO开销也比外部排序小——排序需要多次归并读写，而分桶只需要一次全量读+分桶写，再加上一次桶的读操作。

2. 近似众数算法（内存极度受限场景） #

如果你的场景允许返回近似结果，或者能保证真实众数的出现频率超过某个阈值（比如>n/k，n是总数据量，k是你设定的常数），Misra-Gries算法是绝佳选择，它只需要常数级的内存：

• 核心操作：维护一个大小为k的哈希表，遍历每个整数时：
  • 若该数已在哈希表中，对应计数+1；
  • 若哈希表还有空位，将该数加入并设计数为1；
  • 若哈希表已满，把所有表内元素的计数减1，移除计数为0的元素。
• 遍历完成后，真实众数一定在哈希表的候选元素中（当满足频率>n/k时）。之后只需要再遍历一次数据集，统计这些候选元素的真实频率即可。
  这个方法只需要两次遍历数据集，完全不需要分桶或排序，内存占用极低，适合内存极其紧张的场景。

3. 和外部排序法的效率对比 #

外部排序的时间复杂度是O(n log n)，而上面两种方法都是O(n)线性时间，在数据量极大时差距会非常明显。另外，外部排序的磁盘IO次数更多（归并阶段的多轮读写），而哈希分桶的IO是线性的，近似算法甚至只需要两次全量读，IO开销小很多。

内容的提问来源于stack exchange，提问作者user3508953