Java中的BitSet

最近看到ES在缓存filter的结果时用到了BitSet的数据结构，用一个bit来标识文档是否满足这个filter,利用bitset的or,and,andnot可以迅速地找到符合多个filter的文档的集合。顺带就看了看java中的BitSet的实现。

原理简介

1、 Java平台的BitSet用于存放一个位序列，如果要高效的存放一个位序列，就可以使用位集(BitSet)。由于位集将位包装在字节里，所以使用位集比使用Boolean对象的List更加高效和更加节省存储空间。

2、BitSet是位操作的对象，值只有0或1即false和true，内部维护了一个long数组，初始只有一个long，所以BitSet最小的size是64，当随着存储的元素越来越多，BitSet内部会动态扩充，一次扩充64位，最终内部是由N个long来存储。

private final static int ADDRESS_BITS_PER_WORD = 6;  
private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;  
private long[] words;  
  
private static int wordIndex(int bitIndex) {  
    return bitIndex >> ADDRESS_BITS_PER_WORD;  
}  
  
private void initWords(int nbits) {  
    words = new long[wordIndex(nbits-1) + 1];  
}  
  
public BitSet() {  
    initWords(BITS_PER_WORD);  
    ...  
}  
  
public BitSet(int nbits) {  
    ...  
    initWords(nbits);  
    ...  
}  
上面代码可以看出：long[] words这个数组是BitSet内部的关键实现，
如果用户在构造函数中输入一个nbits变量，
initWords方法会把这个数减1再右移6位加1，按照这个长度产生words数组的长度。 
如果是输入的28，那么words的长度是1， 
如果是输入的2^6       = 64，那么words的长度是1， 
如果是输入的2^6+1     = 65，那么words的长度是2， 
如果是输入的(2^6)*2   = 128，那么words的长度是2， 
如果是输入的(2^6)*2+1 = 129，那么words的长度是3， 
如果是输入的(2^6)*3   = 192，那么words的长度是3， 
如果是输入的(2^6)*3+1 = 193，那么words的长度是4， 
... 

到这里已经很清楚了，BitSet用long类型表示“位图”，因为一个long是64bit，
所以每个long表示64个数据，也就是说：数组中words中的第一个long表示0~63，
第二个long表示64~127，第三个long表示128~191 ... 

1）get函数，检测某个数是否被置位
public boolean get(int bitIndex) {  
    if (bitIndex < 0)  
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);  
...  
    int wordIndex = wordIndex(bitIndex);  
    return (wordIndex < wordsInUse)  
        && ((words[wordIndex] & (1L << bitIndex)) != 0);  
}  

说明： 
- wordsInUse变量主要用来控制long的容量，当set的数值过大时，
BitSet类可以扩充words数组的长度，这一点和很多集合类（例如ArrayList，HashMap）是相似的 
- 下面的语句值得注意： 
1L << bitIndex 
一般看到这条语句，会认为bitIndex如果超过64位，
高位会溢出并得到返回0，事实上这个1会重新循环到低位，也就是说: 
1L << 64 返回为1。 

2）size()方法：

/**
 * Returns the number of bits of space actually in use by this
 * <code>BitSet</code> to represent bit values.
 * The maximum element in the set is the size - 1st element.
 *
 * @return  the number of bits currently in this bit set.
 */
public int size() {
return words.length * BITS_PER_WORD;
}
这里也有一个常量，定义如下：

private final static int ADDRESS_BITS_PER_WORD = 6;
private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
很明显，BITS_PER_WORD = 64，这里很重要的一点就是，
如果使用size来返回BitSet数组的大小，其值一定是64的倍数，原因就在这里

3）与size相似的一个方法：length()源码如下：
/**
    * Returns the "logical size" of this <code>BitSet</code>: the index of
    * the highest set bit in the <code>BitSet</code> plus one. Returns zero
    * if the <code>BitSet</code> contains no set bits.
    *
    * @return  the logical size of this <code>BitSet</code>.
    * @since   1.2
    */
   public int length() {
       if (wordsInUse == 0)
           return 0;
 
       return BITS_PER_WORD * (wordsInUse - 1) +
       (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
   }

方法虽然短小，却比较难以理解，细细分析一下：根据注释，
这个方法法返回的是BitSet的逻辑大小，比如说你声明了一个129位的BitSet,
设置了第23，45，67位，那么其逻辑大小就是67，
也就是说逻辑大小其实是的是在你设置的所有位里面最高位的Index。

这里有一个方法，Long.numberOfLeadingZeros，网上没有很好的解释，做实验如下：

long test = 1;
System.out.println(Long.numberOfLeadingZeros(test<<3));
System.out.println(Long.numberOfLeadingZeros(test<<40));
System.out.println(Long.numberOfLeadingZeros(test<<40 | test<<4));
打印结果如下：

60
23
23

也就是说，这个方法是输出一个64位二进制字符串前面0的个数的。

3、默认情况下，BitSet的所有位都是false即0。
4、在没有外部同步的情况下，多个线程操作一个BitSet是不安全的。
一个1GB的空间，有8102410241024 = 8.5810^9bit，也就是1GB的空间可以表示85亿多个数。

应用场景：

1、统计一组大数据中没有出现过的数；
将这组数据映射到BitSet，然后遍历BitSet，对应位为0的数表示没有出现过的数据。
2、对大数据进行排序；
将数据映射到BitSet，遍历BitSet得到的就是有序数据。
3、 在内存对大数据进行压缩存储等等。
一个GB的内存空间可以存储85亿多个数，可以有效实现数据的压缩存储，节省内存空间开销。

1. BitSet使用的例子

BitSet bits1 = new BitSet(16);
BitSet bits2 = new BitSet(16);
bits1.set(3);
bits1.set(5);
bits2.set(5);
bits2.set(6);
bits1.or(bits2);
System.out.println(bits1);
输出的结果为{3,5,6}，也就是说满足bits1和bits2的文档都被返回。

BitSet bits1 = new BitSet(16);
BitSet bits2 = new BitSet(16);
bits1.set(3);
bits1.set(5);
bits2.set(5);
bits2.set(6);
bits1.and(bits2);
System.out.println(bits1);
输出的结果为{5}，只有同时满足bits1和bits2的文档才会被返回。
2. BitSet的内部实现
BitSet内部用long数组实现了bit的向量

/**
 * The internal field corresponding to the serialField "bits".
 */
private long[] words;
并动态扩展数组的长度

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) {
        // Allocate larger of doubled size or required size
        int request = Math.max(2 * words.length, wordsRequired);
        words = Arrays.copyOf(words, request);
        sizeIsSticky = false;
    }
}
当数组的长度不够时，会将生成一个长度为当前长度2倍的数组，然后将老数组中的内容拷贝到新数组中。
将某一个bit置为1,会先定位到这个bit所在的word，也就是数组中的一个long,然后对这个word进行位的或操作。

public void set(int bitIndex) {
    int wordIndex = wordIndex(bitIndex);
    expandTo(wordIndex);
 
    words[wordIndex] |= (1L << bitIndex); // Restores invariants
 
    checkInvariants();
}

3.BitSet中为什么使用long数组而不是int数组存储bit
当对单个bit进行操作时，两种存储方式不会有太大的区别：首先计算bit所在的word，然后对word中对应的bit进行操作。
当同时对多个bit进行操作时，long数组存储方式可以带来较大的新能提升。例如我们进行BitSet中的and, or, xor操作时，要对整个bitset中的bit都进行操作，需要依次读出bitset中所有的word，如果是long数组存储，我们可以每次读入64个bit,而int数组存储时，只能每次读入32个bit。另外我们在查找bitset中下一个置为1的bit时,word首先会和0进行比较，如果word的值为0，则表示该word中没有为1的bit，可以忽略这个word，如果是long数组存储，可以一次跳过64个bit，如果是int数组存储时，一次只能跳过32个bit。减少循环次数，提高性能。

【本文转自：
Java中的BitSet
Java中的位集】