Bitmap在Java中的實作和應用

給定一個最多包含40億個随機排列的32位整數的順序檔案，找出一個不在檔案中的32位整數(在檔案中至少缺失這樣一個數——為什麼？)。在具有足夠記憶體的情況下，如何解決該問題？（程式設計珠玑）

資料的存在性可以使用bit位上的1或0來表示；一個bit具有2個值：0和1，正好可以用來表示false和true。

對于判斷“資料是否存在”的場景，我們通常使用hashmap來存儲，不過hashmap這個資料結構key和value的儲存需要消耗較多的記憶體，不适合儲存較多的資料，比如上面的問題中，如果使用哈希表，每條記錄儲存一個int型的key和一個boolean型的value，

每條至少需要4位元組，假設40億條資料全部不相同，40億條記錄占據160億位元組，即需要16g記憶體，明顯太高。

如何減少資料占用存儲空間可以使用位示圖解決，java.util.bitset可以按位存儲，提供了bitmap的典型實作。

比如有一堆數字，需要存儲，source=[3,5,6,9] 用int就需要4*4個位元組。 java.util.bitset可以存true/false。 如果用java.util.bitset，則會少很多，其原理是： 1，先找出資料中最大值maxvalue=9 2，聲明一個bitset bs,它的size是maxvalue+1=10 3，周遊資料source，bs[source[i]]設定成true. 最後的值是： (0為false;1為true) bs [0,0,0,1,0,1,1,0,0,1] 3, 5,6, 9 這樣一個本來要int型需要占4位元組共32位的數字現在隻用了1位，這樣就省下了很大空間。

常見的應用場景是那些需要對海量資料進行一些統計工作的時候，比如日志分析、使用者數統計等等。

如統計40億個資料中沒有出現的資料，将40億個不同資料進行排序等。

bitset實作了vector接口，bitset中數組大小會随需要增加，位的值為布爾型，

bitset内部是通過一個long[]數組實作的，

是以初始大小為64bit，初始值均為“false”。

先看一下api中的說明

this class implements a vector of bits that grows as needed. 

bitset類實作了一個按需增長的比特向量，

each component of the bit set has a boolean value. 

每個元素都有一個boolean值，

the bits of a bitset are indexed by nonnegative integers.

使用非負整數對每個位進行索引，

individual indexed bits can be examined, set, or cleared. 

可以對每個編入索引的位進行測試、設定或者清除。

one bitset may be used to modify the contents of another bitset through logical and, logical inclusive or, and logical exclusive or operations.

通過邏輯與、邏輯或和邏輯異或操作，可以使用一個 bitset 修改另一個 bitset 的内容。

by default, all bits in the set initially have the value false.

預設情況下，set 中所有位的初始值都是 false。

every bit set has a current size, which is the number of bits of space currently in use by the bit set. note that the size is related to the implementation of a bit set, so it may change with implementation. the length of a bit set relates to logical length of a bit set and is defined independently of implementation.

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

1

2

3

4

5

6

7

8

9

10

11

<code>public</code> <code>static</code> <code>void</code> <code>main(string[] args) {</code>

<code>        </code><code>int</code> <code>[] array = </code><code>new</code> <code>int</code> <code>[] {</code><code>1</code><code>,</code><code>2</code><code>,</code><code>3</code><code>,</code><code>22</code><code>,</code><code>0</code><code>,</code><code>3</code><code>};</code>

<code>        </code><code>bitset bitset  = </code><code>new</code> <code>bitset(</code><code>6</code><code>);</code>

<code>        </code><code>//将數組内容組bitmap</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i=</code><code>0</code><code>;i&lt;array.length;i++)</code>

<code>        </code><code>{</code>

<code>            </code><code>bitset.set(array[i], </code><code>true</code><code>);</code>

<code>        </code><code>}</code>

<code>       </code><code>system.out.println(bitset.size());</code>

<code>        </code><code>system.out.println(bitset.get(</code><code>3</code><code>));</code>

<code>    </code><code>}</code>