位图原理及实现 - 海量数据处理标配
位图 - 数据结构
为什么要位图？上一篇里面有个例子，是这样的： 你要给1亿个int型数据去重（本篇不讲int以外的，int以外的等我学了布隆过滤器或者各位自行学习布隆过滤器之后再说），要怎么弄？
一般对于去重的思路就是：排序、遍历、去重。
那，就先讲这个排序。怎么排？看完上一篇的小伙伴都知道，用“位”来排序，快。
但是，时间是有了，空间呢？来算一笔账啊：一个int，4个字节，256个int是1k，大概25W个数据为1M，那1billion个数据，就是400M。 那2.5billion个数据就是1G了。
这动不动就要耗费这么大的内存来排个序，挺好。
而位图，就将大大地缩小这个，内存占用。
都知道，一个int是32个字节，那如果用每个字节来存一个数据，又当如何？
先不要问怎么实现的（映射），至少现在知道，一个int可以存32个数据，那么这个空间是不是被直接压缩了32倍。 那1亿个数据也不用400M的内存来排序了，只要25M，接受了这个观点，咱再继续往下。
位图设计
数据结构构造
为了方便，我们将位图用一个数组表示，让vector帮我们开辟一段连续的空间，我们只负责将数据设置或者移除就行。
void SetBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
_bitTable[index] |= (1 << num);
}先把这个构造函数看懂了，不然下面就一团晕。
新元素插入
读取到一个数据，自然是要插入到位图中
void SetBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
_bitTable[index] |= (1 << num);
}如果是为了去重，在这里就可以动手脚了，不过本着“单一职责原则”，我就不动手脚了。
来看看为什么需要size_t index = x >> 5和size_t num = x % 32两步操作：我们看看要映射5和32这俩个数（如果上面那个构造函数没悟到的话）
5表示防在第1个整型空间的第5位上，32则表示放在第2个整型空间第一位上。而**bitTable[index] |= (1 << num)**能保证把第num位上的数字设置为1，其余数字保持不变。
位图中元素移出
这个就比较直观了，如果位运算熟练的话
void RemoveBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
_bitTable[index] &= ~(1 << num); //~(1 << num) ：除了num位为0，其余位都为1
}位图元素查找
可用于查找，也可用于查重。
bool TestBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
return _bitTable[index] & (1 << num);
}这些功能也差不多够用了，接下来组装一下。
完整代码
class BitMap
{
public:
BitMap(size_t range)
{
_bitTable.resize((range >> 5) + 1);
}
//标识一个数字在位图中的位置
void SetBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
_bitTable[index] |= (1 << num);
}
//取消数字在位图当中的标识.
void RemoveBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
_bitTable[index] &= ~(1 << num);
}
bool TestBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
return _bitTable[index] & (1 << num);
}
private:
vector<int> _bitTable;
};找出二次出现的数据
此时我们就需要使用两位来标记同一个数据了。
class NBitMap
{
public:
NBitMap(size_t range)
{
_bitTable.resize((range >> 4) + 1);
}
void SetBit(size_t x)
{
size_t index = x >> 4;
size_t num = x % 16;
num *= 2;
bool first = _bitTable[index] & (1 << num);
bool second = _bitTable[index] & (1 << (num + 1));
if (!(first && second))
{
_bitTable[index] += (1 << num);
}
}
bool TestBit(size_t x)
{
size_t index = x >> 4;
size_t num = x % 16;
num *= 2;
return (_bitTable[index] >> num) & 0x03;
}
private:
vector<int> _bitTable;
};思考
如何分辨一次出现、二次出现与多次出现的数据？