BitSet 解決 40億個整數中找到那個唯一重複的數字

基本原理

BitSet是位操作的對象，值隻有0或1即false和true，内部維護了一個long數組，初始隻有一個long，是以BitSet最小的size是64，當随着存儲的元素越來越多，BitSet内部會動态擴充，最終内部是由N個long來存儲，這些針對操作都是透明的。

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

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

40億個整數中找到那個唯一重複的數字

import java.util.BitSet;
public class BitSet2 {
        public static void main(String[] args) {
            BitSet bitSet=new BitSet();
            int[] nums={,,,,,,};

            for (int num : nums) {
                if(bitSet.get(num)){
                    System.out.println(num);
                    break;
                }else {
                    bitSet.set(num);
                }
            }
        }
}
           

源碼分析：

/**
     * 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) {//62
        if (bitIndex < )
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        int wordIndex = wordIndex(bitIndex);//wordIndex /2^6=0;0号桶
        expandTo(wordIndex);//擴容2倍

//words數組，，，1L是Long型，64位，63-0，左移62位，即010000000000....
        words[wordIndex] |= (L << bitIndex); // Restores invariants

        checkInvariants();
    }
           

/**
     * 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 < )
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        checkInvariants();

        int wordIndex = wordIndex(bitIndex);//wordIndex =0号桶
        return (wordIndex < wordsInUse)
            && ((words[wordIndex] & (L << bitIndex)) != );
    }
/**
 (wordIndex < wordsInUse)//首先位桶足夠

  ((words[wordIndex] & (1L << bitIndex)) != 0);        
等價于(words[wordIndex] & (1L << bitIndex%64)) != 0

bitIndex%64即bitIndex取低6位
然後在1左移bitIndex取低6位之後的結果


如果bitIndex=1025
wordIndex =1025/2^6=16号桶
words[wordIndex]=words[16]
1L << bitIndex即1L << bitIndex%64即 bitIndex取低六位000001=1，再1L<<1,即00...10
即1025在第16号桶的第1個比特位上，，，，，63。。。。0

*/