Bitset分析.doc

JAVA源码分析之BitSet1.BitSet概述BitSet实现了一种比特位的向量，能够自动增长，用途很广泛。如在bloom filter中会用到BitSet来标识某一位是否置位等。初始情况下所有位都为false。主要的变量如下表中所示，下面分析的时候会详细介绍这些变量的用处。首先可以注意到用来存储位向量的数组words为long类型，也就是说每一个值可以保存64位信息，所以ADDRESS_BITS_PER_WORD=6。变量wordsInUse用来表示当前有多少个words在用，初始为0，它的值在每次扩容words数组后更新，第一次调用set(int index)方法时一定会更新wordsInUse变量，因为初始值0会小于需要的words数目。这里的word都是long类型，即64位的。此外，变量sizeInSticky表示用户是否指定了words的数目。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;/* * The internal field corresponding to the serialField bits. */private long words;/* * The number of words in the logical size of this BitSet. */private transient int wordsInUse = 0;/* * Whether the size of words is user-specified. If so, we assume the user * knows what hes doing and try harder to preserve it. */private transient boolean sizeIsSticky = false;2.方法分析BitSet()public BitSet() initWords(BITS_PER_WORD); /BITS_PER_WORD=16=64sizeIsSticky = false;public BitSet(int nbits) / nbits cant be negative; size 0 is OKif (nbits 0)throw new NegativeArraySizeException(nbits 6=0, 646=1)*/private static int wordIndex(int bitIndex) / ADDRESS_BITS_PER_WORD=6return bitIndex ADDRESS_BITS_PER_WORD;由构造方法代码可知，当我们不指定比特数目时，则默认会用64来初始化BitSet，即words数组大小为1，并设置sizeIsSticky为false。如果指定了比特数目，则用指定的数目来创建words数组，并设置sizeInSticky为true。set(int index):设置指定的第index位为true（其实就是置为1）。public void set(int bitIndex) /判断bitIndex不能小于0if (bitIndex 0)throw new IndexOutOfBoundsException(bitIndex 0: + bitIndex); /计算这一位在words数组中的位置int wordIndex = wordIndex(bitIndex); /判断是否需要扩展words数组大小expandTo(wordIndex); wordswordIndex |= (1L bitIndex); / Restores invariantscheckInvariants();/检查一些条件是否满足。private void expandTo(int wordIndex) int wordsRequired = wordIndex + 1;if (wordsInUse wordsRequired) /如果当前使用的words数目小于需要的words数目，则扩展words数组至需要的大小，并设置wordsInUse值为当前需要的words数目。ensureCapacity(wordsRequired);wordsInUse = wordsRequired;private void ensureCapacity(int wordsRequired) if (words.length wordsRequired) / Allocate larger of doubled size or required sizeint request = Math.max(2 * words.length, wordsRequired);words = Arrays.copyOf(words, request);sizeIsSticky = false;首先求出需要设置的位在words数组中的位置，然后判断是否需要增加words数组大小。如果需要增大words数组，则调用ensureCapacity方法实现，该方法设置新数组大小为words数组原来大小的2倍和wordsRequired的较大值，创建新数组，并将原来words数组的元素全部拷贝到新创建数组中，更新words为新数组的引用。同时会设置sizeIsSticky = false。否则，直接将index位置位，即通过这一行代码实现置位：wordswordIndex |= (1L bitIndex);其中wordIndex为index在words数组中的位置，后面通过按位或操作对bitIndex位置位。需要注意的是java中的移位操作会模除位数，也就是说，long类型的移位会模除64。例如对long类型的值左移65位，实际是左移了65%64=1位。这里可以通过一个例子来加深印象，比如如下代码：BitSet bs = new BitSet(); /1bs.set(12); /2bs.set(63); /3bs.set(64); /4第一行创建一个BitSet对象，此时调用无参数的构造函数，初始化比特位为64，也就是说words数组初始大小为1。接着调用set(12)设置第12位为1，在执行set方法的过程中，会调用expandTo()方法来判断是否需要扩容，最终确定是否扩容是由ensureCapacity方法决定的。由于第2行代码是第一次调用set方法，此时wordsInUse=0 wordsInUse=1，所以会扩容，同时设置wordsInUse=2，新的words数组大小为2。get(int index):若index位被置位，则返回true，否则返回false。public boolean get(int bitIndex) if (bitIndex 0)throw new IndexOutOfBoundsException(bitIndex 0: + bitIndex);checkInvariants();int wordIndex = wordIndex(bitIndex);return (wordIndex wordsInUse)& (wordswordIndex & (1L bitIndex) != 0);该方法首先得到获取位在words数组中的索引，然后返回相应值的对应的位的是否置位情况，主要通过wordswordIndex & (1L wordsInUse,所以get方法的return语句的后半部分都不会执行了。BitSet bs = new BitSet();System.out.println(bs.get(126);Clear(int index)：清除index位的置位标志。public void clear(int bitIndex) if (bitIndex 0)throw new IndexOutOfBoundsException(bitIndex = wordsInUse)return;wordswordIndex &= (1L = 0; i-)if (wordsi != 0)break;wordsInUse = i + 1; / The new logical size该方法为set方法的逆过程，即先找到index位在words数组中的位置wordIndex，然后判断如果wordsIndex=wordsInUse，则什么也不做返回；否则，将wordswordIndex对应的bitIndex位清0，然后调用方法recalculateWordsInUse()重新计算正在使用的words大小,该方法会重新设置wordsInUse的值，这只是一个逻辑上的值，实际words数组大小并没有变。例如下面的代码：BitSet bs = new BitSet();bs.set(12);bs.clear(12);System.out.println(bs.size(); /result: 64 /public int size() words.length * BITS_PER_WORD该例子中，默认BitSet为64位，先调用set(12)将第12位置位，然后调用clear(12)清除第12位，这时候recalculateWordsInUse()方法会设置wordsInUse值为0。但是，此时调用bs.size()还是会返回64，因为wordsInUse只是逻辑上的值，表示当前用到的words数目，而实际上我们words数组大小还是为1，所以size()方法返回64。其他方法/* * Sets all of the bits in this BitSet to false. * * since 1.4 */public void clear() while (wordsInUse 0)words-wordsInUse = 0;/*这个方法将fromIndex, toIndex)范围内的位都清零。注意包含开头不包含结尾。这里的位操作要特别注意。*/public void clear(int fromIndex, int toIndex) checkRange(fromIndex, toIndex);if (fromIndex = toIndex)return;int startWordIndex = wordIndex(fromIndex);if (startWordIndex = wordsInUse)return;int endWordIndex = wordIndex(toIndex - 1);if (endWordIndex = wordsInUse) toIndex = length();endWordIndex = wordsInUse - 1;long firstWordMask = WORD_MASK -toIndex; /注意这里是算术移位if (startWordIndex = endWordIndex) / Case 1: One wordwordsstartWordIndex &= (firstWordMask & lastWordMask); else / Case 2: Multiple words/ Handle first wordwordsstartWordIndex &= firstWordMask;/ Hand