我們知道bit-map在大數(shù)據(jù)處理方面有著很大的用途，比如排序，去重等。
JDK 從1.0開(kāi)始就提供了 java.util.BitSet 來(lái)對(duì)bit-map的支持。BitSet的set，get操作主要是通過(guò) “位運(yùn)算” 進(jìn)行的。
BitSet的核心是一個(gè) long的數(shù)組：
- /* ?
- ?????*?BitSets?are?packed?into?arrays?of?"words."??Currently?a?word?is ?
- ?????*?a?long,?which?consists?of?64?bits,?requiring?6?address?bits. ?
- ?????*?The?choice?of?word?size?is?determined?purely?by?performance?concerns. ?
- ?????*/ ??
- ???? 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 ;??
- ??
- ???? /*?Used?to?shift?left?or?right?for?a?partial?word?mask?*/ ??
- ???? private ? static ? final ? long ?WORD_MASK?=?0xffffffffffffffffL;??
- ??
- ???? /** ?
- ?????*?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?he's?doing?and?try?harder?to?preserve?it. ?
- ?????*/ ??
- ???? private ? transient ? boolean ?sizeIsSticky?=? false ;??
從bit的角度看，words 應(yīng)該是一個(gè) 二維的bit數(shù)據(jù)， bit [ ] [64] word, 當(dāng)然 JDK中沒(méi)有 bit 這個(gè)基本的數(shù)據(jù)類型。但是JDK提供了豐富的位運(yùn)算符。每個(gè)bit 只有兩個(gè)值 0 和1（ture 和false）。
bit-map的典型應(yīng)用場(chǎng)景（偽碼表示）：
有一個(gè) bit數(shù)組 bit [ ] bArray = new bit [ 1024 ]。 要對(duì)若干非負(fù)整數(shù)進(jìn)行排序，例如：{ 2, 5, 78, 58, 11}。使用bit-map的做法是：
- bArray[ 2 ]?=? 1 ;??
- bArray[ 5 ]?=? 1 ;??
- bArray[ 78 ]?=? 1 ;??
- bArray[ 58 ]?=? 1 ;??
- bArray[ 11 ]?=? 1 ;??
然后順序遍歷bArray就行了。
同樣對(duì)于BitSet的方法一樣，只不過(guò)要調(diào)用它的set方法，源碼如下：
- /** ?
- ?????*?Sets?the?bit?at?the?specified?index?to?{@code?true}. ?
- ?????* ?
- ?????*?@param??bitIndex?a?bit?index ?
- ?????*?@throws?IndexOutOfBoundsException?if?the?specified?index?is?negative ?
- ?????*?@since??JDK1.0 ?
- ?????*/ ??
- ???? public ? void ?set( int ?bitIndex)?{??
- ???????? if ?(bitIndex?<? 0 )??
- ???????????? throw ? new ?IndexOutOfBoundsException( "bitIndex?<?0:?" ?+?bitIndex);??
- ??
- ???????? int ?wordIndex?=?wordIndex(bitIndex);??
- ????????expandTo(wordIndex);??
- ??
- ????????words[wordIndex]?|=?(1L?<<?bitIndex);? //?Restores?invariants ??
- ??
- ????????checkInvariants();??
- ????}??
如果將 long [ ] words 理解成 bit [ ] [ 64 ] words的話?
第一步，先算出一維（wordIndex(int bitIndex) 方法）
- /** ?
- ?????*?Given?a?bit?index,?return?word?index?containing?it. ?
- ?????*/ ??
- ???? private ? static ? int ?wordIndex( int ?bitIndex)?{??
- ???????? return ?bitIndex?>>?ADDRESS_BITS_PER_WORD;??
- ????}??
notice: ADDRESS_BITS_PER_WORD = 6.
第二步，使用位運(yùn)算對(duì)對(duì)應(yīng)的bit進(jìn)行賦值為1， words[ wordIndex ] |= (1L << bitIndex).
BitSet的get方法和Set方法一樣，先確定一維，再通過(guò)位運(yùn)算得到二維中對(duì)應(yīng)的值。
是不是感覺(jué)很美妙，通過(guò)long數(shù)組 再加上 位運(yùn)算 可以模擬出 bit數(shù)組。當(dāng)然，我們也可以使用int數(shù)組或者double行數(shù)據(jù)來(lái)構(gòu)造 bit數(shù)組
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
