海量数据类型场景设计题（超全！）

1.统计不同号码的个数(位图)

这类题目其实是求解数据重复的问题。对于这类问题，可以使用位图法处理

8位电话号码可以表示的范围为00000000～99999999。如果用 bit表示一个号码，那么总共需要1亿个bit，总共需要大约10MB的内存。

申请一个位图并初始化为0，然后遍历所有电话号码，把遍历到的电话号码对应的位图中的bit设置为1。当遍历完成后，如果bit值为1，则表示这个电话号码在文件中存在，否则这个bit对应的电话号码在文件中不存在。

最后这个位图中bit值为1的数量就是不同电话号码的个数了。

2.出现频率最高的100个词

题目

假如有一个1G大小的文件，文件里每一行是一个词，每个词的大小不超过16byte，要求返回出现频率最高的100个词。内存大小限制是10M

解法一

这种解法的主要思路如下：

1. 采用分治的思想，进行哈希取余
2. 使用HashMap统计每个小文件单词出现的次数
3. 使用小顶堆，遍历步骤2中的小文件，找出词频top100的单词

由于内存限制，我们无法直接将大文件的所有词一次性读到内存中。

可以采用分治策略，把一个大文件分解成多个小文件，保证每个文件的大小小于10M，进而直接将单个小文件读取到内存中进行处理。

第一步，首先遍历大文件，对遍历到的每个词x，执行 hash(x) % 500，将结果为i的词存放到文件f(i)中，遍历结束后，可以得到500个小文件，每个小文件的大小为2M左右；

第二步，接着统计每个小文件中出现频数最高的100个词。可以使用HashMap来实现，其中key为词，value为该词出现的频率。

对于遍历到的词x，如果在map中不存在，则执行 map.put(x, 1)。

若存在，则执行 map.put(x, map.get(x)+1)，将该词出现的次数加1。

第三步，在第二步中找出了每个文件出现频率最高的100个词之后，通过维护一个小顶堆来找出所有小文件中出现频率最高的100个词。

具体方法是，遍历第一个文件，把第一个文件中出现频率最高的100个词构建成一个小顶堆。

如果第一个文件中词的个数小于100，可以继续遍历第二个文件，直到构建好有100个结点的小顶堆为止。

继续遍历其他小文件，如果遍历到的词的出现次数大于堆顶上词的出现次数，可以用新遍历到的词替换堆顶的词，然后重新调整这个堆为小顶堆。

当遍历完所有小文件后，这个小顶堆中的词就是出现频率最高的100个词。

但是很容易可以发现问题，在第二步中，如果这个1G的大文件中有某个词词频过高，可能导致小文件大小超过10m。这种情况下该怎么处理呢？

接下来看另外一种解法

解法二

第一步：使用多路归并排序对大文件进行排序，这样相同的单词肯定是紧挨着的

多路归并排序对大文件进行排序的步骤如下：

① 将文件按照顺序切分成大小不超过2m的小文件，总共500个小文件

② 使用10MB内存分别对 500 个小文件中的单词进行排序

③ 使用一个大小为500大小的堆，对500个小文件进行多路排序，结果写到一个大文件中

其中第三步，对500个小文件进行多路排序的思路如下：

• 初始化一个最小堆，大小就是有序小文件的个数500。堆中的每个节点存放每个有序小文件对应的输入流。
• 按照每个有序文件中的下一行数据对所有文件输入流进行排序，单词小的输入文件流放在堆顶。
• 拿出堆顶的输入流，并其下一行数据写入到最终排序的文件中，如果拿出来的输入流中还有数据的话，那么将这个输入流再一次添加到栈中。否则说明该文件输入流中没有数据了，那么可以关闭这个流。
• 循环这个过程，直到所有文件输入流都没有数据为止。

第二步：

① 初始化一个100个节点的小顶堆，用于保存100个出现频率最多的单词

② 遍历整个文件，一个单词一个单词的从文件中取出来，并计数

③ 等到遍历的单词和上一个单词不同的话，那么上一个单词及其频率如果大于堆顶的词的频率，那么放在堆中，否则不放

最终，小顶堆中就是出现频率前100的单词了。

解法2相对解法1，更加严谨，如果某个词词频过高或者整个文件都是同一个词的话，解法1不适用。

3.查找两个无序大文件共同的URL

题目

给定 a、b 两个文件，各存放 50 亿个 URL，每个 URL 各占 64B，找出 a、b 两个文件共同的 URL。内存限制是 4G。

总结一下：

1. 分而治之，进行哈希取余；
2. 对每个子文件进行 HashSet 统计。

具体思路

每个 URL 占 64B，那么 50 亿个 URL占用的空间大小约为 320GB。

5,000,000,000 * 64B ≈ 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 存储到一