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