浅谈海量数据处理面试题

简介

海量数据处理问题是指基于海量数据的存储与操作。而所谓的海量数据，一般是指数据量过大无法都存放在内存中和数据量过大无法在较快的时间内完成操作。

对于空间存储的问题，一般的做法就是Hash映射，把一个大文件映射成很多的小文件。对于时间的问题，一般就是设计一些巧妙的算法配合一定的数据结构来解决。

具体问题

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

因为数据量太大，无法把所有的访问百度的IP都放到内存中，所以可以采用Hash映射的做法，把大文件映射到多个小文件中，然后每个小文件用HashMap统计。具体做法就是，对IP进行字符串Hash的时候%1000当作IP的HashCode，然后把HashCode相同的IP放在一个文件中，对于每个小文件就可以直接用HashMap统计。注意到这里HashCode相同的IP不一定相同，但HashCode不同的IP一定不同，而且一个IP对应一个HashCode，不会存在同一个IP映射到两个小文件中。

但是在这题中，这么进行Hash映射可能会出现问题。比如IP在映射到小文件的时候并不一定是均匀映射，可能有些文件还是比较大，无法放到内存里，这时候比较简单的做法是对那个文件换个Hash函数再进行Hash映射到更小的文件中。当然这个问题还有别的解决算法叫做一致性Hash算法。

---

2. 寻找热门查询，海量数据中统计最热门的K个查询。

如上题，如果数据量太大无法装到内存中，那么可以采用上面的Hash映射的做法，将大文件分成小文件，然后每个小文件用HashMap统计，在维护一个长度为K的优先队列去遍历这个每个小文件的HashMap得到最终的TopK。

---

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

还是如同上面的做法，Hash取模将大文件分成小文件，然后每个文件维护一个HashMap统计频率，最终维护一个优先队列，得到频数最高的词。

---

4. 海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。

有两种做法。第一种就是维护一个HashMap，遍历这100个电脑，然后用一个长度为10的优先队列去遍历HashMap得到TOP10;还一种做法是先对数据进行Hash映射，将数据重新映射到这100台电脑上，然后在进行统计。

---

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

有三种种做法。第一种就如同前面对query重新Hash映射到这10个文件中，然后每个文件进行排序，最后用归并排序将10个序列合并;第二种做法是query的种类往往较少，直接用HashMap遍历所有的文件就行;第三种做法如做法一将文件重新Hash映射后用分布式文件系统来处理，再用归并排序合并。

---

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

做法还是如同之前，把大文件用Hash映射成小文件，然后对应的小文件用HashMap判断是否有相同的url。

---

7. 2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。整数范围是Int范围。

可以将Int类型划分区间，把数放置到满足条件的区间，然后对每个区间用BitMap进行统计。

---

8. 5亿个int找它们的中位数。

对Int进行分段，得到每段的个数，然后确定区间，和中位数是区间的第几大，然后很容易能得出结果。

---

9. 给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

采用Bitmap的做法。TODO！