Java1.8-BitSet源码分析

概述

  首先，我们要了解一种数据结构，就是位图。位图就是操作位（bit）的一种集合。Java中操作数据的最小单位是字节（byte），并没有直接提供操作bit的基本数据类型。但是我们如果用到的时候可以自己通过位运算进行封装，当然也可以使用我们今天要学习的BitSet类来进行操作。
  其次，就是BitSet不属于集合框架，虽然它也叫Set，也位于java.util包下，但看它的源码，它和Set，List，Collection，Map这些没什么关系。但既然叫Set了，我们就拿过来一起分析。
  其基本原理是使用一个数的二进制的一位来表示一个数据是否出现过，1表示出现过，0表示没出现过。

下面，我们来看一下这个类的实现。首先，先看下官方文档：
https://docs.oracle.com/javase/8/docs/api/java/util/BitSet.html

继承体系及属性

public class BitSet implements Cloneable, java.io.Serializable {

    // 保存bit的数组
    private long[] words;
    // 表示在数组words中已经使用的数的个数
    private transient int wordsInUse = 0;
    
    // 保存bit的words数组的位数是否由用户指定
    private transient boolean sizeIsSticky = false;
    
    private final static int ADDRESS_BITS_PER_WORD = 6;
    private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
    private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;

    /* Used to shift left or right for a partial word mask */
    private static final long WORD_MASK = 0xffffffffffffffffL;
}

我们简单分析一下BitSet中的属性：

1. words我们可以看出BitSet是通过一个long类型的数组来进行存储数据的。而wordInUse表示words数组中long数字已经使用的个数，这个变量对BitSet内部维护，用于判断检查，扩容等相关的参数。
2. 变量sizeIsSticky表示我们在指定words数组的大小时，是否是由用户来指定的，还是采用默认的。
3. ADDRESS_BITS_PER_WORD常量，指的是long类型的地址位数，也就是进行操作时位移的个数。因为JDK文档中有规定，对long类型进行位移的时候，只有低6位有效。因为在Java中，long类型占用8个字节，64位，对应二进制的实际有效位数就是6；
4. BITS_PER_WORD和上面那个常量是对应的，表示的是位移的数字大小。对long类型而言，位移最大数字是64，位移65和位移1是一样的。
5. WORD_MASK这个常量，被称为掩码，是用于位移时进行运算的，这个值就是-1，二进制的话全都是1，在EnumSet中进行操作时我们就说过。

构造方法及关联的方法

/**
 * 默认构造方法，默认初始化数组容量为1
 */
public BitSet() {
    initWords(BITS_PER_WORD);
    sizeIsSticky = false;
}

/**
 * 根据传入的参数初始化数组容量
 */
public BitSet(int nbits) {
    // 位数不能是负数，但可以是0
    if (nbits < 0)
        throw new NegativeArraySizeException("nbits < 0: " + nbits);

    initWords(nbits);
    sizeIsSticky = true;
}

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

private static int wordIndex(int bitIndex) {
    return bitIndex >> ADDRESS_BITS_PER_WORD;
}

从上面方法来看，默认构造方法下，long数组容量是1，而我们也可以指定位数来初始化数组的容量。

set方法

我们在操作BitSet的时候，这个方法用的比较多。set方法就是设置对应位索引处的值为1，比如我们调用SetBit的set(10)，通俗的将，就是将long类型的变量的二进制位的第11位设置为1（从低位开始）。set有4个重载方法，我们先来看单个参数的方法。

public void set(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    // 根据传入的位索引定位到long数组中哪一个元素
    int wordIndex = wordIndex(bitIndex);
    // 扩容操作
    expandTo(wordIndex);

    words[wordIndex] |= (1L << bitIndex); // Restores invariants
    // 使用断言校验wordsInUse变量
    checkInvariants();
}

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

private void ensureCapacity(int wordsRequired) {
    // 如果原数组长度小于实际数组所需容量，扩容
    if (words.length < wordsRequired) {
        // 扩容2倍或者实际所需容量，取两者之间的最大值
        int request = Math.max(2 * words.length, wordsRequired);
        words = Arrays.copyOf(words, request);
        sizeIsSticky = false;
    }
}

大致实现步骤如下：

1. 判断传入的参数位索引是否小于0；
2. 根据传入的位索引定位到long数组中哪一个元素；
3. 根据wordsInUse变量判断long数组中实际所使用的元素个数是否小于实际所需要的个数；
4. 如果是，再判断数组的长度是否小于实际所需要的数组容量；
5. 如果小于，比较扩容两倍后的容量与实际所需要的容量，取两者之间的较大者进行扩容；
6. 进行位与运算，将定位到的long数组中的元素对应位置上的位设置为1；
7. 断言校验wordsInUse变量，所有public方法都会调用。

其中expandTo和ensureCapacity方法是用来确保数组的容量能够满足实际所需的容量，如果不满足，则进行扩容来满足。
我们来看一下另外几个set方法：

/**
 * 将指定位索引处的值设置为指定的值
 * 如果value是true，设置为1，如果是false，设置为0
 */
public void set(int bitIndex, boolean value) {
    if (value)
        set(bitIndex);
    else
        // clear方法来清除对应索引处的值，也就是设置为0
        clear(bitIndex);
}

下面这个set一段范围的方法很精妙：

/**
 * 设置指定范围内的位索引
 */
public void set(int fromIndex, int toIndex) {
    // 校验开始索引和结束索引是否合法，不合法抛异常
    checkRange(fromIndex, toIndex);
    // 如果两个索引相同，直接结束程序流程，不进行任何操作
    if (fromIndex == toIndex)
        return;

    // 定位索引所在数组中的位置
    int startWordIndex = wordIndex(fromIndex);
    int endWordIndex   = wordIndex(toIndex - 1);
    // 确认是否扩容
    expandTo(endWordIndex);
    // 计算掩码
    long firstWordMask = WORD_MASK << fromIndex;
    long lastWordMask  = WORD_MASK >>> -toIndex;
    // 如果定位的索引在数组的同一个元素中
    if (startWordIndex == endWordIndex) {
        // 先对firstWordMask和lastWordMask进行与运算，再进行位或运算(补码运算)
        words[startWordIndex] |= (firstWordMask & lastWordMask);
    } else {
        // 如果不在数组的同一个元素中
        // 对第一个元素进行位于操作，将对应索引的位设置为1
        words[startWordIndex] |= firstWordMask;

        // 如果元素有多个，全部置为1
        for (int i = startWordIndex+1; i < endWordIndex; i++)
            words[i] = WORD_MASK;

        // 对最后一个元素也进行位于操作，将对应索引的位设置为1
        words[endWordIndex] |= lastWordMask;
    }

    checkInvariants();
}

其他的set方法都类似，就不一一说了。

get方法

public boolean get(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    checkInvariants();
    // 定位到具体的long类型
    int wordIndex = wordIndex(bitIndex);
    // 对应索引位上进行位与操作，判断是否等于0来返回对应true和false
    return (wordIndex < wordsInUse)
        && ((words[wordIndex] & (1L << bitIndex)) != 0);
}

flip方法

顾名思义，该方法是反转某一个索引位的，就是将1置为0，将0变为1的操作。

public void flip(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    int wordIndex = wordIndex(bitIndex);
    expandTo(wordIndex);
    // 通过位异或操作进行
    words[wordIndex] ^= (1L << bitIndex);

    recalculateWordsInUse();
    checkInvariants();
}

nextSetBit方法

public int nextSetBit(int fromIndex) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

    checkInvariants();
    // 定位索引
    int u = wordIndex(fromIndex);
    if (u >= wordsInUse)
        return -1;
    // 获取word的实际值
    long word = words[u] & (WORD_MASK << fromIndex);

    while (true) {
        if (word != 0)
            return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
        if (++u == wordsInUse)
            return -1;
        word = words[u];
    }
}

1. 该方法获取的是在指定索引处或之后第一个值为1的值。比如我set了2，又set了8，那么nextSetBit(0)将返回2，nextSetBit(1)和nextSetBit(2)也将返回2，而nextSetBit(3)则返回的是8。因为返回的是指定索引处，如果指定索引处获取不到，就返回最近的下一个位为1的值。
2. 通常该方法用于遍历BitSet，使用方法如下：

for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
    if (i == Integer.MAX_VALUE) {
        break;
    }
}

size，length，cardinality方法

public int size() {
    return words.length * BITS_PER_WORD;
}

public int length() {
    if (wordsInUse == 0)
        return 0;

    return BITS_PER_WORD * (wordsInUse - 1) +
        (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
}

public int cardinality() {
    int sum = 0;
    for (int i = 0; i < wordsInUse; i++)
        sum += Long.bitCount(words[i]);
    return sum;
}

我们可以看到：

1. BitSet的size方法直接返回了数组大小与64的乘积，这也说明了这个方法的返回值将都是64的倍数。
2. 而length()方法返回的是BitSet的逻辑大小，比如默认情况下，我们set了一个2，又set了一个10，那么这个结果返回的就是10+1；
3. cardinality方法返回的是BitSet中实际元素的个数。比如我们set了2，又set了10，那么返回的实际个数就是2个。

BitSet中还有一些其他的方法，比如nextSetBit，nextClearBit，previousSetBit等，不过这些方法只要理解了位运算，都是很简单的，就不一一列举了。

使用场景

由于BitSet特殊的0-1操作，所以非常适合做那些开-关，是-不是类似的操作，例如常见的类似的面试题：

1. 现在有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来
2. 统计40亿个数据中没有出现的数据，将40亿个不同数据进行排序等。

总结

1. BitSet处理的只有1和0，只能处理没有重复的数据，当然也可以借助这一点处理一些特殊的问题；
2. BitSet同样不是线程安全的。我们如果有需要线程安全的地方，注意要手动实现线程安全。
3. BitSet可以动态扩容，但同样的也没有动态减少，所以注意可能会出现的OutOfMemory。

举例

最后，我们来举个简单的例子：对没有重复的数字进行排序。

/**
 * 进行数字排序
 */
public static void sortArray() {
    int[] array = new int[] { 423, 700, 9999, 2323, 356, 6400, 1,2,3,2,2,2,2 };
    BitSet bitSet = new BitSet(2 << 13);
    // 虽然可以自动扩容，但尽量在构造时指定估算大小，
    // 我们要看一下数组中的最大值，然后指定大致的容量，默认为64
    System.out.println("BitSet size: " + bitSet.size());

    for (int i = 0; i < array.length; i++) {
        bitSet.set(array[i]);
    }
    //剔除重复数字后的元素个数
    int bitLen=bitSet.cardinality();
    System.out.println("要排序的数组容量：" + array.length);
    System.out.println("剔除重复数字后的元素个数：" + bitLen);

    //进行排序，即把bit为true的元素复制到另一个数组
    int[] orderedArray = new int[bitLen];
    int k = 0;
    for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
        orderedArray[k++] = i;
    }

    System.out.println("After ordering: ");
    for (int i = 0; i < bitLen; i++) {
        System.out.print(orderedArray[i] + "\t");
    }
    System.out.println("\n通过迭代器获取排序后的元素：");
    //或直接迭代BitSet中bit为true的元素
    for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
        System.out.print(i+"\t");
    }
    System.out.println("\n---------------------------");
}

打印输出：

BitSet size: 16384
要排序的数组容量：13
剔除重复数字后的元素个数：9
After ordering: 
1   2   3   356 423 700 2323    6400    9999    
通过迭代器获取排序后的元素：
1   2   3   356 423 700 2323    6400    9999    
---------------------------

如果要查看其它例子，可以参考：BitSet的使用场景及简单示例