BitMap演算法詳解

　　所謂的BitMap就是用一個bit位來標記某個元素所對應的value，而key即是該元素，由於BitMap使用了bit位來存儲數據，因此可以大大節省存儲空間。

基本思想：

　　這此我用一個簡單的例子來詳細介紹BitMap演算法的原理。假設我們要對0-7內的5個元素(4,7,2,5,3)進行排序(這裡假設元素沒有重覆)。我們可以使用BitMap演算法達到排序目的。要表示8個數，我們需要8個byte。

　　1.首先我們開闢一個位元組(8byte)的空間，將這些空間的所有的byte位都設置為0

　　2.然後便利這5個元素，第一個元素是4，因為下邊從0開始，因此我們把第五個位元組的值設置為1

　　3.然後再處理剩下的四個元素，最終8個位元組的狀態如下圖

　　4.現在我們遍歷一次bytes區域，把值為1的byte的位置輸出(2,3,4,5,7)，這樣便達到了排序的目的

　　從上面的例子我們可以看出，BitMap演算法的思想還是比較簡單的，關鍵的問題是如何確定10進位的數到2進位的映射圖

MAP映射：

　　假設需要排序或則查找的數的總數N=100000000，BitMap中1bit代表一個數字，1個int = 4Bytes = 4*8bit = 32 bit,那麼N個數需要N/32 int空間。所以我們需要申請記憶體空間的大小為int a[1 + N/32]，其中：a[0]在記憶體中占32為可以對應十進位數0-31，依次類推：

　　a[0]-----------------------------> 0-31

　　a[1]------------------------------> 32-63

　　a[2]-------------------------------> 64-95

　　a[3]--------------------------------> 96-127

　　......................................................

　　那麼十進位數如何轉換為對應的bit位，下麵介紹用位移將十進位數轉換為對應的bit位:

　　1.求十進位數在對應數組a中的下標

　　十進位數0-31，對應在數組a[0]中，32-63對應在數組a[1]中，64-95對應在數組a[2]中………，使用數學歸納分析得出結論：對於一個十進位數n，其在數組a中的下標為：a[n/32]

　　2.求出十進位數在對應數a[i]中的下標

　　例如十進位數1在a[0]的下標為1，十進位數31在a[0]中下標為31，十進位數32在a[1]中下標為0。 在十進位0-31就對應0-31，而32-63則對應也是0-31，即給定一個數n可以通過模32求得在對應數組a[i]中的下標。

　　3.位移

　　對於一個十進位數n,對應在數組a[n/32][n%32]中，但數組a畢竟不是一個二維數組，我們通過移位操作實現置1

　　a[n/32] |= 1 << n % 32 
　　移位操作： 
　　a[n>>5] |= 1 << (n & 0x1F)

　　n & 0x1F 保留n的後五位 相當於 n % 32 求十進位數在數組a[i]中的下標

代碼實現：

 1 public class BitMap {
 2 
 3     private static final int N = 10000000;
 4 
 5     private int[] a = new int[N/32 + 1];
 6 
 7     /**
 8      * 設置所在的bit位為1
 9      * @param n
10      */
11     public void addValue(int n){
12         //row = n / 32 求十進位數在數組a中的下標
13         int row = n >> 5;
14         //相當於 n % 32 求十進位數在數組a[i]中的下標
15         a[row] |= 1 << (n & 0x1F);
16     }
17 
18     // 判斷所在的bit為是否為1
19     public boolean exits(int n){
20         int row = n >> 5;
21         return (a[row] & ( 1 << (n & 0x1F))) != 1;
22     }
23 
24     public void display(int row){
25         System.out.println("BitMap點陣圖展示");
26         for(int i=0;i<row;i++){
27             List<Integer> list = new ArrayList<Integer>();
28             int temp = a[i];
29             for(int j=0;j<32;j++){
30                 list.add(temp & 1);
31                 temp >>= 1;
32             }
33             System.out.println("a["+i+"]" + list);
34         }
35     }
36 
37     public static void main(String[] args){
38         int num[] = {1,5,30,32,64,56,159,120,21,17,35,45};
39         BitMap map = new BitMap();
40         for(int i=0;i<num.length;i++){
41             map.addValue(num[i]);
42         }
43 
44         int temp = 120;
45         if(map.exits(temp)){
46             System.out.println("temp:" + temp + "has already exists");
47         }
48         map.display(5);
49     }
50 }

應用範圍：
　　可以運用在快速查找、去重、排序、壓縮數據等。