C++笔记-位图和布隆过滤器

一.位图

位图这个东西是哈希表的一个拓展部份，我们主要来看看位图用来解决什么问题以及简单实现一下。

1.1位图相关面试题

给40亿个不重复的⽆符号整数，没排过序。给⼀个⽆符号整数，如何快速判断⼀个数是否在这40亿个数中。

解题思路1：暴⼒遍历，时间复杂度O(N)，太慢。

解题思路2：排序+⼆分查找。时间复杂度消耗O(N*logN)+O(logN) 深⼊分析：解题思路2是否可⾏，我们先算算40亿个数据⼤概需要多少内存。

1G=1024MB=1024*1024KB=1024*1024*1024Byte约等于10亿多Byte。

那么40亿个整数约等于16G，并且40亿个数是⽆法直接放到内存中的，只能放到硬盘⽂件中。⽽⼆分查找只能对内存数组中的有序数据进⾏查找。

解题思路3：数据是否在给定的整型数据中，结果是在或者不在，刚好是两种状态，那么可以使⽤⼀个⼆进制⽐特位来代表数据是否存在的信息，如果⼆进制⽐特位为1，代表存在，为0代表不存在。那么我们设计⼀个⽤位表⽰数据是否存在的数据结构，这个数据结构就叫位图。

1.2位图的设计及实现

位图本质是一个直接定址法的哈希表，没个整型值映射一个bit位，位图控制这个bit的相关接口。

实现中需要注意的是，C/C++没有对应位的类型，只能看int/char这样整形类型，我们再通过位运算去控制对应的⽐特位。⽐如我们数据存到vector中，相当于每个int值映射对应的32个值，⽐如第⼀个整形映射0-31对应的位，第⼆个整形映射32-63对应的位，后⾯的以此类推，那么来了⼀个整形值 x，i=x/32；j=x%32；计算出x映射的值在vector的第i个整形数据的第j位。

解决给40亿个不重复的⽆符号整数，查找⼀个数据的问题，我们要给位图开2^32个位，注意不能开40亿个位，因为映射是按⼤⼩映射的，我们要按数据⼤⼩范围开空间，范围是是0-2^32-1，所以需要开 2^32个位。然后从⽂件中依次读取每个set到位图中，然后就可以快速判断⼀个值是否在这40亿个数中 了。

而既然要通过位运算，就要利用一些位运算符，如：&，|等符号来对整数的位进行改变，从而实现判断数据是否存在的问题。

1.3位图的实现

这里我们就实现了位图的框架，N代表位数，表示我们要开多少位来存储数据。

而位图底层我们利用vector来实现，而构造函数之所以这样写是因为我们上面也提到了没有对应位的类型，只能用int/char等类型来实现，这里我们使用int，int是4个字节，32个bit位，这样比较节省空间。

而+1是因为如果我们传的位数不能整除32，可能会不够用，比如：要开100个位，如果我们不+1，那么97及后面的数会落在第四个整数中，但是我们只开了三个空间，此时就会不够用，所以我们默认多开一个空间，这样就能解决这种问题。

位图这个数据结构我们的核心是set，reset和test这三个接口，对应的就是插入，删除和检测。

首先讲set，前面两行就是计算这个数在那个整数的那个bit位，就是计算他的位置，主要是最后一步操作。

我们要改变一个整数的某个bit位需要用到位运算符来进行改变，而我们要实现的操作是：只改变那一个相应的bit位，不改变其他的bit位，所以我们要利用1这个数，因为它除了最后一位是1以外，其余bit位全部是0，当然也可是其他数，要保证32个bit位只有一个是1，其余全部是0，不过1是最方便的，所以就不用其他数来掩饰了。

我们上面中1 << j这步操作就是为了找到要改变的那一个bit位，将其变为这个样子：

经过左移后就可以利用当前位的1进行位运算，而我们插入的思路是：如果这个数不存在，就将其改为1；如果已经存在，就不发生变化。

所以这里我们要用到 | 进行运算，| 的效果相比我们都知道，如果我们要插入的数不存在，也就是当前的bit位为0，那么我们与此时经过左移的1进行位运算时，就会将其变为1，这点大家应该都能理解，0和1进行 | ，结果是1，1和1进行 | ，结果还是1，所以经过位运算后，只会改变对应的bit位。

这里还要解释一下为什么要<<，可能有人觉得我们又不知道哪边是高位，哪边是低位，刚才那种情况是左边是高位，右边是低位，那要是反过来不就应该是>>吗？

这里要解释一下不管左边是高位还是低位，左移都是低位向高位移动，左移不是方向，这点要注意。

下面就是reset，前面两步操作和set一样，主要还是最后一步，我们reset的思路是：如果相应的bit位是1，就要把它变成0，如果是0就保持不变。

所以我们上面的思路就不能用于reset，我们要进行这样操作：

1在进行左移之后，我们要对其进行取反操作，这样就会变成相应位为0，其余位都为1，然后进行&的位运算操作，此时我们就可以实现我们上面的思路，如果相应位为1，那么与0进行&操作后就会变为0，而其他位不管是0还是1，与1进行&操作后都会保持不变。

最后就是test，而test的思路就是与1左移后的值进行&操作，就是下面这样：

此时进行&操作，如果相应位为1，那么&操作后的值是就是一个非0的值，但是如果相应位为0，那么&操作后得到的值就为0，所以通过这种方法就可以判断一个数是否在或者不在。