BitSet实现原理及源码解析

BitSet的结构原理

BitSet, 是Java对位集合抽象出的一种数据结构。它的内部维护了一个long数组,数组里的每一个元素用64位的二进制来表示，所以每一位只用来存储0，1值。
BitSet只知道给定的数字是否存在，并不能还原数字本身; 所以它一般用来做精确去重，比如布隆过滤器也是基于位数组来实现的。它的数据结构可以用下图来表示：

BitSet的words数据结构

上图整体表示的是一个long型的数组，我们命名为 words :

最上面的数字表示数组的索引,0,1,2,.....,n, 我们命名为wordIndex
中间一层是数组的long型元素, 用64位的二进制来表示
最下面的数字是64位二进制位索引，我们命名为 bitIndex

那么,从上图我们怎么知道BitSet是怎么工作的呢？我们举例来说明(我很喜欢举栗子), 假如我现在要把 65这个值存入BitSet中，并且设置成true。

我们需要算出65在words数组中的 wordIndex，也就是 "65" 应该放在数组中的第几个64位的二进制中; 怎么算呢？用将要存入的值除以64：

int wordIndex = 65 / 64 (值为1)

算出wordIndex为1,那么我们应该把1对应的64位二进制的某一位设置成 1(true)

将哪一位bit设置成 1(true)呢？我们需要算出bitIndex,怎么算？用将要存入的值对64取模：

int bitIndex = 65 % 64 (值为1)

算出bitIndex 为1,那么我们应该把第1位bit(index从0开始)设置成1。

最终我们得出BitSet的内部数据结构如下图:

我们现在不防把words里的二进制转换成long来看下是什么值：

value.png

从上图看出，wordIndex为0的二进制转换成long为0; wordIndex为1的二进制转换成long为2

long words = {0, 2}

JAVA对BitSet的实现

有了上面的原理，现在我们可以来看Java对BitSet的代码实现了，总得来说，就是对上面原理怎么代码来写，我们还是以65这个数字来讲解，首先看代码:

    BitSet bitSet = new BitSet();
    bitSet.set(65);
    bitSet.clear(65);
    // bit的大小不会变
    System.out.println(bitSet.size());

// 输出 
128

BitSet::BitSet()

首先是BitSet的构造方法，先初始化words数组，默认size为1。从宏观上来讲，这里的初始化是设置wordds数组的大小，从微观上(二进制)来讲，这里的初始化是把words里的long二进制化，并全默认为0。

private final static int ADDRESS_BITS_PER_WORD = 6;
// 1 * 64 = 64
private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD; // 64
public BitSet() {
    //初始化words数组大小
    initWords(BITS_PER_WORD);
    sizeIsSticky = false;
}
private void initWords(int nbits) {
    words = new long[wordIndex(nbits-1) + 1];
}
//算出wordIndex，数组words的下标索引,直接用将要插入的值除以64
private static int wordIndex(int bitIndex) {
    // bitIndex / 64
    return bitIndex >> ADDRESS_BITS_PER_WORD;
}

BitSet::set(int)

接着是 set方法，就如前面所说的，想要插入新值，要先算出wordIndex，然后确保当前的words容量是否够用，最后把对就的bitIndex设置成1

public void set(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    // 得到wordIndex
    int wordIndex = wordIndex(bitIndex);
    // 如果words容量不够,需要扩容
    expandTo(wordIndex);
    // 把1L左移 bitIndex位，再与对应的数组里的二进制取或，目的是将对应的bitIndex设置成1
    words[wordIndex] |= (1L << bitIndex); // Restores invariants
    
    checkInvariants();
}

private void expandTo(int wordIndex) {
    // 需要的words大小为索引加 1,
    int wordsRequired = wordIndex+1;
    // wordsInUse默认为0，代表当前的words的逻辑大小
    if (wordsInUse < wordsRequired) {
        // 扩容
        ensureCapacity(wordsRequired);
        wordsInUse = wordsRequired;
    }
}

private void ensureCapacity(int wordsRequired) {
    // 如果当前worfds的长度小于需要的长度
    if (words.length < wordsRequired) {
        // Allocate larger of doubled size or required size
        // 分配策略是,2倍当前的size与 wordsRequired的最大值
        int request = Math.max(2 * words.length, wordsRequired);
        // 数组扩容
        words = Arrays.copyOf(words, request);
        sizeIsSticky = false;
    }
}

上面的代码比较难理解的是words[wordIndex] |= (1L << bitIndex);。这句代码就如我上面提到的对 64取模得到bitIndex(这里的bitIndex并非方法参数里的bitIndex，可以理解为分片后的bitIndex)，然后把对应的bitIndex设置成1(true) 这也是最重要的逻辑。那么它是怎么把bitIndex设置成1(true)的呢？
先看1L<<bitIndex:

    System.out.println(Long.toBinaryString(1L<<0));
    System.out.println(Long.toBinaryString(1L<<1));
    System.out.println(Long.toBinaryString(1L<<2));
    System.out.println(Long.toBinaryString(1L<<3));
    System.out.println(Long.toBinaryString(1L<<4));
    System.out.println(Long.toBinaryString(1L<<5));
    System.out.println(Long.toBinaryString(1L<<6));
    System.out.println(Long.toBinaryString(1L<<7));
    System.out.println("........");
    System.out.println(Long.toBinaryString(1L<<63));
    System.out.println(Long.toBinaryString(1L<<64));
    System.out.println(Long.toBinaryString(1L<<65));

//------------------------
// 输出如下:
1L<<0 => 1
1L<<1 => 10
1L<<2 => 100
1L<<3 => 1000
1L<<4 => 10000
1L<<5 => 100000
1L<<6 => 1000000
1L<<7 => 10000000
........
1L<<63 => 1000000000000000000000000000000000000000000000000000000000000000
1L<<64 => 1
1L<<65 => 10
1L<<66 => 100
1L<<67 => 1000
........
1L<<127 => 1000000000000000000000000000000000000000000000000000000000000000
1L<<128 => 1

看出什么规律了吗？1 左移多少位，对应了1的位置, 左移溢出时，从头开始，64位一个轮回，这不就是前面提到的 value % 64吗？这样就算出了bitIndex。
现在有了wordIndex和bitIndex，那怎么把bitIndex设置成1(true)呢？words[wordIndex] = words[wordIndex] | bitIndex 就是把bitIndex设置成1，分别把words[wordIndex] = 0(以65为例,原来的值为0的)，与bitIndex=1(1 << 65 = 1) 分别转换成64位二进制，做或操作试试：

0000000000000000000000000000000000000000000000000000000000000000 
| (或操作)
0000000000000000000000000000000000000000000000000000000000000010 
= (等于)
0000000000000000000000000000000000000000000000000000000000000010

BitSet::clear(int)

有插入，肯定也要有去除(设置成0 false)，BitSet的clear和插入一样，也需要得到wordIndex和bitIndex。

public void clear(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    // 得到wordIndex，如果大于当前的words的大小，则不需要remove(压根就没有插入过)
    int wordIndex = wordIndex(bitIndex);
    if (wordIndex >= wordsInUse)
        return;
    // 得到bitIndex后，需要对它取反再后原来的word做与操作，因为要确保原来的值(已经设置成1的值)不被抹去(1 & 1 = 1)。
    words[wordIndex] &= ~(1L << bitIndex);
    // 从words的最后一个元素开始判断，重新设置wordsInUse
    recalculateWordsInUse();
    checkInvariants();
}

private void recalculateWordsInUse() {
    // Traverse the bitset until a used word is found
    int i;
    for (i = wordsInUse-1; i >= 0; i--)
        // 如果最后一个元素不为0，则直接跳出循环。
        if (words[i] != 0)
            break;
    // size = index + 1(index从0开始)
    wordsInUse = i+1; // The new logical size
}

与插入不同的是，需要对算出的bitIndex取反，再与words[wordIndex]做与(&)操作。具体分析，可以参照插入时，自己做与操作看看，我就不必多说了。值得一提的是，当clear之后，bitsize不会变，当扩容之后，做clear操作，bitsize还是扩容后的大小，比如上面的 words大小为2，那么就有2个 64位的 long，那么大小还是128。

总结

以上就是我对BitSet的实现原理的分析，如果有什么不对的地方还望指出。BitSet(bitmap)的使用场景还是蛮多的，常见的如：对海量数据的查找，去重，排序(因为里面的数据本身就是有序的)等。相比于其它集合，BitSet采用的是纯bit实现，占用更少的空间；在我最近的工作中，我就在Flink中使用了BitSet对海量数据的累计去重，以每天每小时的结构滚动输出到mysql。全篇完（：