java下的位图实现

底层数据

    /**
     * 使用long数组保存字符
     */
    private long[] words;
	//当前上限，即long数组长度
    private transient int wordsInUse = 0;
	//判断字（long数组）的大小是否是用户指定的，扩容的时候会选择是当前的2倍还是设置时超出容量的最大值，选最大的
	private transient boolean sizeIsSticky = false;

下标计算

	//idex向右移6位，相当于对index进行64取模，得到对应long下标
    private static int wordIndex(int bitIndex) {
        return bitIndex >> ADDRESS_BITS_PER_WORD;
    }

设置位

	//设置位
    public void set(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
		//得到对应long的下标
        int wordIndex = wordIndex(bitIndex);
        //不足的话，扩容
        expandTo(wordIndex);
        
		//1L<<bitIndex通过循环左移动可以得到64位下对应的位为1的数字，再通过|运算把原long对应的位置1    
        words[wordIndex] |= (1L << bitIndex);

        checkInvariants();
    }

清除位

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

        int wordIndex = wordIndex(bitIndex);
        if (wordIndex >= wordsInUse)
            return;
		
        //~(1L << bitIndex)得到对应位为0其他为为1的long，再和原long与运算，把对应位置0，
        words[wordIndex] &= ~(1L << bitIndex);

        recalculateWordsInUse();
        checkInvariants();
    }

扩容

	//扩容，expandTo中会对容量+1后进行判断是否需要扩容，然后调用此方法
    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);
            //通过创建新数组扩容，扩容为2倍或者所需要的最大值作为容量上限
            words = Arrays.copyOf(words, request);
            sizeIsSticky = false;
        }
    }

遍历

可以用nextBitSet得到传入索引的下一个使用了的位索引（置为1的） 也可以用nextBitClear，同上 previousSetBit、previousClearBit也是顾名思义

next也只是用index下标做遍历

    public int nextClearBit(int fromIndex) {
        // Neither spec nor implementation handle bitsets of maximal length.
        // See 4816253.
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

        checkInvariants();

        int u = wordIndex(fromIndex);
        if (u >= wordsInUse)
            return fromIndex;

        long word = ~words[u] & (WORD_MASK << fromIndex);

        while (true) {
            if (word != 0)
                return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
            if (++u == wordsInUse)
                return wordsInUse * BITS_PER_WORD;
            word = ~words[u];
        }
    }

待续。。