抖音二面，内存只有 2G，如何对 100 亿数据进行排序？

点击关注公众号，一周多次包邮送书

来源：经授权转自 飞天小牛肉（ID：CS-Wiki）

作者：小牛肉

唠嗑，周末抽空把 CS-Wiki 更新了下，迁移到 vuepress 框架上来了，部署的时候 Gitee Pages 老是提示我有一篇文章包含违规内容，一通折腾最后发现是因为包含了 "ke xue 上网" 这几个字。。。

之前我其实不是很能理解这座墙的意义，见证了俄乌战争、美利坚发动的铺天盖地的舆论攻势之后，我大概能够明白，这座墙，抵御的到底是谁了

大数据小内存排序问题，很经典，很常见，类似的还有比如 “如何对上百万考试的成绩进行排序” 等等

大概有这么三种方法：

• 数据库排序（对数据库设备要求较高）
• 分治法（常见思路）
• 位图法（Bitmap）

1. 数据库排序

将存储着 100 亿数据的文本文件一条一条导入到数据库中，然后根据某个字段建立索引，数据库进行索引排序操作后我们就可以依次提取出数据追加到结果集中。

这种方法的特点就是操作简单， 运算速度较慢，对数据库设备要求较高

2. 分治法

假设 100 亿个数据都是 int 类型的数字

1 个 int 类型占 4 个字节（byte，B）

1 B = 8 位（bit）

1024 B（1024 B = 1KB） = 8 * 1024 bit

1024 * 1024 KB（1024KB = 1MB）= 1024 * 8  * 1024 bit

100 亿 int 型数字就是 100 亿 x 4B = 400 亿 B = 38146.97265625 MB 约等于 37.25GB

100 亿个 int 型数字大概占 37 个 G，2G 内存显然一次性是装不下的。

最常见的思路，拆分成一个一个的小文件来处理呗，最终再合并成一个排好序的大文件。

典型的分治法

1）把这个 37 GB 的大文件，用哈希或者直接平均分成若个小文件（比如 1000 个，每个小文件平均 38 MB 左右）

2）拆分完了之后，得到 1000 个 30 多 MB 的小文件，那么就可以放进内存里排序了，可以用快速排序，归并排序，堆排序等等

3）1000 个小文件内部排好序之后，就要把这些内部有序的小文件，合并成一个大的文件，可以用堆排序来做 1000 路合并的操作（假设是从小到大排序，用小顶堆）：

• 首先遍历 1000 个文件，每个文件里面取第一个数字，组成 (数字, 文件号) 这样的组合加入到堆里，遍历完后堆里有 1000 个 (数字，文件号) 这样的元素
• 然后不断从堆顶 pop 元素追加到结果集，每 pop 一个元素，就根据它的文件号去对应的文件里，补虫一个元素进入堆中，直到那个文件中的元素被拿完
• 按照上面的操作，直到堆被取空了，此时最终结果文件里的全部数字就是有序的了

3. 位图法（Bitmap）

位图法的基本思想就是利用一位（bit）代表一个数字，例如第 3 位上为 1，则说明 3 这个数字出现过，若为0，则说明 3 这个数字没有出现过。很简单~

上面分析过，1M = 8388608 bit（800 多万）

也就是说，通过位图法，只需要 1M 的空间，我们就可以处理 800 多万级别的数据

Java 中没有 bit 这样的基本数据类型，最小数据类型是 byte，我们可以用 byte 数组来实现这个位图法

byte 数组上的每一个元素都是 byte 类型，一个 byte 等于 8 个 bit，我们可以把 10 进制的 byte 用二进制的 bit 来表示，如下图：

这样，byte 数组中的一个元素就能表示 8 个数字是否出现过，比如 byte[0] 可以表示 0 ~ 7 是否出现过，byte[1] 可以表示 8 ~ 15 是否出现过.....

全部处理完之后，我们从前往后遍历一遍 byte 数组就能获取到有序数据了，时间复杂度为 O(N)

java.util 封装了 BitSet 这样一个类，是位图法的典型实现

底层用的 long 数组，一个 long 型数据占 8 个字节（64 位，也就是说 long 数组中的一个元素就可以表示 64 个数字否出现过），占比与只占 1 个字节的 byte（8 位） 来说，能存储的数据更多了

BitSet bitSet = new BitSet();
bitSet.set(0, 2, true);

上面的代码的含义是，第 [0,2) 位会被设置成 1，也就是说这个类会自动地生成一个 long 型的元素，二进制表示是 .....(省略 60 个 0) 0011，十进制表示就是 3

位图法的缺点：

• 可读性差（不是一般的差 🤔）
• 位图存储的元素个数虽然比一般做法多，但是存储的元素大小受限于存储空间的大小。要想定义存储空间大小就需要实现知道存储的元素到底有多少
• 对于有符号类型的数据，需要用 2 位来表示，比如 第 0 位和第 1 位表示 0 这个数据，第 2 位和第 3 位表示 1 这个数据......，这会让位图能存储的元素个数，元素值大小上限减半

·················END·················

推荐阅读

👇更多内容请点击👇