数据布局——位图

位图概念

位图可以用来快速判断某个数在不在，它的本质也是一种哈希布局，不外位图更节流空间。位图是用比特位来存储数据的。
我们知道一个整形有32个比特位，我们可以用1个整形存储32个数据，假如我们要查找15这个数在不在，只用判断这个整形的第15个比特位是0还是1，是0，分析不在，是1分析在，假如我们要插入17，只用把这个整形的第17个比特位置设置为1即可。
由于C++没有一个比特的数据范例，因此这个地方我们用char大概int都是可以的，区别在于差异范例存储的比特位个数差异，这个地方我们就用整形了。
那假如我们要插入一个数是99呢？一个整形只有32个比特位呀，那我们搞一个整形数组即可。我们可以用99 / 32盘算这个数在数组的哪一个下标，然后用99 % 32盘算在该下标所对应整形的第几个比特位。99/32=3，因此对应下标为3的整形，99%32=3，因此映射到了该整形的第3个比特位。

干系位运算 

位图肯定是必要位运算的，因此我们必要知道一些位运算的知识。
将整形n的第x个比特位标志为1
比如说要把9的第3个比特位标志为1，我们先让9 | 1左移3位
用代码写出来就是 9 | (1 << 3) ，抽象一下就是 n | (1 << x)。
或运算的特性是有1就为1，全0才是0。1左移3位后，第3个比特位是1，然后与9举行或运算，由于或运算的特性，因此9的第3个比特位肯定是1，然后9的其他位与0举行或运算，假如是1就是1，假如是0就是0，可以包管别的位稳定，次数就把9的第三位酿成了1。

将整形n的第x个比特位标志为0
比如说要把9的第4个比特位标志为0，我们可以让9与上1左移4位取反。
代码写出来是 n = n &(~(1 << x))
与运算的特性是全1为1，有0为0，1左移4位后第4个比特位是1，别的是0，取反后第4个比特位是0，别的位满是1，别的位满是1的环境下和9举行与运算，别的位稳定，然而1的第4位是0，不管9的第4位是0还是1都是0,。

获取整形n的第x个比特位是0还是1
直接让n & (1 << x)，假如效果是0该为就是0，否则是1。1左移x位，第x位为1，别的位满是0，和n举行与运算，别的位全都会酿成0，假如n的第x位是1，那么效果就是大于1的，假如n的第x位是0，那么0 & 1效果是0。
位图

位图的底层我们可以直接用一个vector数组来实现，位图也是一种哈希，因此我们要提前给位图开好空间。而且位图是不可以动态扩容的，必要我们一次就把空间开好，固然也可以动态扩容，但是扩容之后大概会导致索引发生变革，还是很贫苦的，因此末了直接一次开好就行。

2. // 非类型模版参数
3. template <size_t N>
4. class bitset
5. {
6. public:
7.     // 构造函数
8.     bitset()
9.     {
10.         _bits.resize(N / 32 + 1, 0);
11.     }
13. private:
14.     vector<int> _bits; // 位图;
15. };

复制代码

我们可以通过模版参数的方式来给位图开空间，模版参数通报这个位图必要存储的最大值，由于1个整形可以存32个数，因此我们实际上并不必要开N个空间，只必要N / 32 + 1个空间即可，由于有大概N不是32的倍数除不尽，因此要多开一个空间给那些余数。
设置位（插入）

当要插入一个数的时间，只必要盘算出该位地点的整形以及地点的比特位，盘算地点的整形直接 / 32即可，盘算在哪个比特位 % 32即可，然后把该位设置为1即可。

2.     // 设置位
3.     void set(size_t x)
4.     {
5.         // 计算出在第i个整形的第j位
6.         int i = x / 32;
7.         int j = x % 32;
8.         _bit[i] |= (1 << j); // 将该位设置为1，不影响其它位
9.     }

复制代码

打扫位（删除）

当要把一个数从位图删除，同样盘算出在哪个整形哪个比特位，然后将该位置0即可

2.     // 清除位
3.     void reset(size_t x)
4.     {
5.         // 计算出在第i个整形的第j位
6.         int i = x / 32;
7.         int j = x % 32;
8.         _bit[i] &= (~(1 << j)); // 将该位设置为0，不影响其它位
9.     }

复制代码

获取位是0还是1（查找）

2.     // 获取位的状态
3.     bool test(size_t pos)
4.     {
5.         int i = pos / 32;
6.         int j = pos % 32;
7.         if(_bits[i] & (1 << j)) // 该位被设置
8.             return true;
9.         else
10.             return false;
11.     }

复制代码

但是如今有一个标题，位图简直可以办理一个数存在不存在，但假如我这个数是负数呢？假如一个数是负数我们着实可以通过映射等方法将其转成一个整数在举行映射，但是用到的不多。
但是假如我们要快速查询一个字符串在不在呢？如今的位图是办理不了的，这就必要引入下一个数据布局叫做布隆过滤器，布隆过滤器可以快速判断字符串在不在，而且也是接纳位图的情势。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告