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

（1）参见我的其他大数据面试题博文。此处1G文件远远大于1M内存，分治法，先hash映射把大文件分成很多个小文件，具体操作如下：读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件(记为f0,f1,...,f4999)中，这样每个文件大概是200k左右（每个相同的词一定被映射到了同一文件中）

（2）对于每个文件fi，都用hash_map做词和出现频率的统计，取出频率大的前100个词（怎么取？topK问题，建立一个100个节点的最小堆），把这100个词和出现频率再单独存入一个文件

（3）根据上述处理，我们又得到了5000个文件，归并文件取出top100（Top K 问题，比较最大的前100个频数）

借助堆这个数据结构，找出Top K，时间复杂度为N‘logK。即借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比。所以，我们最终的时间复杂度是：O（N） + N' * O（logK），（N为1000万，N’为300万）。

要解决该问题首先要进行分类，把重复出现的IP都放到一个文件里面，一共分成100份，这可以通过把IP对100取模得到，具体方法如把IP中的点转化为整型long型变量，这样取模为0,1,2...99的IP都分到一个文件了，但是要考虑一个问题，如果某个文件的IP取余之后还是特别多无法放入内存中，可以再对这一类IP做一次取模，直到每个小文件足够载入内存为止。这个分类很关键，如果是随便分成100份，相同的IP被分在了不同的文件中，接下来再对每个文件统计次数并做归并，这个思路就没有意义了，起不到“大而化小，各个击破，缩小规模，逐个解决”的效果了。

接下来把每个小文件载入内存，建立哈希表将每个IP作为关键字映射为出现次数，这个哈希表建好之后也得先写入硬盘，因为内存就那么多，一共要统计100个文件。

在统计完100个文件之后，我再建立一个小顶堆，大小为100，把建立好并存在硬盘哈希表载入内存，逐个对出现次数排序，挑出出现次数最多的100个，由于次数直接和IP是对应的，找出最多的次数也就找出了相应的IP。  

所以海量数据面前要多采用分治算法，化整为零 各个击破！