问题引入：

1.给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中?
2.给定一个千万级别数据量的整数集合，判断哪些是重复元素。
3.给定一个千万级别数据量的整形数组，对其进行排序。
4.在5亿个整数中找出不重复的整数(注意，内存不足以容纳这5亿个整数)。

从数据量上看，使用常规的解法（普通排序算法，逐个比较等）明显不合适，所以这里我们引入一个新的解法，就是Bitmap。

Bitmap就是用一个bit位来标记某个元素对应的Value， 而Key即是该bit的位序。由于采用了Bit为单位来存储数据，因此可以大大节省存储空间。 bitmap通过1个位表示一个状态，比如：int类型有2^32个数字，即4G个数字，那么每个数字一个状态，就是2^32个bit，即512 MB（也就是说，用512兆存储空间就可以处理4G个数据，即40+亿数据）。

下面是我用C++写的一个bitmap类，可以通过构造对象时传入数据规模，动态申请所需的内存，然后处理用户的大量数据：

#include
#include
#include
using namespace std;
const unsigned SIZE = 512000000;//512兆静态存储区可处理40.96亿数据

class Bitmap {
? ? typedef struct Byte {
? ? ? ? unsigned char bit8;
? ? ? ? static const unsigned char mask[9];//用来取得一个字节每一位的辅助数组
? ? ? ? Byte()
? ? ? ? {
? ? ? ? ? ? bit8 = 0;
? ? ? ? }
? ? ? ? //设置该位，就是存储该数
? ? ? ? void set1(unsigned at)
? ? ? ? {
? ? ? ? ? ? bit8 |= mask[at];
? ? ? ? }
? ? ? ? //读取该位是否有数
? ? ? ? bool get1(unsigned at)
? ? ? ? {
? ? ? ? ? ? return bit8 & mask[at];
? ? ? ? }
? ? } Byte;
? ? Byte *m_byte;
? ? unsigned m_size;
public:
? ? Bitmap(unsigned _size)
? ? {
? ? ? ? m_byte = new Byte[(_size+7)/8];
? ? ? ? m_size = _size;
? ? }
? ? virtual ~Bitmap()
? ? {
? ? ? ? delete[] m_byte;
? ? ? ? m_size = 0;
? ? }
? ? //存储一个数据
? ? bool push(unsigned data)
? ? {
? ? ? ? if(data>=m_size)
? ? ? ? ? ? return false;
? ? ? ? m_byte[data/8].set1(data%8);
? ? ? ? return true;
? ? }
? ? //读取一个数据是否存在
? ? bool find(unsigned data)
? ? {
? ? ? ? return data>=m_size ? 0 : m_byte[data/8].get1(data%8);
? ? }
? ? //返回能存储的数据个数
? ? unsigned size()
? ? {
? ? ? ? return m_size;
? ? }
? ? //重载运算符实现常用功能
? ? //存储一个数据
? ? bool operator>>(unsigned data)
? ? {
? ? ? ? return push(data);
? ? }
? ? //读取一个数据是否存在
? ? bool operator<<(unsigned data)
? ? {
? ? ? ? return find(data);
? ? }
? ? //访问到某个数据块
? ? Byte& operator[](unsigned i)
? ? {
? ? ? ? if(i>=m_size/8)
? ? ? ? ? ? throw "index out of range";
? ? ? ? return m_byte[i];
? ? }
};
const unsigned char Bitmap::Byte::mask[9] = {0x80,0x40,0x20,0x10,0x8,0x4,0x2,0x1};//用来取得一个字节每一位的辅助数组

int main()
{
? ? Bitmap bitmap(8*SIZE);//可以存储40+亿数据
? ? ifstream file("in.txt");//从文件内录入一些整数
? ? unsigned read, i=0, t1 = clock();
? ? for(i=0; i? ? ? ? if(file>>read)
? ? ? ? ? ? bitmap>>read;
? ? ? ? else
? ? ? ? ? ? break;
? ? file.close();
? ? cout<<"共存储"<? ? t1 = clock();
? ? for(i=0; i<1000000; ++i)
? ? ? ? if(bitmap<? ? ? ? ? ? ;
? ? cout<<"访问"<? ? cout<<"请输入需要检索的数据:"<? ? while(cin>>read) {
? ? ? ? if(bitmap<? ? ? ? ? ? cout<<"已存储"<? ? ? ? else
? ? ? ? ? ? cout<<"Error: 未存储"<? ? }
? ? return 0;
}