Bitset分析.doc

JAVA源碼分析之BitSet1.BitSet概述BitSet實(shí)現(xiàn)了一種比特位的向量，能夠自動(dòng)增長，用途很廣泛。如在bloom filter中會(huì)用到BitSet來標(biāo)識(shí)某一位是否置位等。初始情況下所有位都為false。主要的變量如下表中所示，下面分析的時(shí)候會(huì)詳細(xì)介紹這些變量的用處。首先可以注意到用來存儲(chǔ)位向量的數(shù)組words為long類型，也就是說每一個(gè)值可以保存64位信息，所以ADDRESS_BITS_PER_WORD=6。變量wordsInUse用來表示當(dāng)前有多少個(gè)words在用，初始為0，它的值在每次擴(kuò)容words數(shù)組后更新，第一次調(diào)用set(int index)方法時(shí)一定會(huì)更新wordsInUse變量，因?yàn)槌跏贾?會(huì)小于需要的words數(shù)目。這里的word都是long類型，即64位的。此外，變量sizeInSticky表示用戶是否指定了words的數(shù)目。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;由構(gòu)造方法代碼可知，當(dāng)我們不指定比特?cái)?shù)目時(shí)，則默認(rèn)會(huì)用64來初始化BitSet，即words數(shù)組大小為1，并設(shè)置sizeIsSticky為false。如果指定了比特?cái)?shù)目，則用指定的數(shù)目來創(chuàng)建words數(shù)組，并設(shè)置sizeInSticky為true。set(int index):設(shè)置指定的第index位為true（其實(shí)就是置為1）。public void set(int bitIndex) /判斷bitIndex不能小于0if (bitIndex 0)throw new IndexOutOfBoundsException(bitIndex 0: + bitIndex); /計(jì)算這一位在words數(shù)組中的位置int wordIndex = wordIndex(bitIndex); /判斷是否需要擴(kuò)展words數(shù)組大小expandTo(wordIndex); wordswordIndex |= (1L bitIndex); / Restores invariantscheckInvariants();/檢查一些條件是否滿足。private void expandTo(int wordIndex) int wordsRequired = wordIndex + 1;if (wordsInUse wordsRequired) /如果當(dāng)前使用的words數(shù)目小于需要的words數(shù)目，則擴(kuò)展words數(shù)組至需要的大小，并設(shè)置wordsInUse值為當(dāng)前需要的words數(shù)目。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;首先求出需要設(shè)置的位在words數(shù)組中的位置，然后判斷是否需要增加words數(shù)組大小。如果需要增大words數(shù)組，則調(diào)用ensureCapacity方法實(shí)現(xiàn)，該方法設(shè)置新數(shù)組大小為words數(shù)組原來大小的2倍和wordsRequired的較大值，創(chuàng)建新數(shù)組，并將原來words數(shù)組的元素全部拷貝到新創(chuàng)建數(shù)組中，更新words為新數(shù)組的引用。同時(shí)會(huì)設(shè)置sizeIsSticky = false。否則，直接將index位置位，即通過這一行代碼實(shí)現(xiàn)置位：wordswordIndex |= (1L bitIndex);其中wordIndex為index在words數(shù)組中的位置，后面通過按位或操作對(duì)bitIndex位置位。需要注意的是java中的移位操作會(huì)模除位數(shù)，也就是說，long類型的移位會(huì)模除64。例如對(duì)long類型的值左移65位，實(shí)際是左移了65%64=1位。這里可以通過一個(gè)例子來加深印象，比如如下代碼：BitSet bs = new BitSet(); /1bs.set(12); /2bs.set(63); /3bs.set(64); /4第一行創(chuàng)建一個(gè)BitSet對(duì)象，此時(shí)調(diào)用無參數(shù)的構(gòu)造函數(shù)，初始化比特位為64，也就是說words數(shù)組初始大小為1。接著調(diào)用set(12)設(shè)置第12位為1，在執(zhí)行set方法的過程中，會(huì)調(diào)用expandTo()方法來判斷是否需要擴(kuò)容，最終確定是否擴(kuò)容是由ensureCapacity方法決定的。由于第2行代碼是第一次調(diào)用set方法，此時(shí)wordsInUse=0 wordsInUse=1，所以會(huì)擴(kuò)容，同時(shí)設(shè)置wordsInUse=2，新的words數(shù)組大小為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數(shù)組中的索引，然后返回相應(yīng)值的對(duì)應(yīng)的位的是否置位情況，主要通過wordswordIndex & (1L wordsInUse,所以get方法的return語句的后半部分都不會(huì)執(zhí)行了。BitSet bs = new BitSet();System.out.println(bs.get(126);Clear(int index)：清除index位的置位標(biāo)志。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數(shù)組中的位置wordIndex，然后判斷如果wordsIndex=wordsInUse，則什么也不做返回；否則，將wordswordIndex對(duì)應(yīng)的bitIndex位清0，然后調(diào)用方法recalculateWordsInUse()重新計(jì)算正在使用的words大小,該方法會(huì)重新設(shè)置wordsInUse的值，這只是一個(gè)邏輯上的值，實(shí)際words數(shù)組大小并沒有變。例如下面的代碼：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該例子中，默認(rèn)BitSet為64位，先調(diào)用set(12)將第12位置位，然后調(diào)用clear(12)清除第12位，這時(shí)候recalculateWordsInUse()方法會(huì)設(shè)置wordsInUse值為0。但是，此時(shí)調(diào)用bs.size()還是會(huì)返回64，因?yàn)閣ordsInUse只是邏輯上的值，表示當(dāng)前用到的words數(shù)目，而實(shí)際上我們words數(shù)組大小還是為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;/*這個(gè)方法將fromIndex, toIndex)范圍內(nèi)的位都清零。注意包含開頭不包含結(jié)尾。這里的位操作要特別注意。*/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; /注意這里是算術(shù)移位if (startWordIndex = endWordIndex) / Case 1: One wordwordsstartWordIndex &= (firstWordMask & lastWordMask); else / Case 2: Multiple words/ Handle first wordwordsstartWordIndex &= firstWordMask;/ Hand