一、什么是BitSet？
注：以下內(nèi)容來(lái)自JDK API:
BitSet類(lèi)實(shí)現(xiàn)了一個(gè)按需增長(zhǎng)的位向量。位Set的每一個(gè)組件都有一個(gè)boolean值。用非負(fù)的整數(shù)將BitSet的位編入索引。可以對(duì)每個(gè)編入索引的位進(jìn)行測(cè)試、設(shè)置或者清除。通過(guò)邏輯與、邏輯或和邏輯異或操作，可以使用一個(gè) BitSet修改另一個(gè) BitSet的內(nèi)容。
默認(rèn)情況下，set 中所有位的初始值都是false。
每個(gè)位 set 都有一個(gè)當(dāng)前大小，也就是該位 set 當(dāng)前所用空間的位數(shù)。注意，這個(gè)大小與位 set 的實(shí)現(xiàn)有關(guān)，所以它可能隨實(shí)現(xiàn)的不同而更改。位 set 的長(zhǎng)度與位 set 的邏輯長(zhǎng)度有關(guān)，并且是與實(shí)現(xiàn)無(wú)關(guān)而定義的。
一個(gè)Bitset類(lèi)創(chuàng)建一種特殊類(lèi)型的數(shù)組來(lái)保存位值。BitSet中數(shù)組大小會(huì)隨需要增加。這和位向量（vectorofbits）比較類(lèi)似。
這是一個(gè)傳統(tǒng)的類(lèi)，但它在Java2中被完全重新設(shè)計(jì)。
BitSet定義了兩個(gè)構(gòu)造方法。
第一個(gè)構(gòu)造方法創(chuàng)建一個(gè)默認(rèn)的對(duì)象：
BitSet()
第二個(gè)方法允許用戶指定初始大小。所有位初始化為0。
BitSet(intsize)
二、Java BitSet實(shí)現(xiàn)原理
在java中，BitSet的實(shí)現(xiàn)位于java.util包中：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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的底層實(shí)現(xiàn)是使用long數(shù)組作為內(nèi)部存儲(chǔ)結(jié)構(gòu)的，所以BitSet的大小為long類(lèi)型大小(64位)的整數(shù)倍。
它有兩個(gè)構(gòu)造函數(shù)：
1、BitSet()：創(chuàng)建一個(gè)新的位 set，默認(rèn)大小是64位。
|
1
2
3
4
5
|
public BitSet() { initWords(BITS_PER_WORD); sizeIsSticky = false;} |
2、BitSet(int nbits)：創(chuàng)建一個(gè)位set，它的初始大小足以顯式表示索引范圍在 0 到 nbits-1 的位。
|
1
2
3
4
5
6
7
8
|
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的初始化大小，那么會(huì)把他規(guī)整到一個(gè)大于或者等于這個(gè)數(shù)字的64的整倍數(shù)。比如64位，bitset的大小是1個(gè)long，而65位時(shí)，bitset大小是2個(gè)long，即128位。做這么一個(gè)規(guī)定，主要是為了內(nèi)存對(duì)齊，同時(shí)避免考慮到不要處理特殊情況，簡(jiǎn)化程序。
2：BitSet的size方法：返回此 BitSet 表示位值時(shí)實(shí)際使用空間的位數(shù)，值是64的整數(shù)倍
length方法：返回此 BitSet 的“邏輯大小”：BitSet 中最高設(shè)置位的索引加 1
常見(jiàn)的應(yīng)用場(chǎng)景是對(duì)海量數(shù)據(jù)進(jìn)行一些統(tǒng)計(jì)工作，比如日志分析、用戶數(shù)統(tǒng)計(jì)等。
之前在阿里的實(shí)習(xí)面試就被問(wèn)到一道題：有1千萬(wàn)個(gè)隨機(jī)數(shù)，隨機(jī)數(shù)的范圍在1到1億之間。現(xiàn)在要求寫(xiě)出一種算法，將1到1億之間沒(méi)有在隨機(jī)數(shù)中的數(shù)求出來(lái)？
代碼示例如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
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("產(chǎn)生的隨機(jī)數(shù)有"); 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億不在上述隨機(jī)數(shù)中有"+bitSet.size()); for (int i = 0; i < 100000000; i++) { if(!bitSet.get(i)) { System.out.println(i); } } }} |
總結(jié)
以上就是本文關(guān)于淺談Java BitSet使用場(chǎng)景和代碼示例的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專(zhuān)題，如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！
原文鏈接：http://www.cnblogs.com/xujian2014/p/5491286.html
