一.位图
位图这个东西是哈希表的一个拓展部份，我们主要来看看位图用来解决什么问题以及简单实现一下。
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，所以通过这种方法就可以判断一个数是否在或者不在。
1.4C++库中的bitset
在C++库中也实现了位图这种数据结构，我们来看一下：
我们可以看到在C++库中实现了更多的一些接口，比如[]重载也实现了，一些接口想了解的可以去看一下，主要还是掌握set，reset和test这三个接口。
1.5位图相关考察题目
1.给定100亿个整数，设法找到只出现一次的整数？
2.给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
3.一个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数
这三个题呢大同小异，思路是一样的，所以这里我就拿第一题举例来解决这种问题。
第一题呢要我们找只出现一次的整数，所以我们要来计算每个数出现的次数，这里我们的解决方法是利用两个位图来实现。
比如：两个位图的对应位都为0，也就是00，就表示没有这个数，而01就表示有一个，10就表示有两个，11就表示有三个，因为这里只让我们找只出现一次的，所以没必要统计太多次数，两个位图就够。
根据上面的思路我们来实现set和get_count的接口：
实现起来就如上图所示，根据00，01，10这三种情况我们针对性地做出改变，00就只让_bs2插入数据即可；01的话就得让_bs1插入数据，并且_bs2要删除数据，这样才能变为10；10的话就直接让_bs2插入数据即可。
经过上面的操作，我们每个数据最多可记录三次。
get_count就是找到每个数的个数是多少，如果是00，那么就返回0，01就返回1，10就返回2，11就返回3，这样我们就可以实现上面的问题，再插入数据之后，遍历全部数据，通过get_count函数找到返回值为1输出即可。
经过上面的实现，我们来总结一下位图的优缺点：
优点：增删查改快，节省空间
缺点：只适用于整型
二.布隆过滤器
2.1什么是布隆过滤器
有⼀些场景下⾯，有⼤量数据需要判断是否存在，⽽这些数据不是整形，那么位图就不能使⽤了，使⽤红⿊树/哈希表等内存空间可能不够。这些场景就需要布隆过滤器来解决。
布隆过滤器是由布隆（BurtonHowardBloom）在1970年提出的⼀种紧凑型的、⽐较巧妙的概率型 数据结构，特点是⾼效地插⼊和查询，可以⽤来告诉你“某样东西⼀定不存在或者可能存在”，它是 ⽤多个哈希函数，将⼀个数据映射到位图结构中。此种⽅式不仅可以提升查询效率，也可以节省⼤量的内存空间。
布隆过滤器的思路就是把key先映射转成哈希整型值，再映射⼀个位，如果只映射⼀个位的话，冲突率会⽐较高，所以可以通过多个哈希函数映射多个位，降低冲突率。
布隆过滤器这⾥跟哈希表不⼀样，它⽆法解决哈希冲突的，因为他压根就不存储这个值，只标记映射的位。它的思路是尽可能降低哈希冲突。判断⼀个值key在是不准确的，判断⼀个值key不在是准确的。
为什么说是不准确的呢？因为如果两个数据经过哈希函数后值是相同的，但是如果只有一个数据存进去了，另一个数据没有存，那么在判断两个数据是否存在时就会出现误判。
2.2布隆过滤器的误判率的推导过程
这个推导过程不感兴趣的可以不看，只需要记住结论即可。
由误判率公式可知，在k⼀定的情况下，当n增加时，误判率增加，m增加时，误判率减少。
在m和n⼀定，在对误判率公式求导，误判率尽可能⼩的情况下，可以得到hash函数个数：k =(m/n) * ln2。
2.3布隆过滤器的实现
这里我们先把布隆过滤器的框架给实现一下，上面三个都是哈希函数，哈希函数的个数可以自己选择，这里我只列举了三个哈希函数来举例。
哈希函数可以自己随意设定，尽量降低重复率，上面的三个哈希函数我就是找的比较常用的一些哈希函数。
模板参数中的N指的是我们要插入数据的个数；X指的是位数和N之商，设置这个参数是因为当K一定的时候，随着插入数据的增加，冲突率也会随之升高，这时候我们就可以通过控制X来控制位数，进而控制冲突率，间接控制误判率；K就是值的数据类型，故这里我专门用一个成员变量来M来记录位数。
写完框架我们需要实现的就是set和test：
set的实现较为简单，通过三个哈希函数来映射三个不同的值，并且把这三个值都插入到位图即可，这样一个值就可以通过映射的三个值来控制。
下面就是test函数，用test函数来判断一个值是否不存在是准确的，我们通过set的操作计算出映射的三个值并检测，只要有一个为0，那么就表示这个值不存在，反之就存在，当然是存在误判的情况的。
这里为什么没有实现reset呢？
我们来看这张图，如果实现了reset，将三个映射的值都改为0，就比如上图要删除猪八戒，删完之后如果在检测孙悟空是否存在就会出现错误，明明没有删除孙悟空，但是它映射的三个之中有一个变为0。
所以布隆过滤器一般不设置reset，可能有人有这样的想法：：可以考虑计数标记的⽅式，⼀个位置⽤多个位标记，记录映射这个位的计数值，删除时， 仅仅减减计数，那么就可以某种程度⽀持删除。
但是这个⽅案也有缺陷，如果⼀个值不在布隆过滤器 中，我们去删除，减减了映射位的计数，那么会影响已存在的值，也就是说，⼀个确定存在的值，可能会变成不存在，这⾥就很坑，所以设计出的reset多多少少都会有缺陷。
我们来总结一下布隆过滤器的优缺点：
优点：效率⾼，节省空间，相⽐位图，可以适⽤于各种类型的标记过滤
缺点：存在误判(在是不准确的，不在是准确的)，不好⽀持删除
以上就是位图和布隆过滤器的内容