文章目录

• • 题目
  • 解答
  • 总结

题目

如何在 20 亿个无符号整数中找到出现次数最多的那个数，在只提供 1 G 内存的条件下

解答

找到出现次数最多的数，通常的思维就是使用 HashMap 来统计这 20 亿个无符号整数中每个数出现的次数

已知只有 20 亿个数，那么我们使用 int 类型就足以来统计这些数了，那么一条 Hash 表记录 key 需要 4 个字节，value 需要 4 个字节，一条记录至少 8 个字节。最坏情况下，这 20 亿个数都是不同的，那么就需要 160 亿字节，即 16 G，在题目提供的 1 G内存条件下，显然是没有办法解决问题的

我们知道 Hash 函数，调完之后的结果分布具有离散性和均匀性这样的性质，并且同一个值调用同一个 Hash 函数，最后得到的结果一定是一样的

可以将这 20 亿个数分别进行调用 Hash 函数，然后将产生的结果 %100，最后得到的值的范围就是 0 ~ 99，将结果为 i 的数存放到文件 A_i 中。遍历就结束后，我们就可以得到 100 个小文件。因为调用过 Hash 函数后，结果是比较均匀的，所以每个小文件的数通过 HashMap 统计词频所占内存空间大小最多 0.16 G，妥妥的比 1 G小，如果不幸仍有超过 1 G，就采用相同的方式将 20 亿个数分解到更多的小文件中

根据 Hash 函数的性质，此时小文件中含有不同的数字种类是差不多的，相同的数一定被放在了同一个文件夹中

之后的事就非常好办了，我们只需要将小文件里的数通过 HashMap 进行频率统计，每个文件中都会决出一个出现次数最多的数字，一个文件统计完后，就可以释放内存，最后 100 个小文件产出的结果中在做对比，产出最后的结果，即出现次数最多的数

试问：如果我们想要从这 20 亿个数中找到频率最高的 100 个数，还是 1 G内存怎么找？

前面的将每个数进行调用 Hash 函数，%100，分成 100 个小文件的操作是一样的，只不过每个小文件中频率统计的操作中，我们需要依次遍历每个小文件，构建一个大小为 100 的小根堆（小根堆的特点就是当前节点比它的孩子小）。

如果遍历到的数出现的次数大于堆顶数出现的次数，那么就让新的数顶替堆顶的数，重新调整为小根堆，自然，遍历结束后，小根堆上的数就是出现频率最高的 100 个数

总结

• 分而治之，将大数据进行哈希取余，从而分成小文件
• 使用 HashMap 频率统计
• 将数据整合比对