在所有具有性能優化的數據結構中，我想大家使用最多的就是 hash 表，是的，在具有定位查找上具有 O(1)的常量時間，多么的簡潔優美，但是在特定的場合下：
①：對 10 億個不重復的整數進行排序。
②：找出 10 億個數字中重復的數字。
當然我只有普通的服務器，就算 2G 的內存吧，在這種場景下，我們該如何更好的挑選數據結構和算法呢？

一、問題分析

這年頭，大牛們寫的排序算法也就那么幾個，首先我們算下放在內存中要多少 G:
(10 億 * 32)/(102410241024*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] & 即可。

 #region 初始化所用的bit位為0/// <summary>/// 初始化所用的bit位為0/// </summary>/// <param name="i"></param>static void Clear(byte i){//相當于 i%8 的功能var shift = i & 0x07;//計算應該放數組的下標var arrindex = i >> 3;//則將當前byte中的指定bit位取0，&后其他對方數組bit位必然不變，這就是 1 的妙用var bitPos = ~(1 << shift);//將數組中的指定bit位置一  “& 操作”a[arrindex] &= (byte)(bitPos);}#endregion

2、Add 方法（將 bit 置 1 操作）

同樣也很簡單，要將當前 4 對應的 bit 位置 1 的話，只需要 1 左移 4 位與 B[0] | 即可。

 #region 設置相應bit位上為1/// <summary>/// 設置相應bit位上為1/// </summary>/// <param name="i"></param>static void Add(byte i){//相當于 i%8 的功能var shift = i & 0x07;//計算應該放數組的下標var arrindex = i >> 3;//將byte中的 1 移動到i位var bitPos = 1 << shift;//將數組中的指定bit位置一  “| 操作”a[arrindex] |= (byte)bitPos;}#endregion

3、Contain 方法（判斷當前 bit 位是否是 1）

如果看懂了 Clear 和 Add，我相信最后一個方法已經不成問題了。

 #region 判斷當前的x在數組的位中是否存在/// <summary>///判斷當前的x在數組的位中是否存在/// </summary>/// <param name="i"></param>/// <returns></returns>static bool Contain(byte i){var j = a[i >> 3] & (1 << (i & 0x07));if (j == 0)return false;return true;}#endregion

最后上總的代碼：

 using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Diagnostics;using System.Threading;using System.IO;namespace ConsoleApplication2{public class Program{static byte n = 7;static byte[] a;public static void Main(){//節省空間的做法a = new byte[(n >> 3) + 1];for (byte i = 0; i < n; i++)Clear(i);Add(4);Console.WriteLine("插入4成功！");var s = Contain(4);Console.WriteLine("當前是否包含4:{0}", s);s = Contain(5);Console.WriteLine("當前是否包含5:{0}", s);Console.Read();}#region 初始化所用的bit位為0/// <summary>/// 初始化所用的bit位為0/// </summary>/// <param name="i"></param>static void Clear(byte i){//相當于 i%8 的功能var shift = i & 0x07;//計算應該放數組的下標var arrindex = i >> 3;//則將當前byte中的指定bit位取0，&后其他對方數組bit位必然不變，這就是 1 的妙用var bitPos = ~(1 << shift);//將數組中的指定bit位置一  “& 操作”a[arrindex] &= (byte)(bitPos);}#endregion#region 設置相應bit位上為1/// <summary>/// 設置相應bit位上為1/// </summary>/// <param name="i"></param>static void Add(byte i){//相當于 i%8 的功能var shift = i & 0x07;//計算應該放數組的下標var arrindex = i >> 3;//將byte中的 1 移動到i位var bitPos = 1 << shift;//將數組中的指定bit位置一  “| 操作”a[arrindex] |= (byte)bitPos;}#endregion#region 判斷當前的x在數組的位中是否存在/// <summary>///判斷當前的x在數組的位中是否存在/// </summary>/// <param name="i"></param>/// <returns></returns>static bool Contain(byte i){var j = a[i >> 3] & (1 << (i & 0x07));if (j == 0)return false;return true;}#endregion}}