在所有具有性能优化的数据结构中，我想大家使用最多的就是hash表，是的，在定位查找场景上具有O(1)的常量时间，多么的简洁优美，
但是在特定的场合下：
①：对10亿个不重复的整数进行排序。
②：找出10亿个数字中重复的数字。
当然我只有普通的服务器，就算2G的内存吧，在这种场景下，我们该如何更好的挑选数据结构和算法呢？
一：问题分析这年头，大牛们写的排序算法也就那么几个，首先我们算下放在内存中要多少G:(10亿32)/(8)=3.6G，可怜的2G内存直接爆掉，所以各种神马的数据结构都玩不起来了，当然使用外排序还是可以解决问题的，由于要走IO所以暂时剔除，既然是数据结构和算法，所以高性能是必须的，想想可不可以在二进制位上做些手脚？比如我要对{1,5,7,2}这四个byte类型的数字做排序，该怎么做呢？大家知道byte是占用8bit，转变思路可以将数组中的值作为bit位的key，value用”0，1“来标识该key是否出现过？下面看图：
从图中我们精彩的看到，数组值都已经作为byte中的key了，最后我只要遍历对应的bit位是否为1就可以了，那么自然就成了有序数组。可能有人说，我增加一个13怎么办？很简单，一个字节可以存放8个数，那两个byte是不是就可以存16个数？刚好了覆盖了13个，画图如下：
可以看出我将一个线性的数组变成了一个bit位的二维矩阵，最终需要的空间仅仅是:3.6G/32=0.1G即可，要注意的是bitmap排序不是O(N)的，而是取决于待排序数组中的最大值，有时候必须要加速的话，可以开10个线程去读byte数组，那么复杂度为:O(Max/10)。
二：代码我想bitmap的思想大家都清楚了，这一次又让我们见证了二进制的魅力，当然这些移位都是位运算的工作了，熟悉了你就玩转了。
1:Clear方法（将数组的所有bit位赋值0）比如要将当前4对应的bit位赋值0的话，只需要1左移4位取反与B[0]即可。
///summary///初始化所用的bit位为0////summary///paramname="i"/paramstaticvoidClear(bytei){//相当于i%8的功能varshift=i0x07;//计算应该放数组的下标vararrindex=i3;//则将当前byte中的指定bit位取0，后其他对方数组bit位必然不变，这就是1的妙用varbitPos=~(1shift);//将数组中的指定bit位置一“操作”a[arrindex]=(byte)(bitPos);}2:Add方法（将bit置1操作）
同样也很简单，要将当前4对应的bit位赋值1的话，只需要1左移4位与B[0]
即可。
///summary///设置相应bit位上为1////summary///paramname="i"/paramstaticvoidAdd(bytei){//相当于i%8的功能varshift=i0x07;//计算应该放数组的下标vararrindex=i3;//将byte中的1移动到i位varbitPos=1shift;//将数组中的指定bit位置一“
操作”a[arrindex]
=(byte)bitPos;}3:Contain方法（判断当前bit位是否是1）
如果看懂了Clear和Add，我相信最后一个方法已经不成问题了。
///summary///判断当前的x在数组的位中是否存在////summary///paramname="i"/param///returns/returnsstaticboolContain(bytei){varj=a[i3](1(i0x07));if(j==0)returnfalse;returntrue;}4.最后上总的代码：
usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Diagnostics;usingSystem.Threading;usingSystem.IO;namespaceConsoleApplication2{publicclassProgram{staticbyten=7;staticbyte[]a;publicstaticvoidMain(){//节省空间的做法a=newbyte[(n3)+1];for(bytei=0;in;i++)Clear(i);Add(4);Console.WriteLine("插入4成功！");vars=Contain(4);Console.WriteLine("当前是否包含4:{0}",s);s=Contain(5);Console.WriteLine("当前是否包含5:{0}",s);Console.Read();}#region初始化所用的bit位为0///summary///初始化所用的bit位为0////summary///paramname="i"/paramstaticvoidClear(bytei){//相当于i%8的功能varshift=i0x07;//计算应该放数组的下标vararrindex=i3;//则将当前byte中的指定bit位取0，后其他对方数组bit位必然不变，这就是1的妙用varbitPos=~(1shift);//将数组中的指定bit位置一“操作”a[arrindex]=(byte)(bitPos);}#endregion#region设置相应bit位上为1///summary///设置相应bit位上为1////summary///paramname="i"/paramstaticvoidAdd(bytei){//相当于i%8的功能varshift=i0x07;//计算应该放数组的下标vararrindex=i3;//将byte中的1移动到i位varbitPos=1shift;//将数组中的指定bit位置一“
操作”a[arrindex]
=(byte)bitPos;}#endregion#region判断当前的x在数组的位中是否存在///summary///判断当前的x在数组的位中是否存在////summary///paramname="i"/param///returns/returnsstaticboolContain(bytei){varj=a[i3](1(i0x07));if(j==0)returnfalse;returntrue;}#endregion}}
非常简单的一个数据结构，您学会了吗？
预览时标签不可点收录于话题#个上一篇下一篇