一扔嵌、問(wèn)題引入
bitMap是位圖囤萤，其實(shí)準(zhǔn)確的來(lái)說(shuō)，翻譯成基于位的映射蚯妇，舉一個(gè)例子，有一個(gè)無(wú)序有界int數(shù)組{1,2,5,7},初步估計(jì)占用內(nèi)存44=16字節(jié)暂筝，這倒是沒(méi)什么奇怪的箩言，但是假如有10億個(gè)這樣的數(shù)呢，10億4/(102410241024)=3.72G左右焕襟。如果這樣的一個(gè)大的數(shù)據(jù)做查找和排序陨收，那估計(jì)內(nèi)存也崩潰了，有人說(shuō)，這些數(shù)據(jù)可以不用一次性加載务漩，那就是要存盤(pán)了拄衰，存盤(pán)必然消耗IO。我們提倡的是高性能饵骨，這個(gè)方案直接不考慮翘悉。
二、問(wèn)題分析
如果用BitMap思想來(lái)解決的話居触，就好很多妖混，解決方案如下：
一個(gè)byte是占8個(gè)bit，如果每一個(gè)bit的值就是有或者沒(méi)有轮洋，也就是二進(jìn)制的0或者1制市，如果用bit的位置代表數(shù)組值有還是沒(méi)有， 那么0代表該數(shù)值沒(méi)有出現(xiàn)過(guò)弊予，1代表該數(shù)組值出現(xiàn)過(guò)祥楣。不也能描述數(shù)據(jù)了嗎？具體如下圖：
是不是很神奇汉柒，那么現(xiàn)在假如10億的數(shù)據(jù)所需的空間就是3.72G/32了吧误褪，一個(gè)占用32bit的數(shù)據(jù)現(xiàn)在只占用了1bit，節(jié)省了不少的空間竭翠，排序就更不用說(shuō)了振坚，一切顯得那么順利。這樣的數(shù)據(jù)之間沒(méi)有關(guān)聯(lián)性斋扰，要是讀取的渡八，你可以用多線程的方式去讀取。時(shí)間復(fù)雜度方面也是O(Max/n)传货，其中Max為byte[]數(shù)組的大小屎鳍，n為線程大小。
三问裕、應(yīng)用與代碼
如果BitMap僅僅是這個(gè)特點(diǎn)逮壁，我覺(jué)得還不是它的優(yōu)雅的地方，接下來(lái)繼續(xù)欣賞它的魅力所在粮宛。下面的計(jì)算思想其實(shí)就是針對(duì)bit的邏輯運(yùn)算得到窥淆，類(lèi)似這種邏輯運(yùn)算的應(yīng)用場(chǎng)景可以用于權(quán)限計(jì)算之中。
再看代碼之前巍杈，我們先搞清楚一個(gè)問(wèn)題忧饭，一個(gè)數(shù)怎么快速定位它的索引號(hào)，也就是說(shuō)搞清楚byte[index]的index是多少筷畦，position是哪一位词裤。舉個(gè)例子吧刺洒，例如add(14)。14已經(jīng)超出byte[0]的映射范圍吼砂，在byte[1]范圍之類(lèi)逆航。那么怎么快速定位它的索引呢。如果找到它的索引號(hào)渔肩，又怎么定位它的位置呢因俐。Index(N)代表N的索引號(hào)，Position(N)代表N的所在的位置號(hào)赖瞒。
Index(N) = N/8 = N >> 3;
Position(N) = N%8 = N & 0x07;
(1) add(int num)
你要向bitmap里add數(shù)據(jù)該怎么辦呢女揭，不用擔(dān)心，很簡(jiǎn)單栏饮，也很神奇吧兔。
上面已經(jīng)分析了，add的目的是為了將所在的位置從0變成1.其他位置不變.
代碼：
public void add(int num){
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//將1左移position后袍嬉，那個(gè)位置自然就是1境蔼，然后和以前的數(shù)據(jù)做|，這樣伺通，那個(gè)位置就替換成1了箍土。
bits[arrayIndex] |= 1 << position;
}
(2) clear(int num)
對(duì)1進(jìn)行左移，然后取反罐监，最后與byte[index]作與操作吴藻。
實(shí)例代碼：
public void clear(int num){
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//將1左移position后，那個(gè)位置自然就是1弓柱，然后對(duì)取反沟堡，再與當(dāng)前值做&，即可清除當(dāng)前的位置了.
bits[arrayIndex] &= ~(1 << position);
}
(4) contain(int num)
實(shí)例代碼：
public boolean contain(int num){ // num/8得到byte[]的index
int arrayIndex = num >> 3; // num%8得到在byte[index]的位置
int position = num & 0x07; //將1左移position后矢空，那個(gè)位置自然就是1航罗，然后和以前的數(shù)據(jù)做&，判斷是否為0即可
return (bits[arrayIndex] & (1 << position)) !=0;
}
全部代碼：
package com.chs.alg.bitmap;
public class BitMap {
//保存數(shù)據(jù)的
private byte[] bits;
//能夠存儲(chǔ)多少數(shù)據(jù)
private int capacity;
public BitMap(int capacity){
this.capacity = capacity;
//1bit能存儲(chǔ)8個(gè)數(shù)據(jù)屁药，那么capacity數(shù)據(jù)需要多少個(gè)bit呢粥血，capacity/8+1,右移3位相當(dāng)于除以8
bits = new byte[(capacity >>3 )+1];
}
public void add(int num){
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//將1左移position后，那個(gè)位置自然就是1酿箭，然后和以前的數(shù)據(jù)做|复亏，這樣，那個(gè)位置就替換成1了缭嫡。
bits[arrayIndex] |= 1 << position;
}
public boolean contain(int num){
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//將1左移position后缔御，那個(gè)位置自然就是1，然后和以前的數(shù)據(jù)做&械巡，判斷是否為0即可
return (bits[arrayIndex] & (1 << position)) !=0;
}
public void clear(int num){
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//將1左移position后刹淌，那個(gè)位置自然就是1，然后對(duì)取反讥耗，再與當(dāng)前值做&有勾，即可清除當(dāng)前的位置了.
bits[arrayIndex] &= ~(1 << position);
}
public static void main(String[] args) {
BitMap bitmap = new BitMap(100);
bitmap.add(7);
System.out.println("插入7成功");
boolean isexsit = bitmap.contain(7);
System.out.println("7是否存在:"+isexsit);
bitmap.clear(7);
isexsit = bitmap.contain(7);
System.out.println("7是否存在:"+isexsit);
}
}
轉(zhuǎn)自：http://www.cnblogs.com/wuhuangdi/p/4126752.html#3074215
