[TOC]
1MB=2^20B
1KB=2^10B=10^3B
1.共同URL
给定 a、b 两个文件，各存放 50 亿个 URL，每个 URL 各占 64B，内存限制是 4G。请找出 a、b 两个文件共同的 URL。
解答思路
每个 URL 占 64B，那么 50 亿个 URL占用的空间大小约为 320GB。
5,000,000,000 * 64B ≈ 5GB * 64 = 320GB
由于内存大小只有 4G，因此，我们不可能一次性把所有 URL 加载到内存中处理。对于这种类型的题目，一般采用分治策略，即：把一个文件中的 URL 按照某个特征划分为多个小文件，使得每个小文件大小不超过 4G，这样就可以把这个小文件读到内存中进行处理了。
思路如下：
首先遍历文件 a，对遍历到的 URL 求 hash(URL) % 1000，根据计算结果把遍历到的 URL 存储到文件 a0, a1, a2, …, a999，这样每个大小约为 300MB。使用同样的方法遍历文件 b，把文件 b 中的 URL 分别存储到文件 b0, b1, b2, …, b999 中。这样处理过后，所有可能相同的 URL 都在对应的小文件中，即 a0 对应 b0, …, a999 对应 b999，不对应的小文件不可能有相同的 URL。那么接下来，我们只需要求出这 1000 对小文件中相同的 URL 就好了。
接着遍历 ai( i∈[0,999])，把 URL 存储到一个 HashSet 集合中。然后遍历 bi 中每个 URL，看在 HashSet 集合中是否存在，若存在，说明这就是共同的 URL，可以把这个 URL 保存到一个单独的文件中。
方法总结
1.分而治之，进行哈希取余；2.对每个子文件进行 HashSet 统计。
2.频率Top100
题目描述
有一个 1GB 大小的文件，文件里每一行是一个词，每个词的大小不超过 16B，内存大小限制是 1MB，要求返回频数最高的 100 个词(Top 100)。
解答思路
由于内存限制，我们依然无法直接将大文件的所有词一次读到内存中。因此，同样可以采用分治策略，把一个大文件分解成多个小文件，保证每个文件的大小小于 1MB，进而直接将单个小文件读取到内存中进行处理。
思路如下：
首先遍历大文件，对遍历到的每个词x，执行 hash(x) % 5000，将结果为 i 的词存放到文件 ai 中。遍历结束后，我们可以得到 5000 个小文件。每个小文件的大小为 200KB 左右。如果有的小文件大小仍然超过 1MB，则采用同样的方式继续进行分解。
接着统计每个小文件中出现频数最高的 100 个词。最简单的方式是使用 HashMap 来实现。其中 key 为词，value 为该词出现的频率。具体方法是：对于遍历到的词 x，如果在 map 中不存在，则执行 map.put(x, 1)；若存在，则执行 map.put(x, map.get(x)+1)，将该词频数加 1。
上面我们统计了每个小文件单词出现的频数。接下来，我们可以通过维护一个小顶堆来找出所有词中出现频数最高的 100 个。具体方法是：依次遍历每个小文件，构建一个小顶堆，堆大小为 100。如果遍历到的词的出现次数大于堆顶词的出现次数，则用新词替换堆顶的词，然后重新调整为小顶堆，遍历结束后，小顶堆上的词就是出现频数最高的 100 个词。
方法总结
1.分而治之，进行哈希取余；2.使用 HashMap 统计频数；3.求解最大的 TopN 个，用小顶堆；求解最小的 TopN 个，用大顶堆。
3.找不重复
题目描述
在 2.5 亿个整数中找出不重复的整数。注意：内存不足以容纳这 2.5 亿个整数。
解答思路
方法一：分治法
与前面的题目方法类似，先将 2.5 亿个数划分到多个小文件，用 HashSet/HashMap 找出每个小文件中不重复的整数，再合并每个子结果，即为最终结果。
方法二：位图法
位图，就是用一个或多个 bit 来标记某个元素对应的值，而键就是该元素。采用位作为单位来存储数据，可以大大节省存储空间。
位图通过使用位数组来表示某些元素是否存在。它可以用于快速查找，判重，排序等。不是很清楚？我先举个小例子。
假设我们要对 [0,7] 中的 5 个元素 (6, 4, 2, 1, 5) 进行排序，可以采用位图法。0~7 范围总共有 8 个数，只需要 8bit，即 1 个字节。首先将每个位都置 0：
1 | 00000000 |
然后遍历 5 个元素，首先遇到 6，那么将下标为 6 的位的 0 置为 1；接着遇到 4，把下标为 4 的位 的 0 置为 1：
1 | 00001010 |
依次遍历，结束后，位数组是这样的：
1 | 01101110 |
每个为 1 的位，它的下标都表示了一个数：
1 | for i in range(8):if bits[i] == 1:print(i) |
这样我们其实就已经实现了排序。
对于整数相关的算法的求解，位图法是一种非常实用的算法。假设 int 整数占用 4B，即 32bit，那么我们可以表示的整数的个数为 2^32。
那么对于这道题，我们用 2 个 bit 来表示各个数字的状态：
•00 表示这个数字没出现过；•01 表示这个数字出现过一次（即为题目所找的不重复整数）；•10 表示这个数字出现了多次。
那么这 232 个整数，总共所需内存为 2^32*2b=1GB。因此，当可用内存超过 1GB 时，可以采用位图法。假设内存满足位图法需求，进行下面的操作：
遍历 2.5 亿个整数，查看位图中对应的位，如果是 00，则变为 01，如果是 01 则变为 10，如果是 10 则保持不变。遍历结束后，查看位图，把对应位是 01 的整数输出即可。
方法总结
判断数字是否重复的问题，位图法是一种非常高效的方法。
4.1亿个正整数,范围是0-42亿。求出现次数是2的数字，空间复杂度
使用位图bitMap 。位图是以 bit 位为单位进行数据存储，这样每个字节8个位就可以存储8个数字，普通的一个int占4个字节，32位，用了位图之后可以将空间节省32倍。
开一个42亿大小的位图，将这一亿个数字存进数字大小对应的位置，一个bit每存进去一个数字，就将value+1,比如第一次存8，就将索引为8的位置的value置为1，第二次就置为2，存完之后搜索value为2的key是多少。
32位机器最大能表示的数字是42亿9千多万。
42亿bit /(8 * 1024 * 1024) = 500MB
5.有一个IP地址库，假设有几十万条ip，如何判断某个ip地址是否在这个库中？
思路一：分治法，将ip地址根据前三位分成256份，然后看这个ip地址对应的网段，只比对这个网段里面是否有这个ip，当然还可以继续分下去，根据数据量来决定分成多少份。
思路二：位图，将每一条ip对应位图中的一个位，2^32次方(42亿多)个数据只需要512M空间。可以实现O(1)的时间搜索，O(n)的时间存储。
6. 2g内存，要求一个10g文件的中位数**
如题 “在一个文件中有 10G 个整数,乱序排列,要求找出中位数(内存限制为 2G)”
原创，网上这个题目有好多答案，但是有好多都不准确。
假设整数用32bit来表示。
第一步：要表示10G个整数，最少需要一个64位的数据空间。（10G = 5 * 2^31 > 2^32 )
第二步：分区间
2G的内存，能够表示多少个64bit，就能分多少个区间。（一个区间 就表示 一个64bit的数据空间）
区间数位：2G / 64bit = 256M 个区间。
第三步：求区间表示范围
32bit的整数最大值为2^32-1,所以区间的范围是2^32 / 256M = 16.
即0 ~ 15 ，16 ~ 31，32 ~ 47，……（总共256M个)
此时我们有 256M个区间，大小总共为256M * 64bit = 2G内存。
第四步：遍历10G个整数。每读取一个整数就将此整数对应的区间+1。
第五步：找出中位数所在的区间
统计每个区间中整数的值。然后从第一个区间的整数值开始累加。当累加到5G时，停止。此时的区间便包含中位数。记下此区间所表示的范围，设为[a,a+15].并且记下此区间之前所有区间的累加和，设为m。释放掉除包含中位数区间的其他所有区间的内存。
第六步：再次遍历10G个整数，统计出现在区间[a,a+15]中每个值的计数，有16个数值，按照a到a+15排序。设为n0,n1,n2,…n15
第七步：当m+n0+n1+…+nx首次大于5G时，此时的 a+x 就是所求的中位数。
7.