现在大多主流计算机的内存差不多在16个g左右，然而互联网的用户体量很大数据动不动就是用亿来计算的，对这些数据进行查找或者从中提取一些有用的信息，若能用一般的数据结构比如哈希或者树形结构需要占据很大的内存，按一个整形4字节那么40一个整形需要占用近15g左右空间，比如提出一个问题：如何在40亿个整形中找出那些数字存在，而哪些不存在，若是按照常规将所有数据在内存中查找，16g的内存也会熬不住，因为还有别的程序在跑。所以位图就有了很大的用处。
位图：一个用比特位在存放数据的数据结构，只不过存进去后能用的功能有限，只能存入，取出，和查找这个数在不在，因为它是用比特位的序列来存放整形，比如存入90这个数就将一个数组的第九十个比特位置为一，表示存入。若要查找90就检测类成员数组的第九十个比特位是否为一。
因为位图只能存放整形所以不需要模板直接定义一个类，其中类成员变量是一个类型为int的vector，再加一个计数器表示存入了多少数据。默认有参构造就是需要放多少数据就传参多少，析构函数：内置类型vector自己析构；
需要注意的是：因为vector是整形类型，而我们需要的是比特位，所以要先计算出需要的比特位换算成整形需要多少空间就在默认构造函数开多少空间，但是肯定不能完全开满没所以一般若是开一百个空间，就用resize（）函数开一百除32再加1的空间。
首先插入数据：若要插入50，就先用50除以32找第五十个比特位所在的整形在vector中的哪个位置，因为一个整形占4个字节也就是32个比特位，整除的余数就是第几个比特位了，用出来找到数组中整数的位置，用取余得到帝即位，所以50除以32得1余18，表示在vector中第二个整形的第十八位，可以用1左移（向大端移动一位）18位得到的数字按位或使vector中第二个数字的第十八位在不影响其他比特位的情况下将其0置为1，若原本18位是零，按位或1是1，若是1按位或1还是1，此时表示50这个数据存入位图中。
删除：与上面的插入前两步一样,找到位置，将其特定位变为0，此时就要先将1左移特定位再取反，然后按位与，置为零了，因为若原本那一位是0，0与0是零，若原本是1，0与1还是0.
查找在不在：找到特定位判断是零还是一就好。
位图的基本功能就完成了，可以看到，若将40亿数据存入位图大概占用476mb左右空间，很小了，而且算的也快。
但是在平时计算机处理中，并不只是找一找整形，而是大部分时间都是在匹配字符串，所以需要让位图也适用于字符串，但是字符串并不能像整型那样存放，所以可以考虑先将字符串转换为整形再存入，但是在转换的过程中不免存在冲突，例如qjw和xrh这两这字符串。若按照将各个字符的ascll码相加来转整型，就会转成一样的数据导致误判，所以不妨设计多个函数转换成不同的整形存入，以此来减小冲突于是有了布隆过滤器：
布隆过滤器：底层为位图的一种数据结构，可以存入大量的字符串并且快速的判断字符串是否存在，同时也有着较高的准确度，若布隆过滤器给出的查找结果是不存在则一定是准确的若结果是存在，这个准确度与存入的数据和表的长度有关。
首先过滤器的底层是一个位图，然后有着四个模板参数，一个是关键字，剩下三个是仿函数，用来将特定类型转换成整型存入位图，为什么需要3个呢，也不一定是三个，也可以是4个5个，越多数据就越准确，随之而来的就是大量的空间浪费，因为每多一个函数就代表着多往位图中存一个数据。
构造函数传入大概要存入多少个字符串就给位图通常开辟5倍大小的空间，是为了减小冲突。网上也是有人经过计算得出的结论，这里直接用了。
首先先实现3个仿函数：每个函数都用不同的算法将字符串转化为不同的整形，所以每个字符串有着3个位图的位置，当存入是对应的3个位都会置为一，查找时一个为零就表示这个字符串不存在。
但是没有删除这个功能因为，一个比特位上的1可能是两个字符串共同的结果，如果将这一位值为零，也可能将影响另一个。
可以看到，要存放一个字符串需要将其转换的3个整形全部放入位图中，当查找时一个对不上就表示一定对不上，但是当数据多了以后，可能本来没有的数据也会被误判有，可能被误判的数据的3个整型位位被其他插入的字符串占据了，所以空间越大越不容易重复，同时也伴随着空间浪费。
tips：我们知道c++中对类名+（）可以匿名构造一个实例化对象，只不过这个实例化对象生命周期很短，只有一行，上图中用Hash（）实例化了一个仿函数，再加一个括号调用字符串转整形的函数。
布隆过滤器的优点：高效，节省空间，可以标记任意类型，缺点：不能删除且不能保证百分百准却。
位图应用：找出100亿个整形中只出现过一次的数据。可以用位图解决，给每个数有三个标记，没出现过，出现过一次，和出现过一次以上，最后遍历输出出现过一次的数，
有两种方法：
1：用一个位图中的两位表示一个数，所以可以有4种状态00.01.10.11.只用三种就可以完成这个问题了。需要在开辟默认构造函数时将除数乘2因为用两个比特位表示一个数比起之前需要多开一倍的空间，在求vector的整型位置时除16，并且取余16后在移位时乘二，找到第一个比特位，在多移一位找到第二个。
2：用一个类将两个位图封装以来，两个位图可以有四种状态，思路与上面一样：
标签：日位,比特,数据,布隆,存入,字符串,vector,过滤器,整形 From： https://www.cnblogs.com/qjwxlj/p/17381057.html