海量数据题我之前整理过一部分，这里就直接贴出来了，抛砖引玉。

常见解题思路：

• 分治：hash 后单独处理，最后合并
• 布隆过滤器
• 位图法
• 最大/最小堆

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

首先我们要了解**IP长啥样：255.255.255.255，我们又知道2^8 = 256，所以这里需要4个8 bit，也就是4 * 8 = 32 bit，每个bit有两种可能，所以一共有2^32种IP，我们拆分成1024**个文件：

2^10 = 1024
2^32 / 2^10 = 2^22 = 2^2 * 2^20 = 4M

也就是说每个文件的大小为**4M，接下来我们遍历日志文件，把每个IP采用哈希方式映射到1-1024个文件中，那么相同IP就会到达同一个文件中，然后对每个文件求IP的最大重复数，最后对1024**个文件的各个最大值再求一次最大值，得到最终结果。

• 类似题目：

2. 32位的机器，2亿个整数中找不重复数字？

首先我们理清楚题意，说白了就是两亿个**int整数，我们必然是要遍历这2亿个整数的，这个过程中会出现三种状态：未出现、出现、重复出现，既然是三种状态，1位不够用，我们用2位来存，00代表未出现，01代表出现一次，10代表多次重复出现，我们首先遍历2亿个整数，然后出现的整数就把对应位置改为01，如果当前状态已经是01，则改为10**，那么这样遍历一遍之后，我们就再遍历一遍用来存储的数据，根据状态就知道哪些是不重复数字了。

3. 如何快速判断某个数是否在40亿个整数当中？

完整题目大致如下：给**40亿个不重复的unsigned int**的整数，没有排序，然后再给一个数，判断是否存在。

这题就是很明显的布隆过滤器了，与前一题不同的是，我们可以不需要用两位来表示一个整数，毕竟这里只需要存在和不存在两个情况，1 bit就足够了，所以我们可以用类似上面的思路，先遍历40 亿个整数，出现了，则将相应位置的bit修改为1，判断的时候也只需判断对应位置的**bit是0还是1。0则代表不存在，1**则代表存在。

4. 取超大文件数字交集

现有两个各有**20亿**行的文件，每一行都只有一个数字，求这两个文件的交集。

因为 int的范围长度是2^32 == 4G ≈ 40亿，用一个**bit来表示一个int值，大概需要4G个bit位，即约4G/8 = 552M**的内存。这可以解决问题了

• 如果都是正数：