BitSet 用法总结

BitSet基本介绍

• BitSet是线程不安全的
• BitSet的初始大小是64位的，每次动态扩容为之前的2倍或者可以满足现在大小中最大的

BitSet源码分析

• BitSet存储的基本数据结构(一个long型的数组)

  /** * The internal field corresponding to the serialField "bits". */
  private long[] words;
  

• BitSet的get方法实现

  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);
  }
  

• BitSet的set方法实现

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

• BitSet动态扩容方法的实现

  • 初始大小，2^6 = 64位（一个long型数据）

    private final static int ADDRESS_BITS_PER_WORD = 6;
    

  • 使用long[]数组的数量，即使用的word的数量，一个word64位

    private transient int wordsInUse = 0;
    

  • 计算需要多少个word

    private static int wordIndex(int bitIndex) { 
        return bitIndex >> ADDRESS_BITS_PER_WORD;
    }
    

  • 检查是否需要扩容

    private void expandTo(int wordIndex) { 
        int wordsRequired = wordIndex+1; 
        if (wordsInUse < wordsRequired) { 
            ensureCapacity(wordsRequired); 
            wordsInUse = wordsRequired; 
        }
    }
    

  • 容量扩充为之前的两倍或者满足现在容量最大的(long []数组扩充)

    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; 
        }
    }
    

  • 好好理解一下核心的这句扩容语句

    int request = Math.max(2 * words.length, wordsRequired);
    

  • Arrays内部使用System.arraycopy实现扩容，需要重新new一个long[]

    public static long[] copyOf(long[] original, int newLength) {
        long[] copy = new long[newLength]; 
        System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); 
        return copy;
    }
    

• BitSet 统计true的数量实现方法(cardinality方法)

  public int cardinality() { 
    int sum = 0; 
    for (int i = 0; i < wordsInUse; i++) 
    sum += Long.bitCount(words[i]); 
    return sum;
  }
  

• nextSetBit实现方法

  public int nextSetBit(int fromIndex) { 
    if (fromIndex < 0) 
        throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);    
    checkInvariants(); int u = wordIndex(fromIndex); 
    if (u >= wordsInUse) 
        return -1; 
    long word = words[u] & (WORD_MASK << fromIndex); 
    while (true) { 
        if (word != 0) 
            return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word); 
        if (++u == wordsInUse) 
            return -1; word = words[u]; 
    }
  }
  

BitSet Demo

public static void test1() { 
    BitSet bitSet = new BitSet(); 
    bitSet.set(23); 
    System.out.println("bitSet size:" + bitSet.size()); bitSet.set(54); 
    System.out.println("bitSet size:" + bitSet.size()); bitSet.set(67); 
    System.out.println("bitSet size:" + bitSet.size()); bitSet.set(320);     
    System.out.println("bitSet size:" + bitSet.size()); 
    System.out.println("The true numbers: " + bitSet.cardinality()); 
    System.out.println("The nextClearBit: " + bitSet.nextClearBit(0)); 
    System.out.println("The nextSetBit: " + bitSet.nextSetBit(0)); 
    bitSet.xor(bitSet); 
    System.out.println("The true numbers: " + bitSet.cardinality()); 
    System.out.println("12's numberOfTrailingZeros: " +  Long.numberOfTrailingZeros(12));}
}

输出结果为：

bitSet size:64
bitSet size:64
bitSet size:128
bitSet size:384
The true numbers: 4
The nextClearBit: 0
The nextSetBit: 23
The true numbers: 0
12's numberOfTrailingZeros: 2

BitSet 基本方法介绍

BitSet解决LeetCode 41题方法

public int firstMissingPositive(int[] nums) { 
    BitSet set = new BitSet(); 
    for (int i = 0; i < nums.length; i++) { 
        if (nums[i] >= 0) {
            set.set(nums[i]); 
        }
    } 
    return set.nextClearBit(1);
}