大数据小内存问题

数据量和内存的关系

常常有这样一类问题，数据量很大，但计算机内存很小，无法将所有数据一次性加载进内存处理，如：在 20 亿个整数中找到出现次数最多的数。在正式介绍这一类问题前，先分析一下数据量和内存之间的关系

假设每一个数据都是int类型，占 4 个字节，那么 1 亿个数据就是 $4\times {10}^8$$4 \times 10^8$ 字节，也就是 $\frac{4\times {10}^8}{1024\times 1024\times 1024}$$\frac{4 \times 10^8}{1024 \times 1024 \times 1024}$ GB，等于 0.37252902984 GB，约等于 0.4 GB

所以，我们稍微可以有一个概念：1 亿个int类型的数据大约占 0.4 GB 内存，也就是 4 亿个字节大约占 0.4 GB 内存

常用方法

对于这一类大数据小内存的问题，解法其实都大同小异，主要有两类方法：分治法、位图法

分治法的核心：将待处理的数据分片，以片为单位处理。举个简单的例子，对于 20 亿数据，大约为 8 GB，每次只处理 0.5 GB 数据，分 16 次处理

位图法的核心：以每一位表示一个数据，那么 1 个字节可以表示 8 个数据，20 亿数据只需要 0.23283064365 GB，约等于 0.2 GB

问题一：在 20 亿个整数中找到出现次数最多的数

一般思路：使用一个 HashMap 统计每个整数出现的次数，然后就可以获得出现次数最多的数

假设 HashMap 的 key 和 value 都是int类型，且大约有 2 亿个不同的数，那么每一个数都需要 8B 来计数，2 亿个数大约需要 1.6 GB

极端一点，假设 20 亿个整数中每个数都不相同，那么大约需要 16 GB

正确思路：根据数据范围将 20 亿整数分为若干个小文件，然后统计每个小文件中整数出现的次数，最后比较每个小文件中出现次数最多的整数，获得全局出现次数最多的整数

举个简单的例子，假设全局数据范围在[0, 100]，那么可以将在范围[0, 50]的数分到一个文件中，在范围[51, 100]的数分到一个文件中

最后比较范围[0, 50]中出现次数最多的数和范围[51, 100]中出现次数最多的数，选择出现次数更多的即为全局出现次数最多的数

扩展一：如果数据分布不均匀，某个范围区间内的数过多怎么处理？

不根据范围划分，而改用哈希函数映射，相同值的整数的哈希值一定相同，如果哈希函数设计的好，可以使分布比较均匀

扩展二：如果将数据量增加到 40 亿，且 40 亿个数都是一样的

如果还使用int类型来计数会溢出，int类型最大值约为 21 亿，简单粗暴的方法就是改用long类型，虽然内存会使用更多

但还有一种方法，以Integer.MIN_VALUE为 0，那么int类型就可以记录 40 亿的次数

扩展三：如果将数据量增加到 80 亿，怎么只使用int类型统计？

这个扩展的目的在于就算使用扩展二中的技巧，int类型最多也只能记录 42 亿出现次数，那么如何使用int类型统计 80 亿数据量呢？

当一个数出现的次数大于 40 亿次，那么该数一定就是出现最多的数，即可停止统计，因为 40 亿超过了一半，不可能有其它数出现超过 40 亿次

问题二：对 100 亿个整数排序

利用分治的思想，将 100 亿个整数分为若干个小文件，先对小文件进行内部排序，然后使用优先队列将若干个小文件合并成一个有序文件，每次都只需要取每个文件中的一个元素，类似于合并 k 个有序链表

问题三：判断 URL 是否在包含 100 亿条数据的黑名单中

这个问题的使用场景也很常见，如：网站黑名单系统、垃圾邮件过滤系统、爬虫网站判重系统，一般都允许一定失误率，但对空间使用较为严格

回到本问题，网站过滤系统要求如下：

• 允许万分之一以下的判断失误率

• 使用的额外空间不能超过 30 GB

一般思路：使用 Set 集合保存报名单中的 URL，每次只需要判断 Set 中是否包含 URL 即可

注意：HTTP 并没有规定 URL 的长度，但浏览器有限制，对于 Chrome 来说，好像是 8182 字节，更多可见 HTTP URL最大长度

假设浏览器规定每个 URL 最多占用 64 字节，那么 100 亿条数据大约需要 640 GB 内存空间，显然太大了

正确思路：使用布隆过滤器，它用很少的空间可以保证较高的准确率，完全没有错误不可能

布隆过滤器有一个长度为 m 位的数组，每个位置只占一个 bit，非常节约空间，同时它还有 n 个 Hash 函数，每个 Hash 函数都可以将 URL 映射到[0, m)区间内，具体结构如下图所示：

如上图所示，一个 URL 经过 n 个 Hash 函数后得到 n 个[0, m)区间的数，将这些数在布隆过滤器的位数组中标记为 1

当我们需要判断一个 URL 是否在黑名单中时，只需要将 URL 经过 n 个 Hash 函数得到 n 个[0, m)区间的数：

• 如果这些数在布隆过滤器的位数组中均标记为 1，表示很大很可能该 URL 在黑名单中 (并非一定在哈～)

• 如果这些数在布隆过滤器的位数组中有一个不为 1，表示该 URL 一定不在黑名单中

问题四：在 40 亿非负整数中找出所有未出现的数

先对这个问题进行一下补充，对于 32 位无符号整数，它的范围是 $[0,2^{32}-1]$$[0, 2^{32} - 1]$，即 $[0,4294967295]$$[0, 4294967295]$，现在有一个 40 亿数据量的文件，文件中的数都在无符号整数范围内，现在需要找出无符号整数范围内没有出现的数

举例：对于范围[0, 10)，文件中包含[0, 1, 4, 5, 6, 8]，那么范围[0, 10)内没有出现的数为：[2, 3, 7, 9]

一般思路：使用位图，每一位表示一个数，该位为 1 表示该数存在，该位为 0 表示该数不存在。40 亿个数大约需要 500MB 内存大小。那有没有空间更小的做法呢？

优化思路：首先按照分组统计，如果组内数量不足再使用位图寻找缺失整数

将 $2^{32}$$2^{32}$ 个整数分为 64 组，每组正常情况下应该有 $2^{26}$$2^{26}$ 个数，如果某个组不满足 $2^{26}$$2^{26}$ 个数，表示该组有缺失整数，然后对该组使用位图寻找缺失整数

以上面为例，将[0, 10)分为 5 组，每组内 2 个数，如下图所示：

如上图所示，只有第 2、4、5 组缺少数，所以只需要对 2、4、5 组使用位图寻找缺失整数即可

问题五：在 100 亿个整数中找到中位数

寻找中位数最简单的方法就是排序后根据下标获取中位数，但 100 亿个整数不可能一次性加载到内存中，所以可以像 问题二：对 100 亿个整数排序 一样使用外部排序，然后在多路归并时获取中位数

这里再介绍另外一种方法，首先创建多个小文件桶，为每个桶设置取值范围，然后统计每个桶内的元素个数，接着计算中位数所在的桶，最后仅对中位数所在的桶排序即可

举个例子，如果一共 100 个数，那么中位数就在第 50 和 51 位数取得，如下图所示：

问题六：在 2 亿个整数中找出不连续的最小数

先对这个问题进行一下补充，2 亿个整数，从 0 开始找出不连续的最小数，如：[0, 1, 2, 3, 4, 6, 7, 8]，那么不连续的最小数为 5

可以使用位图来标记某个数是否出现，2 亿个整数需要大约 25 MB 的内存大小，最后遍历位图，第一个断开连续的数即为要寻找的不连续最小数