位向量工作原理？

位向量，也叫位圖，是一個我們經(jīng)常可以用到的數(shù)據(jù)結(jié)構(gòu)，在使用小空間來處理大量數(shù)據(jù)方面有著得天獨(dú)厚的優(yōu)勢；位向量的定義就是一串由0.1組成的序列。

Java中對位向量的實(shí)現(xiàn)類時Java.util.BitSet;C++標(biāo)準(zhǔn)庫中也有相應(yīng)的實(shí)現(xiàn)，原理都是一樣的； BitSet源碼也很簡單，很容易看懂 ，如果讀者在對位向量有一定的了解后，可以通過讀源碼來了解BitSet的具體實(shí)現(xiàn)。

一個bit上有兩個值，正好可以用來判斷某些是非狀態(tài)的場景，在針對大數(shù)據(jù)場景下判斷存在性，BitSet是相比其他數(shù)據(jù)結(jié)構(gòu)比如HashMap更好的選擇，在Java中，位向量是用一個叫words的long型數(shù)組實(shí)現(xiàn)的，一個long型變量有64位，可以保存64個數(shù)字；比如我們有[2,8,6,10,15]這5個數(shù)要保存，一般存儲需要 5*4 = 20字節(jié)的存儲空間。但是如果我們使用Java.util.BitSet進(jìn)行存儲則可以節(jié)省很多的空間只需要一個long型數(shù)字就夠了。BitSet只面向數(shù)字只面向數(shù)字使用，對于string類型的數(shù)據(jù)，可以通過hashcode值來使用BitSet。

由于，1 << 64, 1<<128, 1<<192 這些數(shù)字的結(jié)果都為1，BitSet內(nèi)部，long[]數(shù)組的大小由BitSet接收的最大數(shù)字決定，這個數(shù)組將數(shù)字分段表示[0,63],[64,127],[128,191]...。即long[0]用來存儲[0,63]這個范圍的數(shù)字的“存在性”，long[1]用來存儲[64,127]，依次輪推，這樣就避免了位運(yùn)算導(dǎo)致的沖突。原理如下：

------------|----------|----------|----------|----------

Java的BitSet每次申請空間，申請64位，即一個long型變量所占的位數(shù)；