Java中的BitSet學習筆記

一. Bitset 基礎

Bitset，也就是位圖，由於可以用非常緊湊的格式來表示給定范圍的連續數據而經常出現在各種算法設計中。上面的圖來自c++庫中bitset的一張圖。

基本原理是，用1位來表示一個數據是否出現過，0為沒有出現過，1表示出現過。使用用的時候既可根據某一個是否為0表示此數是否出現過。

一個1G的空間，有 8*1024*1024*1024=8.58*10^9bit，也就是可以表示85億個不同的數。

常見的應用是那些需要對海量數據進行一些統計工作的時候，比如日志分析等。

面試題中也常出現，比如：統計40億個數據中沒有出現的數據，將40億個不同數據進行排序等。

又如：現在有1千萬個隨機數，隨機數的范圍在1到1億之間。現在要求寫出一種算法，將1到1億之間沒有在隨機數中的數求出來(百度)。

programming pearls上也有一個關於使用bitset來查找電話號碼的題目。

 

Bitmap的常見擴展，是用2位或者更多為來表示此數字的更多信息，比如出現了多少次等。

 

二. java中bitset的實現

Bitset這種結構雖然簡單，實現的時候也有一些細節需要主要。其中的關鍵是一些位操作，比如如何將指定位進行反轉、設置、查詢指定位的狀態（0或者1）等。 本文，分析一下java中bitset的實現，拋磚引玉，希望給那些需要自己設計位圖結構的需要的程序員有所啟發。   Bitmap的基本操作有：

1. 初始化一個bitset，指定大小。
2. 清空bitset。
3. 反轉某一指定位。
4. 設置某一指定位。
5. 獲取某一位的狀態。
6. 當前bitset的bit總位數。

1. 聲明

在java中，bitset的實現，位於java.util這個包中，從jdk 1.0就引入了這個數據結構。在多個jdk的演變中，bitset也不斷演變。本文參照的是jdk 7.0 源代碼中的實現。 聲明如下：

package java.util;

import java.io.*;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.nio.LongBuffer;

public class BitSet implements Cloneable, java.io.Serializable {、

  private long[] words;
....
....

  同時我們也看到使用long數組來作為內部存儲結構。這個決定了，Bitset至少為一個long的大小。下面的構造函數中也會有所體現。

2. 初始化函數

 public BitSet() {
        initWords(BITS_PER_WORD);
        sizeIsSticky = false;
    }

    public BitSet(int nbits) {
        // nbits can't be negative; size 0 is OK
        if (nbits < 0)
            throw new NegativeArraySizeException("nbits < 0: " + nbits);

        initWords(nbits);
    private void initWords(int nbits) {
        words = new long[wordIndex(nbits-1) + 1];
    }
    private static int wordIndex(int bitIndex) {
        return bitIndex >> ADDRESS_BITS_PER_WORD;
    }
    private final static int ADDRESS_BITS_PER_WORD = 6;
    private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;

 兩個構造函數，分別是一個指定了初始大小，一個沒指定。如果沒指定，我們可以看到默認的初始大小為, 2^6 = 64-1=63 bit. 我們知道java中long的大小就是8個字節，也就是8*8=64bit。也就是說，bitset默認的是一個long整形的大小。初始化函數指定了必要的大小。
 注意：如果指定了bitset的初始化大小，那麼會把他規整到一個大於或者等於這個數字的64的整倍數。比如64位，bitset的大小是1個long，而65位時，bitset大小是2個long，即128位。做這麼一個規定，主要是為了內存對齊，同時避免考慮到不要處理特殊情況，簡化程序。

3. 清空bitset

a. 清空所有的bit位，即全部置0。通過循環方式來以此以此置0。 如果是c語言，使用memset會不會快點？

    public void clear() {
        while (wordsInUse > 0)
            words[--wordsInUse] = 0;
    }

b. 清空某一位

   public void clear(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        int wordIndex = wordIndex(bitIndex);
        if (wordIndex >= wordsInUse)
            return;

        words[wordIndex] &= ~(1L << bitIndex);

        recalculateWordsInUse();
        checkInvariants();
    }

第一行是參數檢查，如果bitIndex小於0，則拋參數非法異常。後面執行的是bitset中操作中經典的兩步曲：a. 找到對應的long  b. 操作對應的位。
a. 找到對應的long。 這行語句是  int wordIndex = wordIndex(bitIndex);  
b. 操作對應的位。常見的位操作是通過與特定的mask進行邏輯運算來實現的。因此，首先獲取 mask（掩碼）。
    對於 clear某一位來說，它需要的掩碼是指定位為0，其余位為1，然後與對應的long進行&運算。
   ~(1L << bitIndex);  即獲取mask
  words[wordIndex] &= ; 執行相應的運算。
注意：這裡的參數檢查，對負數index跑出異常，對超出大小的index，不做任何操作，直接返回。具體的原因，有待進一步思考。 c. 清空指定范圍的那些bits

 /**
     * Sets the bits from the specified {@code fromIndex} (inclusive) to the
     * specified {@code toIndex} (exclusive) to {@code false}.
     *
     * @param  fromIndex index of the first bit to be cleared
     * @param  toIndex index after the last bit to be cleared
     * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
     *         or {@code toIndex} is negative, or {@code fromIndex} is
     *         larger than {@code toIndex}
     * @since  1.4
     */
    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 << fromIndex;
        long lastWordMask  = WORD_MASK >>> -toIndex;
        if (startWordIndex == endWordIndex) {
            // Case 1: One word
            words[startWordIndex] &= ~(firstWordMask & lastWordMask);
        } else {
            // Case 2: Multiple words
            // Handle first word
            words[startWordIndex] &= ~firstWordMask;

            // Handle intermediate words, if any
            for (int i = startWordIndex+1; i < endWordIndex; i++)
                words[i] = 0;

            // Handle last word
            words[endWordIndex] &= ~lastWordMask;
        }

        recalculateWordsInUse();
        checkInvariants();
    }

方法是將這個范圍分成三塊，startword; interval words; stopword。
其中startword，只要將從start位到該word結束位全部置0；interval words則是這些long的所有bits全部置0；而stopword這是從起始位置到指定的結束位全部置0。
而特殊情形則是沒有startword和stopword是同一個long。
具體的實現，參照代碼，是分別作出兩個mask，對startword和stopword進行操作。

4. 重要的兩個內部檢查函數

從上面的代碼，可以看到每個函授結尾都會有兩個函數,如下：
 recalculateWordsInUse();
 checkInvariants();
這兩個函數，是對bitset的內部狀態進行維護和檢查的函數。細看實現既可明白其中原理：

/**
     * Sets the field wordsInUse to the logical size in words of the bit set.
     * WARNING:This method assumes that the number of words actually in use is
     * less than or equal to the current value of wordsInUse!
     */
    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
    }

wordsInUse 是檢查當前的long數組中，實際使用的long的個數，即long[wordsInUse-1]是當前最後一個存儲有有效bit的long。這個值是用於保存bitset有效大小的。

    /**
     * Every public method must preserve these invariants.
     */
    private void checkInvariants() {
        assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
        assert(wordsInUse >= 0 && wordsInUse <= words.length);
        assert(wordsInUse == words.length || words[wordsInUse] == 0);
    }

checkInvariants 可以看出是檢查內部狀態，尤其是wordsInUse是否合法的函數。

5. 反轉某一個指定位

反轉，就是1變成0,0變成1，是一個與1的xor操作。

 /**
     * Sets the bit at the specified index to the complement of its
     * current value.
     *
     * @param  bitIndex the index of the bit to flip
     * @throws IndexOutOfBoundsException if the specified index is negative
     * @since  1.4
     */
    public void flip(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        int wordIndex = wordIndex(bitIndex);
        expandTo(wordIndex);

        words[wordIndex] ^= (1L << bitIndex);

        recalculateWordsInUse();
        checkInvariants();
    }

反轉的基本操作也是兩步，找到對應的long， 獲取mask並與指定的位進行xor操作。
 int wordIndex = wordIndex(bitIndex);
 words[wordIndex] ^= (1L << bitIndex);
我們注意到在進行操作之前，執行了一個函數 expandTo(wordIndex); 這個函數是確保bitset中有對應的這個long。如果沒有的話，就對bitset中的long數組進行擴展。擴展的策略，是將當前的空間翻一倍。
代碼如下：

 /**
     * Ensures that the BitSet can accommodate a given wordIndex,
     * temporarily violating the invariants.  The caller must
     * restore the invariants before returning to the user,
     * possibly using recalculateWordsInUse().
     * @param wordIndex the index to be accommodated.
     */
    private void expandTo(int wordIndex) {
        int wordsRequired = wordIndex+1;
        if (wordsInUse < wordsRequired) {
            ensureCapacity(wordsRequired);
            wordsInUse = wordsRequired;
        }
    }
    /**
     * Ensures that the BitSet can hold enough words.
     * @param wordsRequired the minimum acceptable number of words.
     */
    private void ensureCapacity(int wordsRequired) {
        if (words.length < wordsRequired) {
            // Allocate larger of doubled size or required size
            int request = Math.max(2 * words.length, wordsRequired);
            words = Arrays.copyOf(words, request);
            sizeIsSticky = false;
        }
    }

同樣，也提供了一個指定區間的反轉，實現方案與clear基本相同。代碼如下：

 public void flip(int fromIndex, int toIndex) {
        checkRange(fromIndex, toIndex);

        if (fromIndex == toIndex)
            return;

        int startWordIndex = wordIndex(fromIndex);
        int endWordIndex   = wordIndex(toIndex - 1);
        expandTo(endWordIndex);

        long firstWordMask = WORD_MASK << fromIndex;
        long lastWordMask  = WORD_MASK >>> -toIndex;
        if (startWordIndex == endWordIndex) {
            // Case 1: One word
            words[startWordIndex] ^= (firstWordMask & lastWordMask);
        } else {
            // Case 2: Multiple words
            // Handle first word
            words[startWordIndex] ^= firstWordMask;

            // Handle intermediate words, if any
            for (int i = startWordIndex+1; i < endWordIndex; i++)
                words[i] ^= WORD_MASK;

            // Handle last word
            words[endWordIndex] ^= lastWordMask;
        }

        recalculateWordsInUse();
        checkInvariants();
    }

6. 設置某一指定位 （or 操作）

/** 
     * 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();
    }

思路與flip是一樣的，只是執行的是與1的or操作。
同時jdk中提供了，具體設置成0或1的操作，以及設置某一區間的操作。

  public void set(int bitIndex, boolean value) {
        if (value)
            set(bitIndex);
        else
            clear(bitIndex);
    }

7. 獲取某一位置的狀態

  /**
     * Returns the value of the bit with the specified index. The value
     * is {@code true} if the bit with the index {@code bitIndex}
     * is currently set in this {@code BitSet}; otherwise, the result
     * is {@code false}.
     *
     * @param  bitIndex   the bit index
     * @return the value of the bit with the specified index
     * @throws IndexOutOfBoundsException if the specified index is negative
     */
    public boolean get(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        checkInvariants();

        int wordIndex = wordIndex(bitIndex);
        return (wordIndex < wordsInUse)
            && ((words[wordIndex] & (1L << bitIndex)) != 0);
    }

同樣的兩步走，這裡的位操作時&。可以看到，如果指定的bit不存在的話，返回的是false，即沒有設置。
jdk同時提供了一個獲取指定區間的bitset的方法。當然這裡的返回值會是一個bitset，是一個僅僅包含需要查詢位的bitset。注意這裡的大小也僅僅是剛剛能夠容納必須的位（當然，規整到long的整數倍）。代碼如下：

public BitSet get(int fromIndex, int toIndex) {
        checkRange(fromIndex, toIndex);

        checkInvariants();

        int len = length();

        // If no set bits in range return empty bitset
        if (len <= fromIndex || fromIndex == toIndex)
            return new BitSet(0);

        // An optimization
        if (toIndex > len)
            toIndex = len;

        BitSet result = new BitSet(toIndex - fromIndex);
        int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;
        int sourceIndex = wordIndex(fromIndex);
        boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);

        // Process all words but the last word
        for (int i = 0; i < targetWords - 1; i++, sourceIndex++)
            result.words[i] = wordAligned ? words[sourceIndex] :
                (words[sourceIndex] >>> fromIndex) |
                (words[sourceIndex+1] << -fromIndex);

        // Process the last word
        long lastWordMask = WORD_MASK >>> -toIndex;
        result.words[targetWords - 1] =
            ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK)
            ? /* straddles source words */
            ((words[sourceIndex] >>> fromIndex) |
             (words[sourceIndex+1] & lastWordMask) << -fromIndex)
            :
            ((words[sourceIndex] & lastWordMask) >>> fromIndex);

        // Set wordsInUse correctly
        result.wordsInUse = targetWords;
        result.recalculateWordsInUse();
        result.checkInvariants();

        return result;
    }

這裡有一個tricky的操作，即fromIndex的那個bit會存在返回bitset的第0個位置，以此類推。如果fromIndex不是word對齊的話，那麼返回的bitset的第一個word將會包含fromIndex所在word的從fromIndex開始的到fromIndex+1開始的的那幾位（總共加起來是一個word的大小）。
其中>>>是無符號位想右邊移位的操作符。

8. 獲取當前bitset總bit的大小

  /**
     * Returns the "logical size" of this {@code BitSet}: the index of
     * the highest set bit in the {@code BitSet} plus one. Returns zero
     * if the {@code BitSet} contains no set bits.
     *
     * @return the logical size of this {@code BitSet}
     * @since  1.2
     */
    public int length() {
        if (wordsInUse == 0)
            return 0;

        return BITS_PER_WORD * (wordsInUse - 1) +
            (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
    }

9. hashcode

hashcode是一個非常重要的屬性，可以用來表明一個數據結構的特征。bitset的hashcode是用下面的方式實現的：

 /**
     * Returns the hash code value for this bit set. The hash code depends
     * Note that the hash code changes if the set of bits is altered.
     *
     * @return the hash code value for this bit set
     */
    public int hashCode() {
        long h = 1234;
        for (int i = wordsInUse; --i >= 0; )
            h ^= words[i] * (i + 1);

        return (int)((h >> 32) ^ h);
    }

這個hashcode同時考慮了沒給word以及word的位置。當有bit的狀態發生變化時，hashcode會隨之改變。  

三 bitset使用

bitset的使用非常簡單，只要對需要的操作調用對應的函數即可。