我們知道bit-map在大數據處理方面有著很大的用途，比如排序，去重等。
JDK 從1.0開始就提供了 java.util.BitSet 來對bit-map的支持。BitSet的set，get操作主要是通過 “位運算” 進行的。
BitSet的核心是一個 long的數組：
- /* ?
- ?????*?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 應該是一個 二維的bit數據， bit [ ] [64] word, 當然 JDK中沒有 bit 這個基本的數據類型。但是JDK提供了豐富的位運算符。每個bit 只有兩個值 0 和1（ture 和false）。
bit-map的典型應用場景（偽碼表示）：
有一個 bit數組 bit [ ] bArray = new bit [ 1024 ]。 要對若干非負整數進行排序，例如：{ 2, 5, 78, 58, 11}。使用bit-map的做法是：
- bArray[ 2 ]?=? 1 ;??
- bArray[ 5 ]?=? 1 ;??
- bArray[ 78 ]?=? 1 ;??
- bArray[ 58 ]?=? 1 ;??
- bArray[ 11 ]?=? 1 ;??
然后順序遍歷bArray就行了。
同樣對于BitSet的方法一樣，只不過要調用它的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.
第二步，使用位運算對對應的bit進行賦值為1， words[ wordIndex ] |= (1L << bitIndex).
BitSet的get方法和Set方法一樣，先確定一維，再通過位運算得到二維中對應的值。
是不是感覺很美妙，通過long數組 再加上 位運算 可以模擬出 bit數組。當然，我們也可以使用int數組或者double行數據來構造 bit數組
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
