海量数据处理

海量数据相关的面试题已经是个老生常谈的话题了。相比于小量数据，海量数据存在两点限制：内存装不下或者读取太慢。

关于海量数据的面试题一般有一下几种：

对于海量数据的处理方式也不外乎以下几种：

这是一道关于统计次数的题，一般使用hashmap或者bitmap就可以解决，使用hashmap时要注意空间是否满足要求。

这个问题有两个点：海量数据，次数最多。

先看第二个点。

把这个问题再提取一下：就是让你在海量数据里去找出现次数最多的那个数。

再提取一下：就是统计次数。问题就很清楚了，使用hash就可以解决。

然后再看第一个点。

海量数据，意味着数据太多，你的hash map内存可能放不下。怎么办？拆分！将这个海量数据拆分成若干个小文件，然后在每个小文件里统计出现次数最多的，最后综合所有的小文件中次数最多的ip找到王中王。是不是有点像归并排序？

那么怎么拆分？假设要拆分成N个文件，可以这么做：hash(IP)%N

这个问题是找出现次数最多的那个数。那么怎么找出现了一次的？或者，给定一个数，怎么判断它有没有在海量数据中出现过？下面我们一一来看。

2.5亿整数中找出不重复的整数。

找出不重复的数，其实也是统计次数，统计只出现一次的那些数，所以上述分割+hash的算法依然可用，不过这里我们再给出另一种更简单的方法：基于bitmap的方法。

对于每个数，我们使用2bit来表示，00表示出现0次，01表示出现1次，10表示出现多次。

2.5亿个整数，需要多少bit才能表示完呢，假设这些整数都是int类型的，那么最多也就只有$2^{32}$种数，已经能表示20多亿了，完全够应付这里的2.5亿，再考虑到每个数用2bit来表示出现次数，一共需要$2^{32}*2$bit=1GB.就可以表示这2.5亿个数的出现次数了。

需要注意的是，上面算出来的1G其实算是大的了，因为真正的并没有$2^{32}$个数，所以没必要开辟这么大空间，现在的开源实现如谷歌的EWAHCompressedBitmap已经对bitmap的内存分配做了很多优化，对于很稀疏的海量数据，那些稀疏数据之间的空缺是没必要申请空间的。