由于面试中经常遇到海量数据的相关问题，比如排序，比如选出topk，比如找出重复的元素等等

海量数据排序

假如有１TB的数据，内存只有32GB

第一步是将１TB的数据分成40组，每组25GB；然后分别读取40组数据，进行内部排序（可以用快排或者归并），然后写回磁盘；接着从这40组数据中分别读取25GB/40=0.625GB，放在40个缓冲区里；最后进行多路归并，可以每次将归并结果写满4GB就写回磁盘；并且一旦有缓冲区已经读完了，就从该缓冲区对应的组里读入新的0.625GB；

海量数据中选出最大的前k个数

一种方法：通过哈希将海量数据分成n个小文件（如果不够小，继续细分，直到文件大小小于内存）。然后为每个小文件建立一个小顶堆，这样就能选出n个topK，进行归并，选出最后的topK；另外的方法：是直接建立一个k大小的大顶堆，然后依次读入数据，与堆顶元素比较，调整堆。当所有数据读完之后，得到最终的堆就是topK个数；

海量数据中选出频率最高的几个元素

与上面相同，先是将数据分成多个小文件，在每个小文件内利用hash_map去统计每个词的频率，选出topK频率的元素。最后再进程归并或者大顶堆统计；

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

首先是分别对这两个大文件进行哈希计算（用同一个哈希函数），得到多个小文件，这样相同的url就会被分到对应的小文件中；然后从a得到的小文件中找出url，存到hash_set中，然后遍历另外的对应小文件url，如果存在则输出到文件中

在海量数据中找出不重复的数

采用2bit法，00表示不存在该数字，01表示数字只出现一次，10表示数字重复多次。扫描完之后，输出对应为01的数字即可

判断一个数是否在海量数据中

一种方法是采用位图法，1个bit代表一个数，扫描一遍海量数据，得到扫描结果。之后进行判断；另外的方法则是，把海量数据按照每个bit为0或者1分成两类，然后又按照次高位分成2类。。一次下去。这样，每次判断数是否存在于海量数据中花费时间为logN

参考

http://blog.csdn.net/FX677588/article/details/72471357 https://kb.cnblogs.com/page/95701/