BigData

只用2GB内存在20亿个整数中找到出现次数最多的数

解法：哈希表？

1. key代表整数，value代表这个数出现的次数
2. 即使1个数出现了20亿次，也可以用32位整数（2^31 = 21,4748,3648，刚好超过21亿）表示出其出现的次数
3. 所以哈希表key需要占用4B（可以存放32位整数），value也需要4B（可以存放20亿的次数）
4. 当哈希表记录数为2亿（2*10^8）个时，需要1.6GB（1.6 * 2^30）内存。
5. 但如果20亿个数不同的数超过2亿种，内存就会不够，有风险。

1GB = 2^10MB = 2^20KB = 2^30B > 10亿B

最优解：哈希函数 + 哈希表
把一个大的集合通过哈希函数分配到多台机器中，或者分配到多个文件里（分批次处理），这种技巧是处理大数据面试题时最常用的技巧之一。但是到底分配到多少台机器，分配到多少文件，在解题时一定要确定下来。

把包含20亿个数的大文件用哈希函数分成16个小文件，同一种数会被哈希到同一个文件上，每个小文件的数一定不会大于2亿种，先取得每个小文件中出现次数最多的数，再将这16个小文件出现次数最多的数取第一名即可。

常用的hash函数是选一个数m取模（余数），这个数在课本中推荐m是素数，但是经常见到选择m=2^{n，因为对2}n求余数更快

找到100亿个URL中重复的URL以及搜索词汇的top K问题

• 内存要求？
• 计算时间要求？

哈希函数 -> 多台机器/小文件 -> 哈希表
哈希表遍历，每个小文件都有自己的小根堆（词频top100）
对不同机器top100再进行外排序或者小根堆，最终求出百亿数据top100

对于topK问题，除哈希函数分流和用哈希表做词频统计之外，还经常用堆结构和外排序进行处理