所謂的Bit-map就是用一個bit位來標記某個元素對應的Value， 而Key即是該元素。由于采用了Bit為單位來存儲數(shù)據(jù)，因此在存儲空間方面，可以大大節(jié)省。

位圖主要用于快速檢索關鍵字狀態(tài)，通常要求關鍵字是一個連續(xù)的序列（或者關鍵字是一個連續(xù)序列中的大部分）， 最基本的情況，使用1bit標示一個關鍵字的狀態(tài)（可標示兩種狀態(tài)），但根據(jù)需要也可以使用2bit（標示4種狀態(tài)），3bit（標示8種狀態(tài)），當一個狀態(tài)標示需要的位數(shù)達到32bit時，就演變成來一個整型數(shù)組了。

位圖的主要應用場合：標示連續(xù)（或接近連續(xù)，即大部分會出現(xiàn)）的關鍵字序列的狀態(tài)（狀態(tài)數(shù)/關鍵字個數(shù) 越小越好）。位圖還可以用于實現(xiàn)諸如BloomFilter（用于快速判斷一個元素是否屬于某個集合）等擴展結構，這里只討論純位圖的應用場景。

常見應用場合：

假設我們要對0-7內(nèi)的5個元素(4,7,2,5,3)排序（這里假設這些元素沒有重復）。那么我們就可以采用Bit-map的方法來達到排序的目的。要表示8個數(shù)，我們就只需要8個Bit（1Bytes），首先我們開辟1Byte的空間，將這些空間的所有Bit位都置為0(如下圖：)

然后遍歷這5個元素，首先第一個元素是4，那么就把4對應的位置為1（可以這樣操作 p+(i/8)|(0×01<<(i%8)) 當然了這里的操作涉及到Big-ending和Little-ending的情況，這里默認為Big-ending）,因為是從零開始的，所以要把第五位置為一（如下圖）：

然后再處理第二個元素7，將第八位置為1,，接著再處理第三個元素，一直到最后處理完所有的元素，將相應的位置為1，這時候的內(nèi)存的Bit位的狀態(tài)如下：

然后我們現(xiàn)在遍歷一遍Bit區(qū)域，將該位是一的位的編號輸出（2，3，4，5，7），這樣就達到了排序的目的。

應用場景1：磁盤空閑塊的管理

很多文件系統(tǒng)采用bitmap管理磁盤空閑塊，如果該塊是空閑的，標為0，已使用則標為1.

Ext3文件系統(tǒng)中使用位圖來管理磁盤空閑塊（空閑inode節(jié)點）。文件系統(tǒng)創(chuàng)建后，該文件系統(tǒng)擁有的塊數(shù)以及inode節(jié)點數(shù)都是確定的，數(shù)據(jù)塊區(qū)包含一系列連續(xù)的塊（塊號是連續(xù)的），于是可以用位圖來標示數(shù)據(jù)塊的分配狀態(tài)（分配、未分配兩種狀態(tài)，1bit即可標示）。

如下圖，假設ext3的數(shù)據(jù)塊從128開始，一直到1024，則需要1024-128 = 996bit = 128字節(jié)的位圖空間。如下圖，第1bit標示128號塊已經(jīng)被分配，第2bit標示129號塊未被分配，依次類推。使用位圖的高效性在于：1bit標示狀態(tài)，節(jié)省存儲空間，通過關鍵字來定位位圖（偏移是固定的），效率高。

應用場景2：區(qū)域服務器路由

騰訊的QQ號用一個數(shù)字標示，范圍從0到20億，每個QQ號都有可能出現(xiàn)，所有的QQ號被分散的存儲北京、上海、深圳、武漢四個城市的服務器中，現(xiàn)在需要一個路由服務器快速的將登陸的QQ路由到正確的服務器，路由服務器可以讀取四個QQ服務器的數(shù)據(jù)，并構建路由表（需全部存在內(nèi)存中，內(nèi)存限制1G），路由表該如何存儲？

關鍵：QQ號從0-20億，每個號碼都有可能出現(xiàn)；服務器通過0、1、2、3標示，這四種狀態(tài)可以用2bit來標示，于是可以考慮使用位圖來描述路由表。

解法：從0~20億，為每個QQ號分配2bit，路由服務器從QQ服務器中獲取信息，并設置QQ于服務器號的對應關系。當QQ登錄時，路由服務器根據(jù)QQ號定位到其對應的狀態(tài)，并返回對應的服務器號。總的內(nèi)存大小20億 * 2 /8 = 5億字節(jié)(約為0.5G)。

應用場景3：高效排序

數(shù)據(jù)庫里存了很多800電話號碼，數(shù)量特別大，以至于內(nèi)存放不下，如何排序，時間比空間更重要？電話號碼類似于800-810-5555。

關鍵：去掉電話號碼的800后面就是7位的十進制整數(shù)，每個整數(shù)都有可能出現(xiàn)而且不會重復出現(xiàn)，可以采用各種排序算法對這些數(shù)據(jù)進行排序，但時間復雜度都在O(NlogN)及以上。

解法：因每個七位以內(nèi)的整數(shù)都有可能出現(xiàn)，可以用1bit來標示電話號是否出現(xiàn)，遍歷整個電話號序列，設置相應的位，遍歷位圖收集位被設置的號碼即可。

擴展：對于上述問題，每個電話號碼最多出現(xiàn)一次，如果關鍵字可能多次重復出現(xiàn)，但關鍵字范圍比較確定且很集中的情況下，也可使用位圖（根據(jù)關鍵字最多可能出現(xiàn)的次數(shù)確定每個關鍵字需要的位數(shù)），但此時的位圖通常會是一個整型數(shù)組，數(shù)組內(nèi)容為對應位置關鍵字出現(xiàn)的次數(shù)，在執(zhí)行收集過程時，對于每個關鍵字要收集多次（根據(jù)數(shù)組的值確定）。如有一大批職工的年齡信息，需要對這些職工按照年齡信息進行排序，則只需要建立一個長度為100的數(shù)組，每個數(shù)組為對應年齡人的個數(shù)，掃描一遍數(shù)組，收集年齡信息即可。