在所有具有效能优化的资料结构中，我想大家使用最多的就是 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