如何从大量数据中心找出高频词

题目

有1GB大小的文件，文件里每一行是一个词，每个词的大小不超过16个字节，内存大小限制是1MB,要求返回词频最高的100个词

思路

由于文件大小1GB，而内存大小1MB,因此不可能一次把所有的词读到内存中进行处理，需要采用分之的思想，把一个大文件分解成多个小文件，从而保证每个文件大小都小于1MB，进而可以直接读取到内存进行处理。具体思路：
1）遍历文件，对遍历到的每一个词，执行hash操作：hash(x)%2000,将结果为i的词放到文件ai中。通过这个分解步骤，可以使每个文件大小约400kb,如果这个操作后某个文件大小超过了1MB,那么就采用相同的方法对这个文件继续分解。
2）统计出每个文件中频率最高的100个词。最简单的方法是使用HashMap来实现：遍历文件中的所有词，对于遍历到的词，如果hashmap中不存在，那么将这个词放入haspmap中（键为这个词，值为1），如已经存在，那么将这个词对应的值加1。可以找到每个文件中频率最高的100个词。
3）对第二步找到的每个文件出现频率最高的100个词，可以通过维护一个小顶堆来找出所有文件中出现频率最高的100个词。具体做法：遍历第一个文件，把第一个文件中出现频率最高的100个词构成一个小顶堆，继续遍历，如果遍历到的词频率大于顶堆上出现的频率，则用遍历到的词替换顶堆上的词，然后调整这个小顶堆。遍历完所有文件，小顶堆中的词即为出现频率最高的100个词。