基于C#实现Bitmap算法

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