最近看到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亿多个数，可以有效实现数据的压缩存储，节省内存空间开销。
- 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的文档才会被返回。
// 使用BitSet进行排序
private static String sortNums(int[] nums){
long start = System.currentTimeMillis();
System.out.println("开始排序");
int len = nums.length;
StringBuilder sb = new StringBuilder();
BitSet bitSet = new BitSet(len);
bitSet.set(0, len, false);
for(int i=0;i<len;i++){
bitSet.set(nums[i], true);
}
for(int i=0;i<len;i++){
if(bitSet.get(i)){
sb.append(i).append(",");
}
}
return sb.toString();
}
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中的位集】
