說bitmap之前漆撞，我們要明白數(shù)字在內(nèi)存中的表示圣贸，如果說byte用8個二進制位表示挚歧，即可以表示個數(shù)，每個byte占8位吁峻，即每個byte占8行滑负，在內(nèi)存中這樣形象的表示：
要說明的一點是，上面框里只是說這個數(shù)是怎樣表示的用含，并沒有說那是內(nèi)存地址矮慕，不要搞混了。
而bitmap結(jié)構(gòu)啄骇，充分利用了每一行所有的位數(shù)痴鳄，它將每個位置作為一個數(shù)，那么一行就可以模擬表示出8個數(shù)缸夹。
Bitmap介紹
bitmap是很有用的結(jié)構(gòu)痪寻。所謂的bitmap就是用一個bit位來標記某個元素，而數(shù)組下標是該元素明未。
bitmap優(yōu)勢
bitmap經(jīng)常用在大數(shù)據(jù)的題中槽华，比如10億個int類型的數(shù)，如果用int數(shù)組存儲的話趟妥，那么需要大約4G內(nèi)存猫态，浪費內(nèi)存。如果用bitmap解決披摄，就比較方便亲雪。bitmap可以用int來模擬，也可以用byte來模擬疚膊，它只是邏輯上的概念义辕，在java語言中寫不出來，我們采用byte寓盗。一個byte占8個bit灌砖，如果每一個bit的值是有或者沒有璧函，即1或0，則如下圖所示：
比如基显，當我們用 int 類型來模擬 Bitmap 時蘸吓，一個 int 4個字節(jié)共 4*8 = 32位，可以表示32個數(shù)撩幽。原來10億個 int 類型的數(shù)用 int 數(shù)組需要 4G 的內(nèi)存库继，但是我用 bitmap 只需要 4GB / 32 = 128 MB 的內(nèi)存，是不是少多了窜醉。
bitmap代碼實現(xiàn)
第一步：構(gòu)建特定長度的byte數(shù)組（new byte[capacity/8 + 1]）宪萄，其中capacity為整數(shù)數(shù)組長度（如：10億個數(shù)字等）
byte[] bits = new byte[getIndex(n) + 1];
第二步：計算數(shù)字num在byte[]中的位置（num/8和num >> 3一樣），也就是說num在byte[k]榨惰，算這個k是幾
/**
* num/8得到byte[]的index
* @param num
* @return
*/
public int getIndex(int num){
return num >> 3;
}
第三步：計算數(shù)字num在byte[index]中的位置拜英，就是在byte[index]的第幾位，每個byte有8位（num % 8）
/**
* num%8得到在byte[index]的位置
* @param num
* @return
*/
public int getPosition(int num){
return num & 0x07;
}
第四步：將所在位置從0變成1琅催，其它位置不變
/**
* 標記指定數(shù)字（num）在bitmap中的值聊记，標記其已經(jīng)出現(xiàn)過
* 將1左移position后，那個位置自然就是1恢暖，然后和以前的數(shù)據(jù)做|排监，這樣，那個位置就替換成1了
* @param bits
* @param num
*/
public void add(byte[] bits, int num){
bits[getIndex(num)] |= 1 << getPosition(num);
}
解釋如下圖：
第五步：判斷指定數(shù)字num是否存在
/**
* 判斷指定數(shù)字num是否存在<br/>
* 將1左移position后杰捂，那個位置自然就是1舆床，然后和以前的數(shù)據(jù)做&，判斷是否為0即可
* @param bits
* @param num
* @return
*/
public boolean contains(byte[] bits, int num){
return (bits[getIndex(num)] & 1 << getPosition(num)) != 0;
}
第六步：重置某一數(shù)字對應(yīng)在bitmap中的值
/**
* 重置某一數(shù)字對應(yīng)在bitmap中的值<br/>
* 對1進行左移嫁佳，然后取反挨队，最后與byte[index]作與操作。
* @param bits
* @param num
*/
public void clear(byte[] bits, int num){
bits[getIndex(num)] &= ~(1 << getPosition(num));
}
全部代碼如下：
public class Test {
/**
* 創(chuàng)建bitmap數(shù)組
*/
public byte[] create(int n){
byte[] bits = new byte[getIndex(n) + 1];
for(int i = 0; i < n; i++){
add(bits, i);
}
System.out.println(contains(bits, 11));
int index = 1;
for(byte bit : bits){
System.out.println("-------" + index++ + "-------");
showByte(bit);
}
return bits;
}
/**
* 標記指定數(shù)字（num）在bitmap中的值蒿往，標記其已經(jīng)出現(xiàn)過<br/>
* 將1左移position后盛垦，那個位置自然就是1，然后和以前的數(shù)據(jù)做|瓤漏，這樣腾夯，那個位置就替換成1了
* @param bits
* @param num
*/
public void add(byte[] bits, int num){
bits[getIndex(num)] |= 1 << getPosition(num);
}
/**
* 判斷指定數(shù)字num是否存在<br/>
* 將1左移position后，那個位置自然就是1蔬充，然后和以前的數(shù)據(jù)做&蝶俱，判斷是否為0即可
* @param bits
* @param num
* @return
*/
public boolean contains(byte[] bits, int num){
return (bits[getIndex(num)] & 1 << getPosition(num)) != 0;
}
/**
* num/8得到byte[]的index
* @param num
* @return
*/
public int getIndex(int num){
return num >> 3;
}
/**
* num%8得到在byte[index]的位置
* @param num
* @return
*/
public int getPosition(int num){
return num & 0x07;
}
/**
* 重置某一數(shù)字對應(yīng)在bitmap中的值<br/>
* 對1進行左移，然后取反饥漫，最后與byte[index]作與操作榨呆。
* @param bits
* @param num
*/
public void clear(byte[] bits, int num){
bits[getIndex(num)] &= ~(1 << getPosition(num));
}
/**
* 打印byte類型的變量<br/>
* 將byte轉(zhuǎn)換為一個長度為8的byte數(shù)組，數(shù)組每個值代表bit
*/
public void showByte(byte b){
byte[] array = new byte[8];
for(int i = 7; i >= 0; i--){
array[i] = (byte)(b & 1);
b = (byte)(b >> 1);
}
for (byte b1 : array) {
System.out.print(b1);
System.out.print(" ");
}
System.out.println();
}
public static void main(String[] args) {
int n = 100;
new Test().create(n);
}
}
結(jié)果如圖庸队，一共100個數(shù)：
