爱吃咖喱棒的打字员DA☆ZE~

0%

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 可以对海量不重复的整数进行排序,也可以对海量的整数进行快速查询和快速去重。