前言

java.util.BitSet 是 JDK 中对 Bitmap 算法的实现类，使用了 long[] 来存储二进制数据。BitSet 提供了 添加、删除、获取数据 以及 与、或、异或 等操作。

下面就来了解一下其中的奥秘吧！

存储结构

BitSet 使用一个 long[] 来存储数据，long 类型占 8 字节，64位。数组中每个元素可以存储 64 个数据，数组中数据的存储顺序 从左到右，从低位到高位。

比如下图中的 words 容量为 4，words[0]从低位到高位分别表示数据 0~63是否存在，words[1] 的低位到高位分别表示数据 64~127 是否存在，以此类推。其中 words[1] = 8，对应的二进制第 8 位为 1，说明此时 BitSet 中存储了一个数据 {67}。

图1

在 BitSet 中定义的一些属性如下：

  • long[] words：数据的存储结构
  • int wordsInUse = 0：表示数组中最多使用的元素个数，也就是最后一个不为 0 的元素的索引加 1；比如上图中，数组长度为 4，但是最后一个不为 0 的元素是 1，所以 wordsInUse = 2

还定义了一些常量，它们的含义如下：

// 每个 word 用 6 个地址位来表示，2^6 = 64
private static final int ADDRESS_BITS_PER_WORD = 6;
// 每个 word 所占的位数，即 64
private static final int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
// ?
private static final int BIT_INDEX_MASK = BITS_PER_WORD - 1;
// ?
private static final long WORD_MASK = 0xffffffffffffffffL;
复制代码

初始化

创建一个 BitSet 对象时，默认 words 的长度为 1，并且 words[0] = 0。当然也可以用户给定一个具体的容量大小，如下代码

/**
* BitSet.class
* 创建一个能存储给定数据索引的 BitSet
*/
public BitSet(int nbits) {
    // 参数合法性判断
    if (nbits < 0)
        throw new NegativeArraySizeException("nbits < 0: " + nbits);
    // 调用 initWords 方法初始化
    initWords(nbits);
    sizeIsSticky = true;
}

private void initWords(int nbits) {
    words = new long[wordIndex(nbits-1) + 1];
}
复制代码

initWords() 方法非常简单，就是 new 一个数组。其中调用了 wordIndex() 方法，该方法的作用是 得到所给 bit 索引（数据）对应在 words 中的下标。

具体的方法是：bitIndex / 64 得到对应的数组下标（也就是右移 6 位）， bitIndex % 64 得到在该元素的第几个二进制位。

// 得到 bitIndex 对应的 words 下标
private static int wordIndex(int bitIndex) {
    return bitIndex >> ADDRESS_BITS_PER_WORD;
}
复制代码

添加数据

set(bitIndex) 的源码如下：

// BitSet.class
public void set(int bitIndex) {
    // 参数合法性检验
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    // 得到对应的数组下标
    int wordIndex = wordIndex(bitIndex);
    // 是否要扩容
    expandTo(wordIndex);
    // 修改数据
    words[wordIndex] |= (1L << bitIndex); 
    // 参数检查
    checkInvariants();
}
复制代码

给定一个索引 bitIndex ，将该数对应的二进制位置为 1。首先调用 wordIndex() 得到该索引对应在 words 中的下标（记为 wordIndex）。

然后调用 expandTo(int) 方法，该方法的作用是 保证 BitSet 的空间够用，即如果空间不够，就进行扩容。

private void expandTo(int wordIndex) {
    int wordsRequired = wordIndex+1;
    if (wordsInUse < wordsRequired) {
        ensureCapacity(wordsRequired);
        wordsInUse = wordsRequired;
    }
}
复制代码

之前已经提到， wordsInUse 一定是 小于等于 数组的长度，所以只有在新添加位置比 wordsInUse 大时（即 wordsInUse < wordsRequired），才有可能进行扩容。

扩容的逻辑是：如果需要的长度大于数组的两倍，则扩容到需要的长度。否则，扩容位数组的两倍。

最后就是修改对应位的值。深入解析 Bitmap 算法（一）中提到，修改为 1 可以使用 bitmap |= (1 << bitIndex) 操作。但是现在我们的操作单位不是一串连续的二进制数，而是一个 64 位的长整型（words[wordIndex]），最多只能左移 64 位，这种操作方法还可以使用吗？

答案是可以的。计算机底层的移位操作，如果移动的位数超过了该类型的最大位数，那么编译器会对移动的位数取模。对 long 类型来说，移动 65位，实际上只移动了 1 位。

而前面又提到，bitIndex % 64 表示索引在对应数组元素中的第几个二进制位。所有可以方向大胆的直接使用左移操作，修改值为 1。

1L << bitIndex <=> 1L << bitIndex % 64
复制代码

比如 BitSet 的 words 为 [0,0,8,0]，现在要 set(66)，对应数组下标为 1，不需要扩容，最终的结果为 words=[0,0,12,0]。

image.png

清除数据

/**
* BitSet.class
* clear 核心代码
*/
public void clear(int bitIndex) {
    //...
    int wordIndex = wordIndex(bitIndex);
    // 如果 wordIndex >= wordsInUse，说明该索引要么不存在，要么一定是 0 ，直接返回即可
    if (wordIndex >= wordsInUse)
        return;
    words[wordIndex] &= ~(1L << bitIndex);
    recalculateWordsInUse();
    //...
}
复制代码

给定一个数据索引 bitIndex，首先调用 wordIndex() 方法得到对应的数组下标。直接使用如下公式将对应位修改为 0。

words[wordIndex] &= ~(1L << bitIndex);
复制代码

修改完可能会引起 wordsInUse 的变化，所以还要调用 recalculateWordsInUse() 重新计算 wordsInUse：从后往前遍历直到遇到 words[i] != 0，修改 wordsInUse = i+1。

private void recalculateWordsInUse() {
    int i;
    for (i = wordsInUse-1; i >= 0; i--)
        if (words[i] != 0)
            break;

    wordsInUse = i+1; // The new logical size
}
复制代码

获取数据

/**
* BitSet.class
* get() 核心代码
*/
public boolean get(int bitIndex) {
    // ...
    int wordIndex = wordIndex(bitIndex);
    return (wordIndex < wordsInUse) && ((words[wordIndex] & (1L << bitIndex)) != 0);
}
复制代码

get(int) 方法判断给定的数据索引 bitIndex 是否存在，也就是对应二进制位是否为 1。

首先调用 wordIndex() 方法得到对应的数组下标。然后使用如下公式判断是否存在：

words[wordIndex] & (1L << bitIndex)) != 0
复制代码

由于 1L << bitIndex 的结果只有索引对应的二进制位是 1，其他都是 0，所以按位与操作后，其他位的结果都是 0，最终的结果是否为 0 取决于对应二进制位原来的值。

集合操作

与操作

public void and(BitSet set) {
    if (this == set)
        return;
    while (wordsInUse > set.wordsInUse)
        words[--wordsInUse] = 0;
    for (int i = 0; i < wordsInUse; i++)
        words[i] &= set.words[i];

    recalculateWordsInUse();
    checkInvariants();
}
复制代码

两个 BitSet 做与操作，只需要对 共同的部分 进行按位与操作即可，可以利用两个 BitSet 的 wordsInUse 比较。

与操作可能会导致某些元素变成 0 ，所以要重新计算 wordsInUse。

或操作

/**
* BitSet.class
*/
public void or(BitSet set) {
    if (this == set)
        return;
    // 获取公共部分范围
    int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
    // 必要时扩容
    if (wordsInUse < set.wordsInUse) {
        ensureCapacity(set.wordsInUse);
        wordsInUse = set.wordsInUse;
    }
    // 公共部分按位或
    for (int i = 0; i < wordsInCommon; i++)
        words[i] |= set.words[i];
    // 复制剩余元素
    if (wordsInCommon < set.wordsInUse)
        System.arraycopy(set.words, wordsInCommon,words, wordsInCommon,wordsInUse - wordsInCommon);
}
复制代码

相对而言，或操作更为复杂。但必要的核心的操作是将公共的部分（0 ~ wordsInCommon）先进行按位或。

  • 如果 wordsInUse >= set.wordsInUse ，这种情况比较简单，不需要做其他额外的操作

image.png

  • 如果 wordsInUse < set.wordsInUse，这种情况下，首先要判断是否需要扩容，然后公共部分（下图红色部分）按位或，最后将 set 中剩余的元素（下图绿色部分）直接复制到 this 中。

image.png

异或操作

/**
* BitSet.class
*/
public void xor(BitSet set) {
    // 获取公共部分范围
    int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
    // 必要时扩容
    if (wordsInUse < set.wordsInUse) {
        ensureCapacity(set.wordsInUse);
        wordsInUse = set.wordsInUse;
    }
    // 公共部分异或操作
    for (int i = 0; i < wordsInCommon; i++)
        words[i] ^= set.words[i];
    // 复制剩余元素
    if (wordsInCommon < set.wordsInUse)
        System.arraycopy(set.words, wordsInCommon,
                         words, wordsInCommon,
                         set.wordsInUse - wordsInCommon);
    // 重新计算 wordsInUse
    recalculateWordsInUse();
    checkInvariants();
}
复制代码

异或操作（不同输出 1，相同输出 0）的思路和或操作一致。但是最后还要多一步，重新计算 wordsInUse。这是因为 两个不为 0 的数异或的结果可能是 0。