BitMap從字面的意思，很多人認為是位圖，其實準確的來說，翻譯成基于位的映射，怎么理解呢？
問題引入
有一個無序有界int數組{1,2,5,7},初步估計占用內存44=16字節，因為只有4個數，很容易，可以很快找到需要的數。但是假如有10億個這樣的數呢，10億個不重復并且沒有排過序的無符號的int整數，給出一個整數，找出給定的某個數，你該如何操作？
需求分析：Int類型在JAVA中的存儲占用4個Byte,32Bit。10億4/(102410241024)=3.72G左右。如果這樣的一個大的數據做查找和排序，那估計內存也崩潰了，有人說，這些數據可以不用一次性加載，那就是要存盤了，存盤必然消耗IO。我們提倡的是高性能，這個方案直接不考慮。
問題分析
如果用BitMap思想來解決的話，就好很多，那么BitMap是怎么解決的啊，如下：
一個byte是占8個bit，如果每一個bit的值就是有或者沒有，也就是二進制的0或者1，如果用bit的位置代表數組值有還是沒有，那么0代表該數值沒有出現過，1代表該數組值出現過。不也能描述數據了嗎？具體如下圖：
是不是很神奇，那么現在假如10億的數據所需的空間就是3.72G/32了吧，一個占用32bit的數據現在只占用了1bit，節省了不少的空間，排序就更不用說了，一切顯得那么順利。這樣的數據之間沒有關聯性，要是讀取的，你可以用多線程的方式去讀取。時間復雜度方面也是O(Max/n)，其中Max為byte[]數組的大小，n為線程大小。
三、應用與代碼
如果BitMap僅僅是這個特點，我覺得還不是它的優雅的地方，接下來繼續欣賞它的魅力所在。下面的計算思想其實就是針對bit的邏輯運算得到，類似這種邏輯運算的應用場景可以用于權限計算之中。
再看代碼之前，我們先搞清楚一個問題，一個數怎么快速定位它的索引號，也就是說搞清楚byte[index]的index是多少，position是哪一位。舉個例子吧，例如add(14)。14已經超出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數據該怎么辦呢，不用擔心，很簡單，也很神奇。
上面已經分析了，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后，那個位置自然就是1，然后和以前的數據做|，這樣，那個位置就替換成1了。
bits[arrayIndex] |= 1 << position;
}
(2) clear(int num)
對1進行左移，然后取反，最后與byte[index]作與操作。
實例代碼：
public void clear(int num){
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//將1左移position后，那個位置自然就是1，然后對取反，再與當前值做&，即可清除當前的位置了.
bits[arrayIndex] &= ~(1 << position);
}
(3) contain(int num)
實例代碼：
public boolean contain(int num){
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//將1左移position后，那個位置自然就是1，然后和以前的數據做&，判斷是否為0即可
return (bits[arrayIndex] & (1 << position)) !=0;
}
全部代碼如下：
public class BitMap {
//保存數據的
private byte[] bits;
//能夠存儲多少數據
private int capacity;
public BitMap(int capacity){
this.capacity = capacity;
//1bit能存儲8個數據，那么capacity數據需要多少個bit呢，capacity/8+1,右移3位相當于除以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后，那個位置自然就是1，然后和以前的數據做|，這樣，那個位置就替換成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后，那個位置自然就是1，然后和以前的數據做&，判斷是否為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后，那個位置自然就是1，然后對取反，再與當前值做&，即可清除當前的位置了.
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);
}
}
總結：
Bitmap典型的應用場景為：大量數據的快速排序、查找、去重
其被廣泛用于數據庫和搜索引擎中，通過利用位級并行，它們可以顯著加快查詢速度。
但是，位圖索引會占用大量的內存，因此我們會更喜歡壓縮位圖索引。
