海量数据面试题总结(1)-Hash映射+Hash统计+归并排序

本系列文章对海量数据面试题进行了归类和总结，给出海量数据处理问题的通用解决思路，后面附有例题，希望大家能够举一反三。

模式一：Hash映射+Hash统计+堆/归并排序

一、解决思路

1. hash映射(分而治之)

首先考虑是否需要将大文件分成小文件，针对数据太大，内存受限，只能是将大文件化成小文件(取模映射)；

2. hash统计

当大文件转化了小文件，那么我们便可以采用常规的Hashmap(ip，value)来进行频率统计；

3. 堆/归并排序

统计完了之后，便进行排序。

注意：1GB = (2^10)^3 = 2^30 = 1073741824B ~= 11亿B

二、经典例题

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

（1）分而治之/hash映射：顺序读文件中对于每个词x取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,…x4999）中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。

（2）hash统计：对每个小文件，采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。

（3）堆/归并排序：取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这样又得到了5000个文件。最后就是把这5000个文件进行归并（类似于归并排序）的过程了。

2. 海量日志数据，提取出某日访问百度次数最多的IP。

（1）由于IP是32位的，最多有个2^32个IP，约4GB；

（2）可以采用映射的方法，比如模1000，把整个日志大文件映射为1000个小文件；

（3）再找出每个小文中出现频率最大的IP（可以采用Hash_map进行频率统计，然后再找出频率最大的几个）及相应的频率。

（4）然后再在这1000个最大的IP中，找出那个频率最大的IP。

3. 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个检索记录，但除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询热度越高，请统计最热门的10个查询串，要求使用的内存不能超过1G。

事实上只有300万的Query，每个Query255B，文件最大是7.65亿B < 1GB。因此我们可以考虑把他们都放进内存中去，而现在只是需要一个合适的数据结构，在这里，Hash Table绝对是我们优先的选择。所以我们摒弃分而治之/hash映射的方法，直接上hash统计，然后排序。

4. 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

可以估计每个文件的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

（1）将a、b均按照相同的hash方法分散到1000个小文件中：a1-a1000、b1-b1000；

（2）a1和b1比较，去重相同的url；

（3）依次类推，将所有相同url合并；