Bitmap

先考虑一个问题：有 40 亿个不重复且无序的无符号整数，如何判断一个整数是否在这 40 亿个整数中，要求使用的内存不超过 2GB。

假设使用 Java 语言，由于一个 int 类型的整数占用 4 个字节，如果使用 int 类型来存储这些数据，40 亿个整数占用大概 14.9GB（40 亿 * 4/1024/1024/1024）的内存，很明显这是不符合要求的。一个常规的思路就是将 40 亿个整数分片，每次读取一个分片到内存中进行判断。如果我们一定要一次性将这些数据存放到不超过 2GB 的内存中呢？这时我们就需要用到一个特殊的算法，这就是 Bitmap 算法。

Bitmap 概述

在《编程珠玑》中提到，所谓的 Bitmap 就是使用一个 bit 位来标记（使用 1 或 0 来标记）某个元素对应的 value，而 key 就是该元素。由于数据使用 bit 为单位来存储，因此需要的存储空间可以被大幅度地压缩。

从字面上好像不太好理解这个定义，下面通过一个例子来详细说明。假如我们需要对 0 到 7 之间的五个整数 5 3 7 6 4 进行排序，这五个整数没有重复。根据定义，要表示 0 到 7 之间的数就需要 8 bit 的存储空间。我们首先开辟 1byte 的空间，然后将这个空间中所有的 bit 位都置为 0。接下来遍历整数集合，第一个元素为 5 ，则将 5 对应的位置置为 1。

以此类推，最终遍历的结果为：

所有的数都落到了对应的位置上，接下来根据排序规则，将值为 1 的位置输出即可。

从上面的例子可以看出，使用 Bitmap 算法进行排序时，优点是运算效率相对较高，不需要进行比较和移位，并且通常内存占用极少。缺点是所有的数据不能重复，且只能对整数进行排序。当样本数据分布极度不均匀时，空间浪费严重。比如需要对 3 4 2 7 99999 这五个数进行排序时，就需要开辟 99999bit 的空间，而其中大部分空间永远不会被用到，浪费严重。

快速查询

我们回到一开始的题目上。在思考这个问题时，我就陷入了一个误区，我的思路是：这 40 亿个整数，我该如何通过 Bitmap 来存储呢？类似上面的排序过程，每个整数本身就是 key，通过这个 key 找到 Bitmap 上对应的位置，将值置为 1。按照这个思路，我需要知道这 40 亿个整数中最大的那个整数值是多少，只有这样我才能知道该分配多少 bit 的内存。

其实完全没有必要将这 40 亿个整数本身（这是关键）存放到 Bitmap 中，只需要通过某种方式将这 40 亿个整数映射到 Bitmap 中即可。所以此时我需要的内存容量其实为 40 亿 bit，每个 bit 位标记某一个整数是否存在（1 或 0），总共需要约 (40 亿 /8/1024/1024) 476 MB 的内存，占用的空间缩小为原来使用 int 类型的 1/32。

接下来需要做的就是，设计一个足够好的 Hash 算法，将这 40 亿个整数唯一映射到 Bitmap 上。假设已经找到了这么一个 Hash 函数，将需要判断是否存在的那个整数进行一次 Hash 运算，然后在 Bitmap 上查找该位置的值是否为 1 即可。如果是 1，则表示该整数已经存在；如果是 0，则表示不存在该整数。当然这都是理想状态下，实际能不能设计出这么一个 Hash 算法还不清楚，但是起码思路是正确的。

快速去重

尽量用少的内存，如何在 20 亿个整数中找出不重复的（或者重复的）整数个数？

像这一类问题，首先能够想到的是使用 Bitmap 算法。在之前的问题中，我们都是使用一个 bit 来表示数字是否存在，在该问题中显然不适用。在这里我们可以使用两个 bit 来表示数字的状态：00 表示不存在，01 表示存在一次，11 表示存在重复。接下来就是遍历这 20 亿个整数，将这些整数映射到 Bitmap 上。在映射的过程中，如果对应的状态位为 00，则置为 01；如果为 01，则置为 11；如果为 11，则不变。最终根据要求统计状态位的个数即可。

总结

使用 Bitmap 可以对海量不重复的整数进行排序，也可以对海量的整数进行快速查询和快速去重。