简介

bitmap在很多海量数据处理的情况下会用到。一些典型的情况包括数据过滤，数据位设置和统计等。 它的引入和应用通常是考虑到海量数据的情况下，用普通的数组会超出数据保存的范围。使用这种位图的方式虽然不能在根本上解决海量数据处理的问题，但是在一定的数据范围内，它是一种有效的方法。bitmap在java的类库里有一个对应的实现：BitSet。我们会对bitmap的引入做一个介绍，然后详细分析一个bitvector的精妙实现，并在后面和java中的BitSet实现做一个对比。在本文中对bitmap, bitvector不做区分，他们表达的是同一个意思。

bitmap的引出

假设我们有一个很大的数据集合，比如说是一组数字，它是保存在一个很大的文件中。它总体的个数为400个亿。里面有大量重复的数据，如果去除重复的元素之后，大概的数据有40个亿。那么，假定我们有一台内存为2GB的机器。我们该如何来消除其中重复的元素呢？再进一步考虑，如果我们消除了重复的元素之后，怎么统计里面元素的个数并将消重后的元素保存到另外的一个结果文件里呢？

我们先来做一个大致的估计。假定数字的范围都是从0到Integer.MAX_VALUE。如果我们开一个数组来保存的话，是否可行呢？一个int数字4个字节，要保存0到Integer.MAX_VALUE个数字，那么就需要2的31次方个，也就是说2G个元素。这么一相乘，除非有8GB的内存，否则根本就保存不下来这么多数据。

bitmap分析和应用

现在，如果我们换一种方式，用bitmap试试呢？bitmap它本质上也是一个数组，只是用数组中间对应的位来表示一个对应的数字。假设我们用byte数组。比如说数字1则对应数组第1个元素的第一位。数字9则超出了第一个元素的8位范围，它对应第二个元素的第一位。这样依次类推，我们可以将这40亿个元素映射到这个byte数组里。一个数字对应到数组中位的关系如下图所示：

在上图中，假设i是数组中的一个字节，那么它将对应有下面的8个位。假设i是第一个字节，那么数字1就对应到第1位，后面的元素依次类推。

通过这一番讨论，我们也可以很容易得到数字和保存在数组中元素具体位之间的关系。假设有一个数字i，它对应保存的元素位置为: i / 8。假设数组为a，那么则为a[i/8]。那么它对应到a[i/8]中间的哪个位呢？它对应这个元素中的第i % 8这一位。

有了这些讨论，我们再来看bitmap的一个具体实现。

bitmap的一个实现

针对前面讨论的部分，bitmap主要的功能包括有一下几个方面。

1. 置位(set)：将某一位置为1.

2. 清楚位(clear)，清楚某一位，将其置为0.

3. 读取位(get)，读取某一位的数据，看结果是1还是0.

4. 容器所能容纳的位个数（size），相当于返回容器的长度。

5. 被置位的元素个数（count），返回所有被置为1的位的个数。

我们就一个个来分析：

首先，我们要定义一个byte数组，来保存这些数据。另外，我们也需要元素来保存里面所有位的个数和被置位的元素个数。因此，我们有如下的定义：

private byte[] bits;

private int size;

private int count = -1;

现在，假设我们要构造一个BitVector，我们就需要指定它的长度。它的一个构造函数可以构造成如下：

public BitVector(int n) {
    size = n;
    bits = new byte[(size >> 3) + 1];
}

这里，指定的参数n表示有多少个数字，相当于要置多少个位。由于我们要用byte来保存，所以能保存这么多数字的byte个数为n / 8 + 1。这种长度用移位的方式来表示则为(size >> 3) + 1。右移3位相当于除以8.

set

前面已经提到过，set某个位的元素，需要找到元素所在的byte，然后再设置byte对应的位。而n / 8得到的就是对应byte的索引，而n % 8得到的是对应byte中的位。这部分的代码实现如下：

public final void set(int bit) {
    bits[bit >> 3] |= 1 << (bit & 7);
    count = -1;
}

和我前面讨论的类似，这里不过是利用移位的方式实现同样的效果。前面bit >> 3相当于bit / 8。而bit & 7则相当于bit % 8。为什么bit & 7会相当于这个效果呢？在前面有一篇分析HashMap实现的文章里也讨论过这种手法。因为这里一个byte是8位，而8对应的二进制表示形式为1000，那么比它小1的7的二进制形式为0111。在将bit和7进行与运算的时候，所有大于第3位的高位都被置为0，之保留最低的3位。这样，最低的3位数字最小是0，最大是7.就相当于对数字8求模的运算效果。

clear

和前面的set方法相反，这里是需要将特定的位置为0。

public final void clear(int bit) {
    bits[bit >> 3] &= ~(1 << (bit & 7));
    count = -1;
}

get

get这部分的代码主要是判断这一位是否被置为1。我们将这个byte和对应位为1的数字求与运算，如果结果不是0，则表示它被置为1.

public final boolean get(int bit) {
    return (bits[bit >> 3] & (1 << (bit & 7))) != 0;
}

count

count方法的实现是一个比较精妙的手法。按照我们原来的理解，如果要计算里面所有被置为1的位的个数，我们需要遍历每个byte，然后求每个byte里面1的个数。一种想当然的办法就是每次和数字1移位的数字进行与运算，如果结果为0表示该位没有被置为1，否则表示该位有被置位。这种办法没问题，不过对于每个字节，都要这么走一轮的话，相当于前面运算量的8倍。如果我们可以优化一下的话，对于大数据来说还是有一定价值的。下面是另一种高效方法的实现，采用空间换时间的办法：