最多出现次数
题目描述：有一个包含20个亿全是32位整数（4byte）的大文件，在其中找到出现次数最多的数。
分析：
使用hashmap，每一个元素维护一个出现次数：比如(“1”,1)，(“2”,2),(“3”,1),key:表示某个元素，value:表示某个元素出现的次数，对文件的每一个元素进行扫描，使用map.contains(“key”)判断是否存在，如果存在就map.get(“key”),然后value的值加1，再map.put(key,value),如果不存在直接map.put(key,value);
上述方法看似可行，但是特备耗内存，假设元素key占4个字节，value占4个字节，那么就是一共就是160亿个字节，也就是16G，一共需要消耗16个G的内存，这是肯定不合适的。一次可以采用hash的方法将文件拆分成16个文件，每个文件大约就是一个G，然后对每一个文件进行hashMap操作，大约需要消耗2个G，看起来是可行的。在每一个文件求出Top1，一共就有16个Top1，然后在16个Top1中求出最后的那个Top1
原理图：
未出现过的数
题目描述：32位无符号整数的范围是：0~4294967295(42亿)，现在正好有一个40亿个无符号数整数的文件，所以在整个范围中必然有没有出现过的数。最多可以使用1G的内存，怎么找到所有没有出现过的数。
分析：
开辟一个位图空间，长度为2的32次方减1，每一个位置上的值为0或1，代表该对应位置的值是否出现过，最后只需要遍历这个位图空间，值为0的即是没有出现过的数据，该空间的大小为：2的32次方bit，大约500M。
原理图：
TopK
题目描述：找到100亿个URL中重复的URL，以及搜索词汇的Topk问题。
分析
假设每一个Url占64个字节，那么大约就是64G的内存，可以根据hash分成64个小文件，每一个文件中统计词频，维护大小为100 的小顶堆，最后生成的n个小顶堆，然后再外部使用排序获取TopK
京公网安备 11010502036488号