JDK中的BitMap實(shí)現(xiàn)之BitSet源碼分析

前提

本文主要內(nèi)容是分析JDK中的BitMap實(shí)現(xiàn)之java.util.BitSet的源碼實(shí)現(xiàn)，基于JDK11編寫，其他版本的JDK不一定合適。

?

文中的圖比特低位實(shí)際應(yīng)該是在右邊，但是為了提高閱讀體驗(yàn)，筆者把低位改在左邊了。

?

什么是BitMap

BitMap，直譯為位圖，是一種數(shù)據(jù)結(jié)構(gòu)，代表了有限域中的稠集（Dense Set），每一個(gè)元素至少出現(xiàn)一次，沒(méi)有其他的數(shù)據(jù)和元素相關(guān)聯(lián)。在索引，數(shù)據(jù)壓縮等方面有廣泛應(yīng)用（來(lái)源于維基百科詞條）。計(jì)算機(jī)中1 byte = 8 bit，一個(gè)比特（bit，稱為比特或者位）可以表示1或者0兩種值，通過(guò)一個(gè)比特去標(biāo)記某個(gè)元素的值，而KEY或者INDEX就是該元素，構(gòu)成一張映射關(guān)系圖。因?yàn)椴捎昧?code style="overflow-wrap: break-word;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;">Bit作為底層存儲(chǔ)數(shù)據(jù)的單位，所以可以「極大地節(jié)省存儲(chǔ)空間」。

在Java中，一個(gè)int類型的整數(shù)占4字節(jié)，16比特，int的最大值也就是20多億（具體是2147483647）。假設(shè)現(xiàn)在有一個(gè)需求，在20億整數(shù)中判斷某個(gè)整數(shù)m是否存在，要求使用內(nèi)存必須小于或者等于4GB。如果每個(gè)整數(shù)都使用int存儲(chǔ)，那么存放20億個(gè)整數(shù)，需要20億 * 4byte /1024/1024/1024約等于7.45GB，顯然無(wú)法滿足需求。如果使用BitMap，只需要20億 bit內(nèi)存，也就是20億/8/1024/1024/1024約等于0.233GB。在數(shù)據(jù)量極大的情況下，數(shù)據(jù)集具備有限狀態(tài)，可以考慮使用BitMap存儲(chǔ)和進(jìn)行后續(xù)計(jì)算等處理?，F(xiàn)在假設(shè)用byte數(shù)組去做BitMap的底層存儲(chǔ)結(jié)構(gòu)，初始化一個(gè)容量為16的BitMap實(shí)例，示例如下：

可見(jiàn)當(dāng)前的byte數(shù)組有兩個(gè)元素bitmap[0]（虛擬下標(biāo)為[0,7]）和bitmap[1]（虛擬下標(biāo)為[8,15]）。這里假定使用上面構(gòu)造的這個(gè)BitMap實(shí)例去存儲(chǔ)客戶ID和客戶性別關(guān)系（比特為1代表男性，比特為0代表女性），把ID等于3的男性客戶和ID等于10的女性客戶添加到BitMap中：

由于1 byte = 8 bit，通過(guò)客戶ID除以8就可以定位到需要存放的byte數(shù)組索引，再通過(guò)客戶ID基于8取模，就可以得到需要存放的byte數(shù)組中具體的bit的索引：

#?ID等于3的男性客戶
邏輯索引?=?3
byte數(shù)組索引?=?3?/?8?=?0
bit索引?=?3?%?8?=?3
=>?也就是需要存放在byte[0]的下標(biāo)為3的比特上，該比特設(shè)置為1

#?ID等于10的女性客戶
邏輯索引?=?10
byte數(shù)組索引?=?10?/?8?=?1
bit索引?=?10?%?8?=?2
=>?也就是需要存放在byte[1]的下標(biāo)為2的比特上，該比特設(shè)置為0

然后分別判斷客戶ID為3或者10的客戶性別：

如果此時(shí)再添加一個(gè)客戶ID為17的男性用戶，由于舊的BitMap只能存放16個(gè)比特，所以需要擴(kuò)容，判斷byte數(shù)組中只需新增一個(gè)byte元素（byte[2]）即可：

原則上，底層的byte數(shù)組可以不停地?cái)U(kuò)容，當(dāng)byte數(shù)組長(zhǎng)度達(dá)到Integer.MAX_VALUE，BitMap的容量達(dá)到最大值。

BitSet簡(jiǎn)單使用

java.util.BitSet雖然名字上稱為Set，但實(shí)際上它就是JDK中內(nèi)置的BitMap實(shí)現(xiàn)，1這個(gè)類算是一個(gè)十分古老的類，從注釋上看是JDK1.0引入的，不過(guò)大部分方法是JDK1.4之后新添加或者更新的。以前一小節(jié)的例子基于BitSet做一個(gè)Demo：

public?class?BitSetApp?{

????public?static?void?main(String[]?args)?{
????????BitSet?bitmap?=?new?BitSet(16);
????????bitmap.set(3,?Boolean.TRUE);
????????bitmap.set(11,?Boolean.FALSE);
????????System.out.println("Index?3?of?bitmap?=>?"?+?bitmap.get(3));
????????System.out.println("Index?11?of?bitmap?=>?"?+?bitmap.get(11));
????????bitmap.set(17,?Boolean.TRUE);
????????//?這里不會(huì)觸發(fā)擴(kuò)容，因?yàn)锽itSet中底層存儲(chǔ)數(shù)組是long[]
????????System.out.println("Index?17?of?bitmap?=>?"?+?bitmap.get(17));
????}
}

//?輸出結(jié)果
Index?3?of?bitmap?=>?true
Index?11?of?bitmap?=>?false
Index?17?of?bitmap?=>?true

API使用比較簡(jiǎn)單，為了滿足其他場(chǎng)景，BitSet還提供了幾個(gè)實(shí)用的靜態(tài)工廠方法用于構(gòu)造實(shí)例，范圍設(shè)置和清除比特值和一些集合運(yùn)算等，這里不舉例，后面分析源碼的時(shí)候會(huì)詳細(xì)展開(kāi)。

BitSet源碼分析

前文提到，BitMap如果使用byte數(shù)組存儲(chǔ)，當(dāng)新添加元素的邏輯下標(biāo)超過(guò)了初始化的byte數(shù)組的最大邏輯下標(biāo)就必須進(jìn)行擴(kuò)容。為了盡可能減少擴(kuò)容的次數(shù)，除了需要按實(shí)際情況定義初始化的底層存儲(chǔ)結(jié)構(gòu)，還應(yīng)該選用能夠"承載"更多比特的數(shù)據(jù)類型數(shù)組，因此在BitSet中底層的存儲(chǔ)結(jié)構(gòu)選用了long數(shù)組，一個(gè)long整數(shù)占64比特，位長(zhǎng)是一個(gè)byte整數(shù)的8倍，在需要處理的數(shù)據(jù)范圍比較大的場(chǎng)景下可以有效減少擴(kuò)容的次數(shù)。后文為了簡(jiǎn)化分析過(guò)程，在模擬底層long數(shù)組變化時(shí)候會(huì)使用盡可能少的元素去模擬。BitSet頂部有一些關(guān)于其設(shè)計(jì)上的注釋，這里簡(jiǎn)單羅列概括成幾點(diǎn)：

• BitSet是可增長(zhǎng)比特向量的一個(gè)實(shí)現(xiàn)，設(shè)計(jì)上每個(gè)比特都是一個(gè)布爾值，比特的邏輯索引是非負(fù)整數(shù)
• BitSet的所有比特的初始化值為false（整數(shù)0）
• BitSet的size屬性與其實(shí)現(xiàn)有關(guān)，length屬性（比特表的邏輯長(zhǎng)度）與實(shí)現(xiàn)無(wú)關(guān)
• BitSet在設(shè)計(jì)上是非線程安全，多線程環(huán)境下需要額外的同步處理

按照以往分析源碼的習(xí)慣，先看BitSet的所有核心成員屬性：

public?class?BitSet?implements?Cloneable,?java.io.Serializable?{
????
????//?words是long數(shù)組，一個(gè)long整數(shù)為64bit，2^6?=?64，這里選取6作為words的尋址參數(shù)，可以基于邏輯下標(biāo)快速定位到具體的words中的元素索引
????private?static?final?int?ADDRESS_BITS_PER_WORD?=?6;

????//?words中每個(gè)元素的比特?cái)?shù)，十進(jìn)制值是64
????private?static?final?int?BITS_PER_WORD?=?1?<
????//?bit下標(biāo)掩碼，十進(jìn)制值是63
????private?static?final?int?BIT_INDEX_MASK?=?BITS_PER_WORD?-?1;

????//?掩碼，十進(jìn)制值-1，也就是64個(gè)比特全是1，用于部分word掩碼的左移或者右移
????private?static?final?long?WORD_MASK?=?0xffffffffffffffffL;

????/**
?????*?序列化相關(guān)，略過(guò)
?????*/
????private?static?final?ObjectStreamField[]?serialPersistentFields?=?{
????????new?ObjectStreamField("bits",?long[].class),
????};

????/**
?????*?底層的比特存儲(chǔ)結(jié)構(gòu)，long數(shù)組，同時(shí)也是序列化字段"bits"的對(duì)應(yīng)值
?????*/
????private?long[]?words;

????/**
?????*?已經(jīng)使用的words數(shù)組中的元素個(gè)數(shù)，注釋翻譯：在當(dāng)前BitSet的邏輯長(zhǎng)度中的word（words的元素）個(gè)數(shù)，瞬時(shí)值
?????*/
????private?transient?int?wordsInUse?=?0;

????/**
?????*?標(biāo)記words數(shù)組的長(zhǎng)度是否用戶
?????*/
????private?transient?boolean?sizeIsSticky?=?false;

????//?JDK?1.0.2使用的序列化版本號(hào)
????private?static?final?long?serialVersionUID?=?7997698588986878753L;

????//?暫時(shí)省略其他方法
}

接著看BitSet的幾個(gè)輔助方法：

//?基于bit的邏輯下標(biāo)定位words中word元素的索引，直接右移6位
//?舉例：bitIndex = 3，那么bitIndex >> ADDRESS_BITS_PER_WORD =>?0，說(shuō)明定位到words[0]
//?舉例：bitIndex = 35，那么bitIndex >> ADDRESS_BITS_PER_WORD => 1，說(shuō)明定位到words[1]
private?static?int?wordIndex(int?bitIndex)?{
????return?bitIndex?>>?ADDRESS_BITS_PER_WORD;
}

//?每個(gè)公共方法都必須保留這些不變量，內(nèi)部變量的恒等式校驗(yàn)，字面意思就是每個(gè)公共方法必須調(diào)用此恒等式校驗(yàn)
//?第一條恒等式：當(dāng)前BitSet為空或者最后一個(gè)words元素不能為0（其實(shí)就是當(dāng)前BitSet不為空）
//?第二條恒等式：wordsInUse邊界檢查，范圍是[0, words.length]
//?第三條恒等式：wordsInUse或者等于words.length，意味著用到了所有words的元素；或者words[wordsInUse]?==?0，意味著words中索引為[wordsInUse, words.length - 1]的元素都沒(méi)有被使用
private?void?checkInvariants()?{
????assert(wordsInUse?==?0?||?words[wordsInUse?-?1]?!=?0);
????assert(wordsInUse?>=?0?&&?wordsInUse?<=?words.length);
????assert(wordsInUse?==?words.length?||?words[wordsInUse]?==?0);
}

//?重新計(jì)算wordsInUse的值，也就是刷新已使用的words元素計(jì)算值
//?基于當(dāng)前的wordsInUse?-?1向前遍歷到i?=?0，找到最近一個(gè)不為0的words[i]，然后重新賦值為i?+?1，這里i是words數(shù)組的索引
//?wordsInUse其實(shí)是words數(shù)組最后一個(gè)不為0的元素的下標(biāo)加1，或者說(shuō)用到的words的元素個(gè)數(shù)，稱為邏輯容量(logical?size)
private?void?recalculateWordsInUse()?{
????//?Traverse?the?bitset?until?a?used?word?is?found
????int?i;
????for?(i?=?wordsInUse-1;?i?>=?0;?i--)
????????if?(words[i]?!=?0)
????????????break;

????wordsInUse?=?i+1;?//?The?new?logical?size
}

然后看BitSet的構(gòu)造函數(shù)和靜態(tài)工廠方法：

//?默認(rèn)的公共構(gòu)造方法，比特表的邏輯長(zhǎng)度為64，words數(shù)組長(zhǎng)度為2，標(biāo)記sizeIsSticky為false，也就是比特表的長(zhǎng)度不是用戶自定義的
public?BitSet()?{
????initWords(BITS_PER_WORD);
????sizeIsSticky?=?false;
}

//?自定義比特表邏輯長(zhǎng)度的構(gòu)造方法，該長(zhǎng)度必須為非負(fù)整數(shù)，標(biāo)記sizeIsSticky為true，也就是比特表的長(zhǎng)度是由用戶自定義的
public?BitSet(int?nbits)?{
????if?(nbits?0)
????????throw?new?NegativeArraySizeException("nbits??+?nbits);
????initWords(nbits);
????sizeIsSticky?=?true;
}

//?初始化words數(shù)組，數(shù)組的長(zhǎng)度為length?=?(nbits?-?1)?/?64?+?1
//?例如nbits?=?16，相當(dāng)于long[]?words?=?new?long[(16?-?1)?/?64?+?1]?=>?new?long[1];
//?例如nbits?=?65，相當(dāng)于long[]?words?=?new?long[(65?-?1)?/?64?+?1]?=>?new?long[2];
//?以此類推
private?void?initWords(int?nbits)?{
????words?=?new?long[wordIndex(nbits-1)?+?1];
}

//?直接自定義底層的words數(shù)組構(gòu)造方法，標(biāo)記所有words的元素都被使用
private?BitSet(long[]?words)?{
????this.words?=?words;
????this.wordsInUse?=?words.length;
????checkInvariants();
}

//?直接自定義底層的words數(shù)組構(gòu)造方法，這個(gè)構(gòu)造方法和上一個(gè)方法不一樣，會(huì)從入?yún)ong數(shù)組從后面開(kāi)始遍歷，直到遍歷到第一個(gè)元素或者不為0的元素，這樣可以盡量截?cái)酂o(wú)用的高位的0元素
//?簡(jiǎn)單來(lái)說(shuō)就是相當(dāng)于：BitSet.valueOf(new long[]{1L, 0L})?=?移除后面的0元素?=> BitSet.valueOf(new long[]{1L})
public?static?BitSet?valueOf(long[]?longs)?{
????int?n;
????for?(n?=?longs.length;?n?>?0?&&?longs[n?-?1]?==?0;?n--)
????????;
????return?new?BitSet(Arrays.copyOf(longs,?n));
}

//?直接自定義底層的words數(shù)組構(gòu)造方法，要求入?yún)長(zhǎng)ongBuffer類型，需要把LongBuffer?=>?long[]?words，方法和BitSet?valueOf(long[]?longs)處理邏輯一致
public?static?BitSet?valueOf(LongBuffer?lb)?{
????lb?=?lb.slice();
????int?n;
????for?(n?=?lb.remaining();?n?>?0?&&?lb.get(n?-?1)?==?0;?n--)
????????;
????long[]?words?=?new?long[n];
????lb.get(words);
????return?new?BitSet(words);
}

//?下面兩個(gè)構(gòu)造方法都是基于byte數(shù)組從后面開(kāi)始遍歷，直到遍歷到第一個(gè)元素或者不為0的元素，截?cái)喑鲆粋€(gè)新的數(shù)組，然后轉(zhuǎn)化為long數(shù)組構(gòu)造BitSet實(shí)例
public?static?BitSet?valueOf(byte[]?bytes)?{
????return?BitSet.valueOf(ByteBuffer.wrap(bytes));
}

public?static?BitSet?valueOf(ByteBuffer?bb)?{
????//?小端字節(jié)排序
????bb?=?bb.slice().order(ByteOrder.LITTLE_ENDIAN);
????int?n;
????//?從后向前遍歷獲到第一個(gè)元素或者第一個(gè)不為0的元素
????for?(n?=?bb.remaining();?n?>?0?&&?bb.get(n?-?1)?==?0;?n--)
????????;
????//?這里需要考慮字節(jié)容器中的字節(jié)元素個(gè)數(shù)不是8的倍數(shù)的情況
????long[]?words?=?new?long[(n?+?7)?/?8];
????//?截?cái)嗪竺娴?元素
????bb.limit(n);
????int?i?=?0;
????//?剩余元素個(gè)數(shù)大于等于8時(shí)候，按照64位去讀取
????while?(bb.remaining()?>=?8)
????????words[i++]?=?bb.getLong();
????//?剩余元素個(gè)數(shù)小于8時(shí)候，按照byte讀取，并且通過(guò)掩碼計(jì)算和左移填充到long數(shù)組元素中
????for?(int?remaining?=?bb.remaining(),?j?=?0;?j?????????words[i]?|=?(bb.get()?&?0xffL)?<8?*?j);
????return?new?BitSet(words);
}

這里構(gòu)造函數(shù)的源碼不是十分復(fù)雜，比較繁瑣的是靜態(tài)工廠方法BitSet valueOf(ByteBuffer bb)，這里舉例推演一下：

ByteBuffer?byteBuffer?=?ByteBuffer.allocate(10);
byteBuffer.order(ByteOrder.LITTLE_ENDIAN);
byteBuffer.putLong(1L);
byteBuffer.put((byte)3);
byteBuffer.put((byte)1);
byteBuffer.flip();
BitSet?bitSet?=?BitSet.valueOf(byteBuffer);
System.out.println(bitSet.size());
System.out.println(bitSet.length());

//?輸出結(jié)果
128
73

過(guò)程如下：

接著看常規(guī)的set、get和clear方法：

//?設(shè)置指定的邏輯索引的比特為true
public?void?set(int?bitIndex)?{
????//?比特邏輯索引必須大于等于0
????if?(bitIndex?0)
????????throw?new?IndexOutOfBoundsException("bitIndex??+?bitIndex);
????//?計(jì)算words數(shù)組元素的索引
????int?wordIndex?=?wordIndex(bitIndex);
????//?判斷是否需要擴(kuò)容，如果需要?jiǎng)t進(jìn)行words數(shù)組擴(kuò)容
????expandTo(wordIndex);
????//?相當(dāng)于words[wordIndex]?=?words[wordIndex]?|?(1L?<
????//?注意long的左移如果超過(guò)63位會(huì)溢出，也就是1L?<?1L,1L?<?1L?<?1L?<
????//?這里相當(dāng)于把左移結(jié)果直接和對(duì)應(yīng)的words元素進(jìn)行或運(yùn)算，前者因?yàn)槭腔?進(jìn)行左移，二進(jìn)制數(shù)一定是只有一個(gè)比特為1，其他比特都是0的64比特二級(jí)制序列，或運(yùn)算會(huì)讓對(duì)應(yīng)的words元素與前者對(duì)應(yīng)的比特為1的比特值設(shè)置為1，并且重新賦值對(duì)應(yīng)的words元素
????//?類似于這樣：0000?0000?|?0000 1000?=>?0000 1000
????words[wordIndex]?|=?(1L?<//?Restores?invariants
????//?不變量恒等式斷言校驗(yàn)
????checkInvariants();
}

//?基于計(jì)算的words數(shù)組元素下標(biāo)進(jìn)行擴(kuò)容
private?void?expandTo(int?wordIndex)?{
????//?計(jì)算當(dāng)前的words元素下標(biāo)需要的words數(shù)組長(zhǎng)度
????int?wordsRequired?=?wordIndex?+?1;
????//?如果當(dāng)前的words元素下標(biāo)需要的words數(shù)組長(zhǎng)度大于當(dāng)前已經(jīng)使用的words數(shù)組中的元素個(gè)數(shù)，則進(jìn)行擴(kuò)容（未必一定擴(kuò)容數(shù)組，擴(kuò)容方法里面還有一層判斷）
????if?(wordsInUse?????????//?基于需要的words數(shù)組長(zhǎng)度進(jìn)行擴(kuò)容
????????ensureCapacity(wordsRequired);
????????//?重置當(dāng)前已經(jīng)使用的words數(shù)組中的元素個(gè)數(shù)
????????wordsInUse?=?wordsRequired;
????}
}

//?基于計(jì)算的words數(shù)組元素下標(biāo)進(jìn)行擴(kuò)容，滿足前提下進(jìn)行數(shù)組拷貝
private?void?ensureCapacity(int?wordsRequired)?{
????//?當(dāng)前words數(shù)組長(zhǎng)度比需要的words數(shù)組長(zhǎng)度小，則進(jìn)行擴(kuò)容
????if?(words.length?????????//?分配的新數(shù)組的長(zhǎng)度是舊words數(shù)組元素和傳入的需要的words數(shù)組長(zhǎng)度之間的最大值
????????int?request?=?Math.max(2?*?words.length,?wordsRequired);
????????//?數(shù)組擴(kuò)容
????????words?=?Arrays.copyOf(words,?request);
????????//?因?yàn)橐呀?jīng)進(jìn)行了擴(kuò)容，所以要標(biāo)記比特表的長(zhǎng)度不是用戶自定義的
????????sizeIsSticky?=?false;
????}
}

//?獲取指定的邏輯索引的比特的狀態(tài)
public?boolean?get(int?bitIndex)?{
????//?比特邏輯索引必須大于等于0
????if?(bitIndex?0)
????????throw?new?IndexOutOfBoundsException("bitIndex??+?bitIndex);
????//?不變量恒等式斷言校驗(yàn)
????checkInvariants();
????//?計(jì)算words數(shù)組元素的索引
????int?wordIndex?=?wordIndex(bitIndex);
????//?words數(shù)組元素的索引必須小于正在使用的words元素個(gè)數(shù)，并且把1L左移bitIndex結(jié)果直接和對(duì)應(yīng)的words元素進(jìn)行與運(yùn)算的結(jié)果不是全部比特為0則返回true，否則返回false
????//?類似于這樣（返回true的場(chǎng)景）：0000 1010?&?0000 1000?=>?0000 1000?=>?說(shuō)明定位到的words中的元素曾經(jīng)通過(guò)set方法設(shè)置過(guò)對(duì)應(yīng)1L << bitIndex的比特為1
????//?類似于這樣（返回false的場(chǎng)景）：0000?0110?&?0000 1000?=>?0000?0000?=>?說(shuō)明定位到的words中的元素未曾通過(guò)set方法設(shè)置過(guò)對(duì)應(yīng)1L << bitIndex的比特為1，對(duì)應(yīng)比特使用的是默認(rèn)值0
????return?(wordIndex?1L?<0);
}

//?設(shè)置指定的邏輯索引的比特為false
public?void?clear(int?bitIndex)?{
????//?比特邏輯索引必須大于等于0
????if?(bitIndex?0)
????????throw?new?IndexOutOfBoundsException("bitIndex??+?bitIndex);
????//?計(jì)算words數(shù)組元素的索引
????int?wordIndex?=?wordIndex(bitIndex);
????//?如果words數(shù)組元素的索引大于等于正在使用的words元素個(gè)數(shù)，說(shuō)明該邏輯下標(biāo)的比特處于初始化狀態(tài)還未被使用，不用處理
????if?(wordIndex?>=?wordsInUse)
????????return;
????//?相當(dāng)于words[wordIndex]?=?words[wordIndex]?&?(~(1L?<
????//?把左移結(jié)果各比特取反然后和對(duì)應(yīng)的words元素進(jìn)行與運(yùn)算，再重新賦值到對(duì)應(yīng)的words元素
????//?類似于：0000 1100?&?(~(0000 1000))?=>?0000 1100?& 1111 0111 =>?0000?0100
????words[wordIndex]?&=?~(1L?<????//?重新計(jì)算wordsInUse的值，也就是刷新已使用的words元素計(jì)算值
????recalculateWordsInUse();
????//?不變量恒等式斷言校驗(yàn)
????checkInvariants();
}

這里模擬一下set方法的過(guò)程：

接著看集合運(yùn)算相關(guān)的方法：

//?判斷兩個(gè)BitSet是否存在交集，這是一個(gè)判斷方法，不會(huì)修改當(dāng)前BitSet的結(jié)構(gòu)
public?boolean?intersects(BitSet?set)?{
????//?對(duì)比當(dāng)前BitSet實(shí)例和入?yún)itSet實(shí)例使用的words元素?cái)?shù)量，取較小值作為遍歷基準(zhǔn)
????for?(int?i?=?Math.min(wordsInUse,?set.wordsInUse)?-?1;?i?>=?0;?i--)
????????//?遍歷和對(duì)比每一個(gè)words數(shù)組的元素，只要滿足與運(yùn)算結(jié)果不為0就返回true（這個(gè)條件是很寬松的，只要底層邏輯比特表剛好兩個(gè)BitSet實(shí)例在同一邏輯索引的比特都為1即可滿足）
????????if?((words[i]?&?set.words[i])?!=?0)
????????????return?true;
????return?false;
}

//?AND運(yùn)算，底層是兩個(gè)BitSet實(shí)例對(duì)應(yīng)索引的words數(shù)組元素進(jìn)行與運(yùn)算，直觀來(lái)看就是計(jì)算兩個(gè)BitSet實(shí)例的交集，存放在本BitSet實(shí)例中
public?void?and(BitSet?set)?{
????//?入?yún)楸綛itSet實(shí)例，不進(jìn)行處理
????if?(this?==?set)
????????return;
????//?如果當(dāng)前BitSet實(shí)例已經(jīng)使用的words數(shù)組元素?cái)?shù)量比傳入的多，那么當(dāng)前BitSet實(shí)例把多出來(lái)那部分words數(shù)組元素置為0
????while?(wordsInUse?>?set.wordsInUse)
????????words[--wordsInUse]?=?0;
????//?遍歷當(dāng)前的BitSet實(shí)例的words數(shù)組已使用的元素，與傳入的BitSet實(shí)例的相同索引元素進(jìn)行與運(yùn)算和重新賦值
????for?(int?i?=?0;?i?????????words[i]?&=?set.words[i];
????//?重新計(jì)算wordsInUse的值，也就是刷新已使用的words元素計(jì)算值
????recalculateWordsInUse();
????//?不變量恒等式斷言校驗(yàn)
????checkInvariants();
}

//?OR運(yùn)算，底層是兩個(gè)BitSet實(shí)例對(duì)應(yīng)索引的words數(shù)組元素進(jìn)行或運(yùn)算，直觀來(lái)看就是計(jì)算兩個(gè)BitSet實(shí)例的并集，存放在本BitSet實(shí)例中
public?void?or(BitSet?set)?{
????//?入?yún)楸綛itSet實(shí)例，不進(jìn)行處理
????if?(this?==?set)
????????return;
????//?計(jì)算兩個(gè)BitSet中words數(shù)組已使用元素的公共部分，其實(shí)也就是較小的wordsInUse
????int?wordsInCommon?=?Math.min(wordsInUse,?set.wordsInUse);
????//?當(dāng)前的BitSet實(shí)例的words數(shù)組已使用的元素?cái)?shù)量比傳入的BitSet實(shí)例小，以傳入的實(shí)例為準(zhǔn)進(jìn)行擴(kuò)容，并且拷貝其wordsInUse值
????if?(wordsInUse?????????ensureCapacity(set.wordsInUse);
????????wordsInUse?=?set.wordsInUse;
????}
????//?兩個(gè)BitSet實(shí)例words數(shù)組已使用元素的公共部分分別按索引進(jìn)行或運(yùn)算，賦值在當(dāng)前BitSet實(shí)例對(duì)應(yīng)索引的words元素
????for?(int?i?=?0;?i?????????words[i]?|=?set.words[i];
????//?如果傳入的BitSet實(shí)例還有超出words數(shù)組已使用元素的公共部分，這部分words數(shù)組元素也拷貝到當(dāng)前的BitSet實(shí)例中，因?yàn)榍懊嬗袛U(kuò)容判斷，走到這里當(dāng)前BitSet實(shí)例的wordsInUse大于等于傳入的BitSet實(shí)例的wordsInUse
????if?(wordsInCommon?????????System.arraycopy(set.words,?wordsInCommon,
????????????????????????????words,?wordsInCommon,
????????????????????????????wordsInUse?-?wordsInCommon);
????//?不變量恒等式斷言校驗(yàn)
????checkInvariants();
}

//?XOR運(yùn)算，底層是兩個(gè)BitSet實(shí)例對(duì)應(yīng)索引的words數(shù)組元素進(jìn)行異或運(yùn)算，實(shí)現(xiàn)和OR基本相似，完成處理后需要重新計(jì)算當(dāng)前BitSet實(shí)例的wordsInUse值
public?void?xor(BitSet?set)?{
????int?wordsInCommon?=?Math.min(wordsInUse,?set.wordsInUse);
????if?(wordsInUse?????????ensureCapacity(set.wordsInUse);
????????wordsInUse?=?set.wordsInUse;
????}
????//?Perform?logical?XOR?on?words?in?common
????for?(int?i?=?0;?i?????????words[i]?^=?set.words[i];

????//?Copy?any?remaining?words
????if?(wordsInCommon?????????System.arraycopy(set.words,?wordsInCommon,
????????????????????????????words,?wordsInCommon,
????????????????????????????set.wordsInUse?-?wordsInCommon);
????recalculateWordsInUse();
????checkInvariants();
}


//?AND?NOT運(yùn)算，底層是兩個(gè)BitSet實(shí)例對(duì)應(yīng)索引的words數(shù)組元素進(jìn)行與運(yùn)算之前傳入BitSet實(shí)例對(duì)應(yīng)索引的words數(shù)組元素先做非運(yùn)算，過(guò)程和AND運(yùn)算類似
public?void?andNot(BitSet?set)?{
????//?Perform?logical?(a?&?!b)?on?words?in?common
????for?(int?i?=?Math.min(wordsInUse,?set.wordsInUse)?-?1;?i?>=?0;?i--)
????????words[i]?&=?~set.words[i];
????recalculateWordsInUse();
????checkInvariants();
}

這里模擬一下and方法的過(guò)程：

接著看搜索相關(guān)方法（nextXXXBit、previousYYYBit），這里以nextSetBit(int fromIndex)方法為例子：

//?以比特邏輯索引fromIndex為起點(diǎn)，向后搜索并且返回第一個(gè)狀態(tài)為true的比特的邏輯索引，搜索失敗則返回-1
public?int?nextSetBit(int?fromIndex)?{
????//?起始的比特邏輯索引必須大于等于0
????if?(fromIndex?0)
????????throw?new?IndexOutOfBoundsException("fromIndex??+?fromIndex);
????//?不變量恒等式斷言校驗(yàn)
????checkInvariants();
????//?基于起始的比特邏輯索引計(jì)算words數(shù)組元素的索引
????int?u?=?wordIndex(fromIndex);
????//?words數(shù)組元素的索引超過(guò)已經(jīng)使用的words數(shù)組元素?cái)?shù)量，說(shuō)明數(shù)組越界，直接返回-1
????if?(u?>=?wordsInUse)
????????return?-1;
????//?這里和之前的set方法的左移類似，不過(guò)使用了-1L進(jìn)行左移，例如-1L?<?1111?1111?<?1111?1100（這里假設(shè)限制長(zhǎng)度8，溢出的高位舍棄）
????//?舉例：0000 1010?&?(1111 1111 << 2)?=>?0000 1010?& 1111 1100?=>?0000 1000（索引值為4，當(dāng)前這里不一定得到存在比特為1的結(jié)果）
????long?word?=?words[u]?&?(WORD_MASK?<????//?基于得到的word進(jìn)行遍歷
????while?(true)?{
????????//?說(shuō)明word中存在比特為1，計(jì)算和返回該比特的邏輯索引
????????if?(word?!=?0)
????????????//?基于起始的比特邏輯索引計(jì)算words數(shù)組元素的索引?*?64?+?word中低位連續(xù)為0的比特?cái)?shù)量
????????????return?(u?*?BITS_PER_WORD)?+?Long.numberOfTrailingZeros(word);
????????//?說(shuō)明word中全部比特為0，則u需要向后遞增，等于wordsInUse說(shuō)明越界返回-1，這個(gè)if存在賦值和判斷兩個(gè)邏輯
????????if?(++u?==?wordsInUse)
????????????return?-1;
????????word?=?words[u];
????}
}

nextSetBit(int fromIndex)方法先查找fromIndex所在的words數(shù)組元素，不滿足后再向后進(jìn)行檢索，該方法注釋中還給出了一個(gè)經(jīng)典的使用例子，這里摘抄一下：

BitSet?bitmap?=?new?BitSet();
//?add?element?to?bitmap
//?...?bitmap.set(1993);
for?(int?i?=?bitmap.nextSetBit(0);?i?>=?0;?i?=?bitmap.nextSetBit(i?+?1))?{
????//?operate?on?index?i?here
????if?(i?==?Integer.MAX_VALUE)?{
????????break;?//?or?(i+1)?would?overflow
????}
}

最后看規(guī)格屬性相關(guān)的一些Getter方法：

//?獲取BitSet中的比特總數(shù)量
public?int?size()?{
????//?words數(shù)組長(zhǎng)度?*?64
????return?words.length?*?BITS_PER_WORD;
}

//?獲取BitSet中的比特值為1的總數(shù)量
public?int?cardinality()?{
????int?sum?=?0;
????//?獲取每一個(gè)已使用的words數(shù)組元素的比特為1的數(shù)量然后累加
????for?(int?i?=?0;?i?????????sum?+=?Long.bitCount(words[i]);
????return?sum;
}

//?獲取BitSet的邏輯大?。ú挥?jì)算只是初始化但是未使用的高位比特），簡(jiǎn)單來(lái)說(shuō)就是words[wordsInUse?-?1]中去掉高位比特連續(xù)0的第一個(gè)比特值為1的邏輯索引，例如0001?1010，高位連續(xù)3個(gè)0，邏輯索引為4
public?int?length()?{
????if?(wordsInUse?==?0)
????????return?0;
????return?BITS_PER_WORD?*?(wordsInUse?-?1)?+
????????(BITS_PER_WORD?-?Long.numberOfLeadingZeros(words[wordsInUse?-?1]));
}

其他按范圍設(shè)置或者清除值如set(int fromIndex, int toIndex)、clear(int fromIndex, int toIndex)等方法限于篇幅不進(jìn)行詳細(xì)分析，套路大致是相似的。

BitSet沒(méi)有解決的問(wèn)題

ADDRESS_BITS_PER_WORD的字段注釋中也提到過(guò)：The choice of word size is determined purely by performance concerns（'word'大小的選擇純粹是由性能考慮決定的）。這里的尋址基礎(chǔ)值6的選擇是因?yàn)榈讓舆x用了long數(shù)組，盡可能減少底層數(shù)組的擴(kuò)容次數(shù)。但是這里存在一個(gè)比較矛盾的問(wèn)題，似乎在JDK中沒(méi)有辦法找到位寬比long大而且占用內(nèi)存空間跟long等效的數(shù)據(jù)類型，像byte、String（底層是char數(shù)組）等等都會(huì)在擴(kuò)容次數(shù)方面遠(yuǎn)超long類型。因?yàn)榈讓邮菙?shù)組存儲(chǔ)結(jié)構(gòu)，「并且沒(méi)有限定數(shù)組中元素的下邊界和上邊界」，在一些特定的場(chǎng)景下會(huì)浪費(fèi)過(guò)多的無(wú)用內(nèi)存空間。以前文提到過(guò)的例子做改造，如果要把10億到20億之間的整數(shù)全部加裝到BitSet實(shí)例中（這些值在BitSet的對(duì)應(yīng)的邏輯比特索引的值都標(biāo)記為1），那么在BitSet實(shí)例的底層比特表中，邏輯索引[0,10億)的值都會(huì)是初始化值0，也就是約一半的words[N]的值都是0，這部分內(nèi)存空間是完全被浪費(fèi)掉的。在實(shí)際的業(yè)務(wù)場(chǎng)景中，很多時(shí)候業(yè)務(wù)的主鍵并不是使用數(shù)據(jù)庫(kù)的自增主鍵，而是使用通過(guò)SnowFlake這類算法生成的帶自增趨勢(shì)的數(shù)值主鍵，如果算法定義的基準(zhǔn)時(shí)間戳比較大，那么生成出來(lái)的值會(huì)遠(yuǎn)超int類型的上限（使用long類型承載）。也就是BitSet沒(méi)有解決的問(wèn)題如下：

• 問(wèn)題一：比特表的邏輯索引值上限是Integer.MAX_VALUE，目前沒(méi)有辦法擴(kuò)展成Long.MAX_VALUE，原因是JDK中數(shù)組在底層設(shè)計(jì)的length屬性是int類型的，可以從java.lang.reflect.Array類中得知此限制，筆者認(rèn)為暫時(shí)無(wú)法從底層解決這個(gè)問(wèn)題
• 問(wèn)題二：BitSet沒(méi)有考慮已知比特表的邏輯索引范圍的場(chǎng)景優(yōu)化，也就是必須存儲(chǔ)[0,下邊界)這部分0值，在一些特定場(chǎng)景下會(huì)浪費(fèi)過(guò)多的無(wú)用內(nèi)存空間

對(duì)于問(wèn)題一，可以考慮做一個(gè)簡(jiǎn)單的映射。假設(shè)現(xiàn)在需要存儲(chǔ)[Integer.MAX_VALUE + 1,Integer.MAX_VALUE + 3]到BitSet實(shí)例中，可以實(shí)際存儲(chǔ)[1,3]，處理完畢后，通過(guò)long realIndex = (long) bitIndex + Integer.MAX_VALUE恢復(fù)實(shí)際的索引值，這樣就可以邏輯上擴(kuò)大BitSet的存儲(chǔ)范圍，猜測(cè)可以滿足99%以上的場(chǎng)景：

public?class?LargeBitSetApp?{

????public?static?void?main(String[]?args)?{
????????long?indexOne?=?Integer.MAX_VALUE?+?1L;
????????long?indexTwo?=?Integer.MAX_VALUE?+?2L;
????????long?indexThree?=?Integer.MAX_VALUE?+?3L;
????????BitSet?bitmap?=?new?BitSet(8);
????????//?set(int?fromIndex,?int?toIndex)?=>?[fromIndex,toIndex)
????????bitmap.set((int)?(indexOne?-?Integer.MIN_VALUE),?(int)?(indexThree?-?Integer.MIN_VALUE)?+?1);
????????System.out.printf("Index?=?%d,value?=?%s\n",?indexOne,?bitmap.get((int)?(indexOne?-?Integer.MIN_VALUE)));
????????System.out.printf("Index?=?%d,value?=?%s\n",?indexTwo,?bitmap.get((int)?(indexTwo?-?Integer.MIN_VALUE)));
????????System.out.printf("Index?=?%d,value?=?%s\n",?indexThree,?bitmap.get((int)?(indexThree?-?Integer.MIN_VALUE)));
????}
}

//?輸出結(jié)果
Index?=?2147483648,value?=?true
Index?=?2147483649,value?=?true
Index?=?2147483650,value?=?true

對(duì)于問(wèn)題二，已經(jīng)有現(xiàn)成的實(shí)現(xiàn)，就是類庫(kù)RoaringBitmap，倉(cāng)庫(kù)地址是：https://github.com/RoaringBitmap/RoaringBitmap。該類庫(kù)被Apache的多個(gè)大數(shù)據(jù)組件使用，經(jīng)得起生產(chǎn)環(huán)境的考驗(yàn)。引入依賴如下：

<dependency>
????<groupId>org.roaringbitmapgroupId>
????<artifactId>RoaringBitmapartifactId>
????<version>0.9.23version>
dependency>

簡(jiǎn)單使用：

public?class?RoaringBitmapApp?{

????public?static?void?main(String[]?args)?{
????????RoaringBitmap?bitmap?=?RoaringBitmap.bitmapOf(1,?2,?3,?Integer.MAX_VALUE,?Integer.MAX_VALUE?-?1);
????????System.out.println(bitmap.contains(Integer.MAX_VALUE));
????????System.out.println(bitmap.contains(1));
????}
}

//?輸出結(jié)果
true
true

RoaringBitmap區(qū)分了不同場(chǎng)景去建立底層的存儲(chǔ)容器：

• 稀疏場(chǎng)景：使用ArrayContainer容器，元素?cái)?shù)量小于4096
• 密集場(chǎng)景：使用BitmapContainer容器，類似java.util.BitSet的實(shí)現(xiàn)，元素?cái)?shù)量大于4096
• 聚集場(chǎng)景（理解為前兩種場(chǎng)景的混合）：使用RunContainer容器

小結(jié)

學(xué)習(xí)和分析BitSet的源碼是為了更好地在實(shí)際場(chǎng)景中處理有限狀態(tài)的大批量數(shù)據(jù)集合之間的運(yùn)算，剛好在筆者的業(yè)務(wù)中有匹配的場(chǎng)景，后面有機(jī)會(huì)的話在另一篇實(shí)戰(zhàn)文章中再詳細(xì)展開(kāi)。

參考資料：

• JDK11相關(guān)源碼
• RoaringBitmap Performance Tricks

（本文完 c-4-d e-a-20220103 元旦快樂(lè)，封面來(lái)自Cheems）