海量数据处理

大数据题目的处理技巧：

• 分治法：将大文件按照 hash(x) % n 的方法分成 n 个小文件，依次对 n 个小文件进行处理
• HashMap：通过 HashMap 存储元素及其个数
• 位图：使用位图统计每个元素是否出现过
• 小顶堆：用于统计 TOP N 的数据，遍历文件实时跟新小顶堆以保证小顶堆永远是值最大的 N 个数值
• 前缀树：用于统计含有大量相似或重复的字符串，前缀树节点中要记录每个字符串的数量

参考：advanced-java (opens new window)

1 如何从大量 URL 中找出相同的 URL ？

题目描述

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

解答思路

50 亿个 64B 的 URL 共占用 620 G 空间，如果把他分成 1000 份，平均每份 320 M，就可以放入内存中。

采用分治策略，逐步读取遍历 a 文件，对遍历到的 URL 求 hash(URL) % 1000，根据不同的结果存储在不同的文件 a0, a1, a2, ... 中，这样大概就会有 1000 份文件。对 b 文件采用相同的方法，得到 b0, b1, b2, ...

接着遍历ai，把 URL 存储到一个 HashSet 中，然后再遍历 bi 中的每一个 URL，查看 HashSet 集合中是否存在。

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

题目描述

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

解答思路

采用分治策略，逐步读取遍历文件中的每个单词 x，执行 hash(x) % 5000，将结果为 i 的单词存放到文件 ai 中，这样我们可以得到 5000 个小文件。如果这个小文件过大的话，可以对这个小文件继续进行拆分。

用 HashMap 统计每个小文件中出现频率最高的的 100 个单词。维护一个小顶堆来找出所有词中频率最高的 100 个。具体方法：构建大小为 100 的小顶堆，依次遍历每个小文件的 TOP100，如果遍历到的词出现的次数大于堆顶的词，则用新词替换并重新调整堆，遍历结束后，小顶堆上的词就是 TOP 100.

3 如何找出某一天访问百度网站最多的 IP？

题目描述

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

解答思路

采用分治策略，逐步读取遍历文件中的每个 IP，计算 hash(IP) % 1000，将结果为 i 的 url 存放到文件 ai 中，这样就可以得到 1000 个小文件。

使用 HashMap 统计出每个小文件中出现次数最多的IP，遍历所有小文件得到这个次数最多的 IP。

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

题目描述

在 2.5 亿个整数中找出不重复的整数。注意：内存不足以容纳这 2.5 亿个整数。

方法一：分治法

与前面的题目方法类似，先将 2.5 亿个数划分到多个小文件，用 HashSet/HashMap 找出每个小文件中不重复的整数，再合并每个子结果，即为最终结果。

方法二：位图法

假设这 2.5 亿个整数都是 int 整数，占用 4B，即 32bit，那么我们可以表示的整数的个数为 2³²。我们可以用 2 bit 来标识各个数字的状态：

• 00 表示这个数字没出现过；
• 01 表示这个数字出现过一次（即为题目所找的不重复整数）；
• 10 表示这个数字出现了多次。

那么这写整数，共需要内存为： $$ 2^{32} * 2 b = 1 GB $$ 当 内存超过 1GB 时，可以采用这种方法，逐步读取遍历这 2.5 亿 个整数，查看位图中对应的为，如果是00，则变为01，01则变为10，10保持不变。最后在遍历位图，找出对应位是 01 的整数输出。

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

题目描述

给定 40 亿个不重复的没排过序的 unsigned int 型整数，然后再给定一个数，如何快速判断这个数是否在这 40 亿个整数当中？

方法一：分治法

分为多个小文件，分别判断每个小文件中是否存在这个数。（与前面题目的方法差不多）

方法二：位图法

由于 unsigned int 数字的范围是 [0, 1 << 32)，我们用 1<<32=4,294,967,296 个 bit 来表示每个数字。初始位均为 0，那么总共需要内存：4,294,967,296b≈512M。

我们读取这 40 亿个整数，将对应的 bit 设置为 1。接着读取要查询的数，查看相应位是否为 1，如果为 1 表示存在，如果为 0 表示不存在。

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

题目描述

搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度不超过 255 字节。

假设目前有 1000w 个记录（这些查询串的重复度比较高，虽然总数是 1000w，但如果除去重复后，则不超过 300w 个）。请统计最热门的 10 个查询串，要求使用的内存不能超过 1G。（一个查询串的重复度越高，说明查询它的用户越多，也就越热门。）

方法一：分治法（同题目2）

每个查询串最长为 255B，1000w 个串需要占用 约 2.55G 内存，因此，我们无法将所有字符串全部读入到内存中处理。

划分为多个小文件，保证单个小文件中的字符串能被直接加载到内存中处理，然后求出每个文件中出现次数最多的 10 个字符串；最后通过一个小顶堆统计出所有文件中出现最多的 10 个字符串。

方法二：HashMap 法

虽然字符串总数比较多，但去重后不超过 300w，因此，可以考虑把所有字符串及出现次数保存在一个 HashMap 中，所占用的空间为 300w*(255+4)≈777M（其中，4 表示整数占用的 4 个字节）。由此可见，1G 的内存空间完全够用。

逐步遍历日志文件，并将每个文件出现的次数存储到 HashMap 中。再次遍历 HashMap 构建一个小顶堆。

方法二：前缀树法

方法二使用了 HashMap 来统计次数，当这些字符串有大量相同前缀时，可以考虑使用前缀树来统计字符串出现的次数，树的结点保存字符串出现次数，0 表示没有出现。

在遍历字符串时，在前缀树中查找，如果找到，则把结点中保存的字符串次数加 1，否则为这个字符串构建新结点，构建完成后把叶子结点中字符串的出现次数置为 1。

最后依然使用小顶堆来对字符串的出现次数进行排序。

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

题目描述

已知某个文件内包含一些电话号码，每个号码为 8 位数字，统计不同号码的个数。

解答思路

这道题本质还是求解数据重复的问题，对于这类问题，一般首先考虑位图法。

对于本题，8 位电话号码可以表示的号码个数为 10⁸ 个，即 1 亿个。我们每个号码用一个 bit 来表示，则总共需要 1 亿个 bit，内存占用约 12M。

申请一个位图数组，长度为 1 亿，初始化为 0。然后遍历所有电话号码，把号码对应的位图中的位置置为 1。遍历完成后，如果 bit 为 1，则表示这个电话号码在文件中存在，否则不存在。最后统计位图中值为 1 的数量。

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

题目描述

从 5 亿个数中找出中位数。数据排序后，位置在最中间的数就是中位数。当样本数为奇数时，中位数为 第 (N+1)/2 个数；当样本数为偶数时，中位数为 第 N/2 个数与第 1+N/2 个数的均值。

方法一：双堆法，需要把数据全部读取到内存中

维护两个堆，一个大顶堆，一个小顶堆。大顶堆中最大的数小于等于小顶堆中最小的数；保证这两个堆中的元素个数的差不超过 1。

若数据总数为偶数，当这两个堆建好之后，中位数就是这两个堆顶元素的平均值。当数据总数为奇数时，根据两个堆的大小，中位数一定在数据多的堆的堆顶。

方法二：分治法

顺序读取这 5 亿个数字，对于读取到的数字 num，如果它对应的二进制中最高位为 1，则把这个数字写到 f1 中，否则写入 f0 中。通过这一步，可以把这 5 亿个数划分为两部分，而且 f0 中的数都大于 f1 中的数（最高位是符号位）。

划分之后，可以非常容易地知道中位数是在 f0 还是 f1 中。假设 f1 中有 1 亿个数，那么中位数一定在 f0 中，且是在 f0 中。对于 f0 可以用次高位的二进制继续将文件一分为二，如此划分下去，直到划分后的文件可以被加载到内存中，把数据加载到内存中以后直接排序，找出中位数。

9 如何按照 query 的频度排序？

题目描述

有 10 个文件，每个文件大小为 1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求按照 query 的频度排序。

分治法

可以顺序遍历 10 个文件中的 query，通过 Hash 函数 hash(query) % 10 把这些 query 划分到 10 个小文件中。之后对每个小文件使用 HashMap 统计 query 出现次数，根据次数排序并写入到另外一个单独文件中。

接着对所有文件按照 query 的次数进行排序，这里可以使用归并排序（由于无法把所有 query 都读入内存，因此需要使用外排序）。