这类题目，首先需要确定可用内存的大小，然后确定数据的大小，由这两个参数就可以确定hash函数应该怎么设置才能保证每个文件的大小都不超过内存的大小，从而可以保证每个小的文件都能被一次性加载到内存中。

1. 如何从大量的url中找到相同的url？

题目描述：给定a、b两个文件，各存放50亿个url，每个url各占64B，内存限制是4GB，请找出a、b两个文件共同的url。

分析：50亿个url，50亿*64 = 5GB*64=320GB，内存大小4GB，因此不可能一次性把所有的url都加载到内存中处理。需要用分治法把一个文件中的url按照某一特征分成多个文件，使得每个文件的内容都小于4GB，这样就可以把这个文件一次性读到内存中进行处理了。

主要思路：

（1）遍历文件a，对遍历到的url求hash(url)%500，根据计算结果把遍历到的url分别存储到a0,a1,...,a499(计算结果为i的url存储到文件ai中)，这样每个文件的大小约为600MB。当某一个文件中url的大小超过2GB的时候，可以按照类似的思路把这个文件继续分为更小的子文件；

（2）按照（1）的方法遍历文件b，把文件b中的url分别存储到文件b0,b1,...,b499中；

（3）通过上面的划分，与ai中相同的url一定在bi中。由于ai与bi中所有的url的大小不会超过4GB，因此可以把它们同时读入到内存中进行处理。具体思路为：遍历文件ai，把遍历到的url存入hash_set中，接着遍历文件bi的url，如果这个url在hash_set中存在，那么说明这个url是这两个文件共同的url，如果这个url在hash_set中存在，那么说明这个url是这两个url是这两个文件共同的url，可以把这个url保存到另外一个单独的文件夹中。当把文件a0~a499都遍历完成后，就找到了两个文件共同的url。

2. 如何从大量数据中找出高频词？

题目描述：有一个1GB大小的文件，文件里面每一行是一个词，每个词的大小不超过16B，内存大小限制是1MB，要求返回频数最高的100个词。

分析：由于文件大小为1GB，而内存大小只有1MB，因此不可能一次把所有的词读入到内存中处理，因此也需要采用分治的方法，把一个大的文件分解成多个小的子文件，从而保证每个文件的大小都小于1MB，进而可以直接被读取到内存中处理，具体的思路为：

（1）遍历文件，对遍历到的每一个词，执行如下Hash操作：hash(x)%2000，将结果为i的词存放到ai中，通过这个分解步骤，可以使每个子文件的大小大约为400KB左右，如果这个操作后某个文件的大小超过1MB了，那么可以采用相同的方法对这个文件继续分解，直到文件的大小小于1MB为止。

（2）统计每个文件中出现频率最高的100个词。遍历文件中的所有词，对于遍历到的词，如果在字典中不存在，就把这个词对应的值+1，遍历完后可以非常容易地找出出现频率最高的100个词。

（3）维护一个小顶堆来找出所有词中出现频率最高的100个，具体方法为：遍历第一个文件，把第一个文件中出现频率最高的100个词构建成一个小顶堆（如果第一个文件中词的个数小于100，那么可以继续遍历第2个文件，直到构建好有100个结点的小顶堆为止）。继续遍历，如果遍历到的词的出现次数大于堆顶上词的出现次数，那么可以用新遍历到的词替换堆顶的词，然后重新调整这个堆为小顶堆。当遍历完所有文件后，这个小顶堆中的词就是出现频率最高的100个词。这一步也可以采用类似归并排序的方法把所有文件中出现频率最高的100个词排序，最终找出出现频率最高的100个词。

引申：在海量数据中找出重复次数最多的一个

前面的算法是求解topk，这道题目是求解top1，将上面的小顶堆变成一个变量就可以了。

3. 如何找出访问百度最多的IP?

题目描述：现有海量日志数据存在一个超级大的文件中，该文件无法直接读入内存，要求从中提取某天访问BD次数最多的那个IP。

分析：先对文件遍历一遍，把一天访问BD的IP信息记录到一个单独的文件中。接下来用上一题的思路求解。需要将大文件分成小文件。以IPV4为例，一个IP地址占用32位，因此最多会有2³²=4G种取值情况。如果使用hash(IP)%1024值，那么把海量IP日志分别存储到1024个小文件中，这样，每个小文件最多包含4M个IP地址；如果使用2048个小文件，每个文件最多包含2M个IP地址。

4. 如何在大量的数据中找出不重复的整数？

题目描述：在2.5亿个整数中找出不重复的整数，注意，内存不足以容纳这2.5亿个整数

思路1：使用hash，把这2.5亿个数划分到更小的文件中，从而保证每个文件的大小不超过可用的内存的大小。然后对于每个小文件而言，所有的数据可用一次性被加载到内存中，因此可以使用字典或set来找到每个小文件中不重复的数。当处理完所有的文件后就可以找出这2.5亿个整数中所有的不重复的数。

思路2：位图法

　　如果可用内存空间超过1GB就可以使用这种方法。具体思路为：假设整数占用4B（如果占用8B，那么求解思路类似，只不过需要占用更大的内存），4B也就是32位，可以表示的整数的个数为2³²。由于本题只查找不重复的数，而不关心具体数字出现的次数，因此可以分别使用2bit来表示各个数字的状态：用00表示这个数字没有出现过，01表示出现过1次，10表示出现了多次，11暂不使用。

　　根据上面的逻辑，在遍历这2.5亿个整数的时候，如果这个整数对应的位图中的位为00，那么修改为01，如果未01，修改为10，如果为10，就保持不变。这样当所有数据遍历完成后，可以再遍历一遍位图，位图中01的对应的数字就是没有重复的数字。

5. 如何在大量的数据中判断一个数是否存在？

6. 如何查询最热门的查询串？

7. 如何统计不同电话号码的个数？

8. 如何从5亿个数中找出中位数？

9. 如何安装query的频度拍戏？

10. 如何找出排序前500的数？

参考文献：

【1】海量数据中找出前k大数（topk问题）

海量数据找相同数,高配词,不重复的数,判断一个数是否存在,查询串,不同电话号码的个数,中位数,安装query频度排序,topk

原文：https://www.cnblogs.com/nxf-rabbit75/p/10558836.html