一.位图位图这个东西是哈希表的一个拓展部份我们主要来看看位图用来解决什么问题以及简单实现一下。1.1位图相关面试题给40亿个不重复的⽆符号整数没排过序。给⼀个⽆符号整数如何快速判断⼀个数是否在这40亿个数中。解题思路1暴⼒遍历时间复杂度O(N)太慢。解题思路2排序⼆分查找。时间复杂度消耗O(N*logN)O(logN) 深⼊分析解题思路2是否可⾏我们先算算40亿个数据⼤概需要多少内存。1G1024MB1024*1024KB1024*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对应的位后⾯的以此类推那么来了⼀个整形值 xix/32jx%32计算出x映射的值在vector的第i个整形数据的第j位。解决给40亿个不重复的⽆符号整数查找⼀个数据的问题我们要给位图开2^32个位注意不能开40亿个位因为映射是按⼤⼩映射的我们要按数据⼤⼩范围开空间范围是是0-2^32-1所以需要开 2^32个位。然后从⽂件中依次读取每个set到位图中然后就可以快速判断⼀个值是否在这40亿个数中 了。而既然要通过位运算就要利用一些位运算符如|等符号来对整数的位进行改变从而实现判断数据是否存在的问题。1.3位图的实现这里我们就实现了位图的框架N代表位数表示我们要开多少位来存储数据。而位图底层我们利用vector来实现而构造函数之所以这样写是因为我们上面也提到了没有对应位的类型只能用int/char等类型来实现这里我们使用intint是4个字节32个bit位这样比较节省空间。而1是因为如果我们传的位数不能整除32可能会不够用比如要开100个位如果我们不1那么97及后面的数会落在第四个整数中但是我们只开了三个空间此时就会不够用所以我们默认多开一个空间这样就能解决这种问题。位图这个数据结构我们的核心是setreset和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进行 | 结果是11和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所以通过这种方法就可以判断一个数是否在或者不在。