【導讀：數據是二十一世紀的石油，蘊含巨大價值，這是·情報通·大數據技術系列第[136]篇文章，歡迎閱讀收藏】
1 基本概念
BitMap 從字面的意思，很多人認為是位圖，其實準確的來說，翻譯成基於位的映射。其原理就是用一個 bit 位來標記某個元素對應的 Value ， 而 Key 即是該元素。由於採用了 Bit 為單位來存儲數據，因此可以大大節省存儲空間。
2 詳細說明
2.1 bitmap 應用
a. 進行數據的快速查找，判重，刪除，一般來說數據範圍是 int 的 10 倍以下
b.去重數據而達到壓縮數據
排序示例：
假設我們要對 0-7 內的 5 個元素 (4,7,2,5,3) 排序（這裡假設這些元素沒有重複）。那麼我們就可以採用 Bit-map 的方法來達到排序的目的。要表示 8 個數，我們就只需要 8 個 Bit （ 1Bytes ），首先我們開闢 1Byte 的空間，將這些空間的所有 Bit 位都置為 0( 如下圖： )
然後遍歷這 5 個元素，首先第一個元素是 4 ，那麼就把 4 對應的位置為 1 （可以這樣操作 p+(i/8)|(0×01<
然後再處理第二個元素 7 ，將第八位置為 1, ，接著再處理第三個元素，一直到最後處理完所有的元素，將相應的位置為 1 ，這時候的內存的 Bit 位的狀態如下：
然後我們現在遍歷一遍 Bit 區域，將該位是一的位的編號輸出（ 2 ， 3 ， 4 ， 5 ， 7 ），這樣就達到了排序的目的。
複雜度分析：
Bitmap 排序需要的時間複雜度和空間複雜度依賴於數據中最大的數字。
bitmap 排序的時間複雜度不是 O(N) 的，而是取決於待排序數組中的最大值 MAX ，在實際應用上關係也不大，比如我開 10 個線程去讀 byte 數組，那麼複雜度為 :O(Max/10) 。也就是要是讀取的，可以用多線程的方式去讀取。時間複雜度方面也是 O(Max/n) ，其中 Max 為 byte[] 數組的大小， n 為線程大小。
即空間複雜度應該就是 O(Max/8)bytes 。
2.2 BitMap 算法流程
假設需要排序或者查找的最大數 MAX=10000000 （這裡 MAX 應該是最大的數而不是 int 數據的總數！），那麼我們需要申請內存空間的大小為 int a[1 + MAX/32] 。
其中： a[0] 在內存中佔 32 為可以對應十進制數 0-31 ，依次類推：
bitmap 表為：
<code>a[0]--------->0-31
a[1]--------->32-63
a[2]--------->64-95
a[3]--------->96-127
..........
/<code>
我們要把一個整數 N 映射到 Bit-Map 中去，首先要確定把這個 N Mapping 到哪一個數組元素中去，即確定映射元素的 index 。我們用 int 類型的數組作為 map 的元素，這樣我們就知道了一個元素能夠表示的數字個數 ( 這裡是 32) 。於是 N/32 就可以知道我們需要映射的 key 了。所以餘下來的那個 N%32 就是要映射到的位數。
2.3 BitMap 算法評價
優點：
1. 運算效率高，不進行比較和移位；
2. 佔用內存少，比如最大的數 MAX=10000000 ；只需佔用內存為 MAX/8=1250000Byte=1.25M 。
缺點：
1. 所有的數據不能重複，即不可對重複的數據進行排序。（少量重複數據查找還是可以的，用 2-bitmap ）。
2. 當數據類似（ 1 ， 1000 ， 10 萬）只有 3 個數據的時候，用 bitmap 時間複雜度和空間複雜度相當大，只有當數據比較密集時才有優勢。
閱讀更多 情報通 的文章
