java.util.BitSet 分析

我们知道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数组