海量数据问题汇总

TopK问题：分治（哈希算法）+HashMap/Trie树+小顶堆或大顶堆。
（1）有一个1g大小的文件，里面的每一行都是一个词，词的大小不超过16字节，内存限制大小1M。返回频数最高的100词。

顺序读取文件每一行，利用哈希算法映射到2000个小文件。对每个小文件，使用trie树统计每个词的词频。使用小顶堆计算每个小文件的top100。使用归并，计算2000和top100的top100。
（2）海量日志数据，提取某日访问百度次数最多的ip。

IP是32位，使用哈希算法存到1000个小文件里面。使用HashMap统计频率，找到最大的频率。使用小顶堆计算1000个文件里面的最大频率对应的IP。

（3）海量数据分布在100台电脑，高效统计出TOP10。

虽然数据是分布的，但相同数据可能在不同电脑。因此有些总数属于TOP10的，可能在某台机器的分布只排TOP11。

因此应该使用哈希算法进行电脑重分配。然后使用HashMap统计每台电脑数据频率。然后使用最小堆在每台电脑求TOP10。

然后组合100台机器的TOP10，再使用最小堆求TOP10。

（4）一个有一万行单词的文本文件，要求统计出其中最频繁出现的前10个词。

一万行不算多，不用分割文件。然后使用Trie树统计词的频数。然后使用小顶堆求出TOP10。如果行数多的话就要增加一个步骤：使用哈希算法分割成小文件。再对每个小文件循环上面操作。

（5）一百万个数找出最大的100个。像刷题一样，可以使用快排、堆排。堆排的效率比较高。

重复问题：bitmap位图/布隆过滤器/哈希集合，每个元素对应一个位处理。

（1）给定a/b两个文件，各自存放50亿个URL地址，每个地址各占64个字节，内存限制是4G，找出两个文件公共的URL。

方案一：每个文件的大小大概是5G*64=320G，远远超过内存大小，考虑分而治之的方法。

可以先遍历文件a，使用哈希算法分散到1000个小文件，文件b使用同样的哈希算法分散到1000个小文件。只有相同编号的小文件才可能有相同的元素。接下来，读取a文件某编号的所有URL到Hash_map，然后遍历b中同样编号的所有URL，看是不是再那个Hash_map里面。如果存在，输出文件。

方案二：如果允许有一定错误率，可以使用布隆过滤器，使用位数组。

4G内存大概可以表示340亿bit。将其中一个文件的URL使用布隆过滤器映射为这340亿个位，然后挨个读取另外一个文件的URL。检查是不是在布隆过滤器。如果是，那么该URL应该是共同的（有一定错误率）。

（2）在2.5亿个整数中找出不重复的整数，内存不足以容纳这2.5亿个整数。

使用哈希算法分割成小文件。然后利用Hash_set，在小文件找出不重复的整数，再进行归并。

（3）一个文件包含40亿个整数，找出不包含的一个整数。

对于32位的整数，一共有2^32个，每个数对应一个bit，一共需要0.5GB的内存。遍历文件，将每个数对应的位置为1，最后查找位为0的拼凑起来就可以。

排序问题：外排序/bitmap位图。分割文件+文件内排序+文件间归并。

 （1）有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求按照query的频度进行排序。（不是像TOPK问题，只要得到TOPK的那种堆只要固定几个就好的解法，是要全部都排序）

首先进行分治，顺序读取每一行，使用哈希算法将它们全部都重新分配到十个文件。使用Hash_map记录（query和query_count），调入内存，利用快速排序/堆排序/归并排序等内部排序算法进行排序，输出到十个文件。再对十个文件进行归并排序。