海量数据面试题

思路

分而治之/hash映射 + hashmap统计 + 快速/归并/堆排序

这种方法是典型的“分而治之”的策略，是解决空间限制最常用的方法，即海量数据不能一
次性读入内存，而我们需要对海量数据进行的计数、排序等操作。基本思路如下图所示：先
借助哈希算法，计算每一条数据的 hash 值，按照 hash 值将海量数据分布存储到多个桶
中。根据 hash 函数的唯一性，相同的数据一定在同一个桶中。如此，我们再依次处理这些
小文件，最后做合并运算即可

问题1：海量日志数据，统计出某日访问百度次数最多的那个IP

解决方式：
IP地址最多有 2^32 = 4G 种取值情况，所以不能完全加载到内存中进行处理，采用 hash分解+ 分而治之 + 归并 方式：
（1）按照 IP 地址的 Hash(IP)%1024 值，把海量IP日志分别存储到1024个小文件中。这样，每个小文件最多包含4MB个IP地址；
（2）对于每一个小文件，构建一个IP为key，出现次数为value的Hash map，同时记录当前出现次数最多的那个IP地址
（3）然后再在这1024组最大的IP中，找出那个频率最大的IP

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

解决思想： hash分解+ 分而治之 + 归并

（1）顺序读文件中，对于每个词x，按照 hash(x)/(1024*4) 存到4096个小文件中。这样每个文件大概是250k左右。如果其中的有的文件超过了1M大小，还可以按照hash继续往下分，直到分解得到的小文件的大小都不超过1M。
（2）对每个小文件，可以采用 trie树/hashmap 统计每个文件中出现的词以及相应的频率，使用 100个节点的小顶堆取出出现频率最大的100个词，并把100个词及相应的频率存入文件。这样又得到了4096个文件。
（3）下一步就是把这4096个文件进行归并的过程了，内存里面用一个size=100的小顶堆，加载遍历每4096个文件的top100，排序规则是针对词频进行排序，如果某一个单词的词频小于堆顶元素的词频，直接看下一个单词，如果大于堆顶元素的词频，那个弹出堆顶元素，把该单词加载进去。

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

如果内存中想要存入所有的 url，共需要 50亿 * 64= 320G大小空间，所以采用 hash 分解+
分而治之 + 归并 的方式：

（1）f分别遍历文件a，b ， 以a为例 ： 对每个 url 根据某种hash规则，求取hash(url)/1024，然后根据所取得的值将 url 分别存储到1024个小文件（a0~a1023）中。这样每个小文件的大约为300M。
如果hash结果很集中使得某个文件ai过大，可以在对ai进行二级hash(ai0~ai1024)，这样 url 就 被hash到 1024 个不同级别的文件中。

（2）分别比较ab各自对应的文件，a0 VS b0，…… ，a1023 VS b1023，求每对小文件中相同的url时：
把其中一个小文件的 url 存储到 hashmap 中，然后遍历另一个小文件的每个url，看其是否
在刚才构建的 hashmap 中，如果是，那么就是共同的url，存到文件中。
（3）把1024个文件中的相同 url 合并起来

如果允许有一定的错误率，可以使用 Bloom filter，4G内存大概可以表示 340 亿bit，n = 50亿，如果按照出错率0.01算需要的大概是650亿个bit，现在可用的是340亿，相差并不多，这样可能会使出错率上升些，将其中一个文件中的 url 使用 Bloom filter 映射为这340 亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）

问题4：有10个文件，每个文件1G，每个文件的每一行存放的都是用户的 query，每个文件的query都可能重复。要求你按照query的频度排序。

解决方案1：hash分解+ 分而治之 +归并

（1）顺序读取10个文件 a0~a9，按照 hash(query)%10 的结果将 query 写入到另外10个文件（记为 b0~b9）中，这样新生成的文件每个的大小大约也1G

（2）找一台内存2G左右的机器，依次使用 hashmap(query, query_count) 来统计每个query 出现的次数。利用 快速/堆/归并排序 按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件c0~c9。

（3）对这10个文件 c0~c9 进行归并排序（内排序与外排序相结合）。每次取 c0~c9 文件的 m 个数据放到内存中，进行 10m 个数据的归并，即使把归并好的数据存到 d结果文件中。如果 ci 对应的m个数据全归并完了，再从 ci 余下的数据中取m个数据重新加载到内存中。直到所有ci文件的所有数据全部归并完成。

解决方案2：Trie树

如果query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性
就可以加入到内存了。在这种情况下，可以采用 trie树/hashmap 等直接来统计每个query出
现的次数，然后按出现次数做快速/堆/归并排序就可以了。

问题5：海量数据分布在100台电脑中，请高效统计出这批数据的TOP10

解决思想： 分而治之 + 归并
（1）在每台电脑上求出TOP10，采用包含10个元素的堆完成（TOP10小，用最大堆，
TOP10大，用最小堆）
（2）求出每台电脑上的TOP10后，把这100台电脑上的 TOP10 合并之后，共1000个数
据，在采用堆排序或者快排方式 求出 top10
（注意：该题的 TOP10 是取最大值或最小值，如果取频率TOP10，就应该先hash分解，
将相同的数据移动到同一台电脑中，再使用hashmap分别统计出现的频率）

问题6：在 2.5 亿个整数中找出不重复的整数，内存不足以容纳这2.5亿个整数

解决方案1：hash 分解+ 分而治之 + 归并

（1）2.5亿个 int 类型 hash 到1024个小文件中 a0~a1023，如果某个小文件大小还大于内存，进行多级hash
（2）将每个小文件读进内存，找出只出现一次的数据，输出到b0~b1023
（3）最后数据合并即可

解决方案2 ： 2-Bitmap
如果内存够1GB的话，采用 2-Bitmap 进行统计，共需内存 2^32 * 2bit = 1GB内存。
2- bitmap 中，每个数分配 2bit（00表示不存在，01表示出现一次，10表示多次，11无意义），
然后扫描这 2.5 亿个整数，查看Bitmap中相对应位，如果是00，则将其置为01；如果是01，将其置为10；如果是10，则保持不变。所描完成后，查看bitmap，把对应位是01的整数输出即可。
（如果是找出重复的数据，可以用1-bitmap。第一次bit位由0变1，第二次查询到相应bit位为1说明是重复数据，输出即可）