在所有具有效能最佳化的資料結構中，我想大家使用最多的就是 hash 表，是的，在具有定位查詢上具有 O(1) 的常量時間，多麼的簡潔優美，
但是在特定的場合下：
①：對 10 億個不重複的整數進行排序。
②：找出 10 億個數字中重複的數字。
當然我只有普通的站群伺服器，就算 2G 的記憶體吧，在這種場景下，我們該如何更好的挑選資料結構和演演算法呢？
一：問題分析
這年頭，大牛們寫的排序演演算法也就那麼幾個，首先我們算下放在記憶體中要多少 G: (10 億 * 32)/(1024*1024*1024*8)=3.6G，可憐
的 2G 記憶體直接爆掉，所以各種神馬的資料結構都玩不起來了，當然使用外排序還是可以解決問題的，由於要走 IO 所以暫時剔除，因為我們
要玩高效能，無望後我們想想可不可以在二進位制位上做些手腳？
比如我要對 {1,5,7,2} 這四個 byte 型別的數字做排序，該怎麼做呢？我們知道 byte 是佔 8 個 bit 位，其實我們可以將陣列中的值作為 bit 位的
key，value 用”0，1“來標識該 key 是否出現過？下面看圖：
從圖中我們精彩的看到，我們的陣列值都已經作為 byte 中的 key 了，最後我只要遍歷對應的 bit 位是否為 1 就可以了，那麼自然就成有序陣列了。
可能有人說，我增加一個 13 怎麼辦？很簡單，一個位元組可以存放 8 個數，那我只要兩個 byte 就可以解決問題了。
可以看出我將一個線性的陣列變成了一個 bit 位的二維矩陣，最終我們需要的空間僅僅是:3.6G/32=0.1G 即可，要注意的是 bitmap 排序不
是 N 的，而是取決於待排序陣列中的最大值，在實際應用上關係也不大，比如我開 10 個執行緒去讀 byte 陣列，那麼複雜度為:O(Max/10) 。
二：程式碼
我想 bitmap 的思想大家都清楚了，這一次又讓我們見證了二進位制的魅力，當然這些移位都是位運算的工作了，熟悉了你就玩轉了。
1:Clear 方法（將陣列的所有 bit 位置 0）
比如要將當前 4 對應的 bit 位置 0 的話，只需要 1 左移 4 位取反與 B[0] & 即可。
1 #region 初始化所用的 bit 位為 0
2 ///
4 ///
5 ///
6 static void Clear(byte i)
7 {
8 //相當於 i%8 的功能
9 var shift = i & 0x07;
10
11 //計算應該放陣列的下標
12 var arrindex = i >> 3;
13
14 //則將當前 byte 中的指定 bit 位取 0，& 後其他對方陣列 bit 位必然不變，這就是 1 的妙用
15 var bitPos = ~(1 << shift);
16
17 //將陣列中的指定 bit 位置一 “& 操作”
18 a[arrindex] &= (byte)(bitPos);
19 }
20 #endregion
2:Add 方法（將 bit 置 1 操作）
同樣也很簡單，要將當前 4 對應的 bit 位置 1 的話，只需要 1 左移 4 位與 B[0] | 即可。
1 #region 設定相應 bit 位上為 1
2 ///
4 ///
5 ///
6 static void Add(byte i)
7 {
8 //相當於 i%8 的功能
9 var shift = i & 0x07;
10
11 //計算應該放陣列的下標
12 var arrindex = i >> 3;
13
14 //將 byte 中的 1 移動到 i 位
15 var bitPos = 1 << shift;
16
17 //將陣列中的指定 bit 位置一 “| 操作”
18 a[arrindex] |= (byte)bitPos;
19 }
20 #endregion
2:Contain 方法（判斷當前 bit 位是否是 1）
如果看懂了 Clear 和 Add，我相信最後一個方法已經不成問題了。
1 #region 判斷當前的 x 在陣列的位中是否存在
2 ///
4 ///
5 ///
6 ///
7 static bool Contain(byte i)
8 {
9 var j = a[i >> 3] & (1 << (i & 0x07));
10
11 if (j == 0)
12 return false;
13 return true;
14 }
15 #endregion
最後上總的程式碼：
View Code
文章來自網際網路部落格網站 http://www.cnblogs.com/huangxincheng/archive/2012/12/06/2804756.html