歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

Java BitSet使用場景和示例

閱讀目錄

  • 一、什麼是BitSet?
  • 二、Java BitSet實現原理
  • 三、使用場景
  • 四、參考資料

一、什麼是BitSet?

  注:以下內容來自JDK API:

  BitSet類實現了一個按需增長的位向量。位Set的每一個組件都有一個boolean值。用非負的整數將BitSet的位編入索引。可以對每個編入索引的位進行測試、設置或者清除。通過邏輯與、邏輯或和邏輯異或操作,可以使用一個 BitSet修改另一個 BitSet的內容。 

  默認情況下,set 中所有位的初始值都是false。 

  每個位 set 都有一個當前大小,也就是該位 set 當前所用空間的位數。注意,這個大小與位 set 的實現有關,所以它可能隨實現的不同而更改。位 set 的長度與位 set 的邏輯長度有關,並且是與實現無關而定義的。 

二、Java BitSet實現原理

  在java中,BitSet的實現位於java.util包中:

public class BitSet implements Cloneable, java.io.Serializable 
{
    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;

    private static final ObjectStreamField[] serialPersistentFields =
     {
        new ObjectStreamField("bits", long[].class),
    };

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

  可以看到,BitSet的底層實現是使用long數組作為內部存儲結構的,所以BitSet的大小為long類型大小(64位)的整數倍。

  它有兩個構造函數:

  1、BitSet():創建一個新的位 set,默認大小是64位。

 public BitSet() 
{ initWords(BITS_PER_WORD); sizeIsSticky = false; }

  2、BitSet(int nbits):創建一個位set,它的初始大小足以顯式表示索引范圍在 0 到 nbits-1 的位。

    public BitSet(int nbits)
     {
        // nbits can't be negative; size 0 is OK
        if (nbits < 0)
            throw new NegativeArraySizeException("nbits < 0: " + nbits);
        initWords(nbits);
        sizeIsSticky = true;
    }

  注:

  1、如果指定了bitset的初始化大小,那麼會把他規整到一個大於或者等於這個數字的64的整倍數。比如64位,bitset的大小是1個long,而65位時,bitset大小是2個long,即128位。做這麼一個規定,主要是為了內存對齊,同時避免考慮到不要處理特殊情況,簡化程序。

  2:BitSet的size方法:返回此 BitSet 表示位值時實際使用空間的位數,值是64的整數倍

   length方法:返回此 BitSet 的“邏輯大小”:BitSet 中最高設置位的索引加 1  

三、使用場景

   常見的應用場景是對海量數據進行一些統計工作,比如日志分析、用戶數統計等。

  之前在阿裡的實習面試就被問到一道題:有1千萬個隨機數,隨機數的范圍在1到1億之間。現在要求寫出一種算法,將1到1億之間沒有在隨機數中的數求出來?

  代碼示例如下: 

public class Alibaba
{
    public static void main(String[] args)
    {
        Random random=new Random();
        
        List<Integer> list=new ArrayList<>();
        for(int i=0;i<10000000;i++)
        {
            int randomResult=random.nextInt(100000000);
            list.add(randomResult);
        }
        System.out.println("產生的隨機數有");
        for(int i=0;i<list.size();i++)
        {
            System.out.println(list.get(i));
        }
        BitSet bitSet=new BitSet(100000000);
        for(int i=0;i<10000000;i++)
        {
            bitSet.set(list.get(i));
        }
        
        System.out.println("0~1億不在上述隨機數中有"+bitSet.size());
        for (int i = 0; i < 100000000; i++)
        {
            if(!bitSet.get(i))
            {
                System.out.println(i);
            }
        }     
    }
}

四、參考資料

  1. http://www.linuxidc.com/Linux/2016-07/133592.htm
  2. http://www.linuxidc.com/Linux/2016-07/133594.htm

Copyright © Linux教程網 All Rights Reserved