位图原理及实现 – 海量数据处理标配看，未来的博客-

下午的时候写了一下位运算的：位运算 – 初见
我个人感觉如果对位运算不是很熟的话可以先看一下上面那个

位图 – 数据结构

为什么要位图？上一篇里面有个例子，是这样的：
你要给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; }; 

思考

如何分辨一次出现、二次出现与多次出现的数据？