昨日读July大神《教你如何迅速秒杀掉：99%的海量数据处理面试题》博客，有这么一题与大家分享：
给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
July给出思路，位图/Bitmap方法，未闻，遂学之。
1.map类型
map是“键-值”对的集合。map类型通常可理解为关联数组：可使用键作为下表来获取一个值，正如内置数组类型一样。而关联的本质在于元素的值与某个特定的键相关联，而并非通过元素在数组中的位置来获取。
--引自《C++ Primer中文版》pp.309
这里讲map的概念并不是要介绍map这个容器，而是引入map类型数据结构，即“key-value”。
2.Bit-Map
所谓Bit-Map，就是用一个bit位来标记某个元素对应的value，而key即是该元素。
比如上题，若是用int型数组存储，每个数据占4个字节，那么40亿个数就是160亿字节，需要16g的内存；而用Bit-Map，以bit为单位存储数据，每个数据占1bit，40亿bit也就是512m（1B=8bit），因此能够有效节约存储空间。
给一个例子：现在我们有一个数组（4,7,2,5,3），现在我们要用Bit-Map来存储。最大的数为7，所以我们需要8个bit来存储，开辟1B的空间，将所有bit位（key=0~7）置为0（value=0），如下图：
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置置为1（p+(i/8)|(0x01<<(i%8))），即右数第4个为1：
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
依次类推，遍历结束：
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
好了，我们只用1B空间存储了5个数，大大节约存储空间。
简单实现本文开头的题目，代码如下：
//written by 七年之后
//2013.09.06于行政北楼 #include<iostream>
using namespace std; #define BYTE_SIZE 8
#define MAX 4000000000 void Bit_Map_Insert(char *bitmap,unsigned int data)
{
bitmap+=data/BYTE_SIZE;
*bitmap=(*bitmap)|(0x01<<(data%BYTE_SIZE));
} void Bit_Map_Search(char *bitmap,unsigned int data)
{
bitmap+=data/BYTE_SIZE;
if((*bitmap)&(0x01<<(data%BYTE_SIZE)))
cout<<data<<" exist."<<endl;
else
cout<<data<<" doesn't exist."<<endl;
} void Bit_Map_Delete(char *bitmap,unsigned int data)
{
bitmap+=data/BYTE_SIZE;
if((*bitmap)&(0x01<<(data%BYTE_SIZE)))
{
*bitmap=(*bitmap)&(~(0x01<<(data%BYTE_SIZE)));
cout<<data<<" has deleted."<<endl;
}
else
{
cout<<data<<" doesn't exist."<<endl;
}
} int main()
{
char *bitmap;
bitmap=new char[+MAX/BYTE_SIZE];
memset(bitmap,,sizeof(bitmap)); /*测试数据*/
unsigned int data_array[]={,,,,,,,,,,
,,,,
,};
for(int i=;i<sizeof(data_array)/;i++)
Bit_Map_Insert(bitmap,data_array[i]); Bit_Map_Search(bitmap,);
Bit_Map_Search(bitmap,);
Bit_Map_Search(bitmap,);
Bit_Map_Search(bitmap,); Bit_Map_Delete(bitmap,);
Bit_Map_Search(bitmap,); return ;
}
本文如有任何疑问、错误，欢迎与我联系，谢谢！（转载请说明出处）
参考：
1.《C++ Primer 中文版》