一、問題引入
BitMap從字面的意思，很多人認(rèn)為是位圖，其實(shí)準(zhǔn)確的來說，翻譯成基于位的映射，怎么理解呢？
舉一個(gè)例子，有一個(gè)無序有界int數(shù)組{1,2,5,7},初步估計(jì)占用內(nèi)存44=16字節(jié)，這倒是沒什么奇怪的，但是假如有10億個(gè)這樣的數(shù)呢，10億4/(102410241024)=3.72G左右。如果這樣的一個(gè)大的數(shù)據(jù)做查找和排序，那估計(jì)內(nèi)存也崩潰了，有人說，這些數(shù)據(jù)可以不用一次性加載，那就是要存盤了，存盤必然消耗IO。我們提倡的是高性能，這個(gè)方案直接不考慮。
二、問題分析
如果用BitMap思想來解決的話，就好很多，那么BitMap是怎么解決的啊，如下：
一個(gè)byte是占8個(gè)bit，如果每一個(gè)bit的值就是有或者沒有，也就是二進(jìn)制的0或者1，如果用bit的位置代表數(shù)組值有還是沒有，那么0代表該數(shù)值沒有出現(xiàn)過，1代表該數(shù)組值出現(xiàn)過。不也能描述數(shù)據(jù)了嗎？具體如下圖：
是不是很神奇，那么現(xiàn)在假如10億的數(shù)據(jù)所需的空間就是3.72G/32了吧，一個(gè)占用32bit的數(shù)據(jù)現(xiàn)在只占用了1bit，節(jié)省了不少的空間，排序就更不用說了，一切顯得那么順利。這樣的數(shù)據(jù)之間沒有關(guān)聯(lián)性，要是讀取的，你可以用多線程的方式去讀取。時(shí)間復(fù)雜度方面也是O(Max/n)，其中Max為byte[]數(shù)組的大小，n為線程大小。
三、應(yīng)用與代碼
如果BitMap僅僅是這個(gè)特點(diǎn)，我覺得還不是它的優(yōu)雅的地方，接下來繼續(xù)欣賞它的魅力所在。下面的計(jì)算思想其實(shí)就是針對bit的邏輯運(yùn)算得到，類似這種邏輯運(yùn)算的應(yīng)用場景可以用于權(quán)限計(jì)算之中。
再看代碼之前，我們先搞清楚一個(gè)問題，一個(gè)數(shù)怎么快速定位它的索引號，也就是說搞清楚byte[index]的index是多少，position是哪一位。舉個(gè)例子吧，例如add(14)。14已經(jīng)超出byte[0]的映射范圍，在byte[1]范圍之類。那么怎么快速定位它的索引呢。如果找到它的索引號，又怎么定位它的位置呢。Index(N)代表N的索引號，Position(N)代表N的所在的位置號。
Index(N) = N/8 = N >> 3;
Position(N) = N%8 = N & 0x07;
(1) add(int num)
你要向bitmap里add數(shù)據(jù)該怎么辦呢，不用擔(dān)心，很簡單，也很神奇。
上面已經(jīng)分析了，add的目的是為了將所在的位置從0變成1.其他位置不變.
實(shí)例代碼：
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)
對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，然后對取反，再與當(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;
//能夠存儲多少數(shù)據(jù)
private int capacity;
public BitMap(int capacity){
this.capacity = capacity;
//1bit能存儲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，然后對取反，再與當(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);
}
}
