BitMap(位图)

? 1K=1024byte ? 1M=1024K=1024*1024byte(约100万个字节) ? 1G=1024M=1024*1024K=1024*1024*1024byte(约10亿个字节)
? 假设现在有40亿个不重复且无序的无符号整数，现在给你一个整数让你快速判断它是否在这40亿个数里面？？？（假设现在只有4G的内存） ? 这道题的解决办法很简单，就是用这个数到这40个数中去找就行了，如果找到就是存在，找不到就是不存在。那么问题来了，40亿个无符号整形共有160亿个byte，也就是至少需要16G才能放得下，我么应该怎么才能将这40亿个整数加载到内存中呢？
方法一：分割文件 对于这种大数据问题，通用的方法就是对大文件切分，切分成若干个小文件，再对小文件应用数据结构求解。
方法二：bitmap(位图) ? 对于这种问题，我们通常还有一种更好的方法，那就是位图，位图也是hash的一种应用。 ? 对于这些无符号整数我们完全没有必要用4个字节来表示，因为现在我们只需要找这个数存在还是不存在，只有两种状态，所以我们可以用一个bit位来表示一个数存在还是不存在，0表示不存在，1表示存在。所以现在40亿个无符号整数只需要500M就可以表示了。要找这个数存在还是不存在，只需要计算这个数在bitmap中的位置，再看这一位是0还是1就可以了。

#pragma once
#include<vector>
using namespace std;
class BitMap
{
public:
       BitMap(size_t range)                 //给定位图所能表示的范围
       {
              _bitmap.resize(range/32+1);      //设置大小
       }
       void Set(size_t num)         //置1
       {
              size_t index = num / 32;     //计算所在下标
              size_t bit = num % 32;       //得位所在位置
              _bitmap[index] |= (1 << bit);
       }
       void ReSet(size_t num)           //置零
       {
              size_t index = num / 32;         //计算所在下标
              size_t bit = num % 32;          //得位所在位置
              _bitmap[index] &= (~(1 << bit));
       }
       bool Test(size_t num)
       {
              size_t index = num / 32;         //计算所在下标
              size_t bit = num % 32;          //得位所在位置
              return (_bitmap[index]>>num)&1;
       }
private:
       vector<size_t> _bitmap;
};

（编辑：安卓应用网_ASP源码网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!