海量数据如何解决？位图和布隆过滤器来帮你
位图的介绍
下面有这样一个场景：给定40亿个数，现在要找这当中的一个数，如何寻找？
- 遍历，一个一个进行比对
- 排序 + 二分进行查找
- 位图
在使用位图前，要先明确计算机中的大小是如何计算的
1 Byte = 8 Bits
1 KB = 1024 Bytes
1 MB = 1024 KB
1 GB = 1024 MB
按照上面的换算关系，我们可以大致的算一下，1GB大约是10亿字节
那么在这个情景下，很明显，哪怕这40亿个数都不一样，也仅仅占用了40亿个比特位，也只是500MB左右的量级
位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的
位图的实现
template<size_t N> class bitset { public: bitset() { _bs.resize(N / 32 + 1); } // 将x这个数字对应的位置为1 void set(size_t x) { size_t i = x / 32; size_t j = x % 32; _bs[i] |= (1 << j); } // 将x这个数字对应的位置为0 void reset(size_t x) { size_t i = x / 32; size_t j = x % 32; _bs[i] &= (~(1 << j)); } // 查看x这个数字是否存在，存在返回1，否则返回0 bool test(size_t x) { size_t i = x / 32; size_t j = x % 32; return _bs[i] & (1 << j); } private: std::vector<int> _bs; };从上面的代码可以看出，位图的实现逻辑是非常简单的，只需要通过位运算就可以实现对数字状态的存储
位图的注意点
在使用标准库中的bitset的时候无法开大位图，因为vs等IDE有些在实现标准库的时候使用的是静态数组，开大的位图的时候可能会直接栈溢出，所以在使用的时候最好直接开到对上，防止程序直接崩溃掉，为了防止忘记delete，直接使用智能指针管理起来
#include <memory> std::unique_ptr<std::bitset<10000>> bs = std::make_unique<std::bitset<10000>>();
位图的应用
- 快速查找某个数据是否在一个集合中
- 排序 + 去重
- 求两个集合的交集、并集等
- 操作系统中磁盘块标记
看到这里想必大家会觉得位图简直是查找利器O(1)的查找效率确实非常快，但是位图的缺点也是非常的明显，只能对整型进行查找，这样让其它类型的伙伴怎么办呢？别急，布隆过滤器来拯救你！！！
布隆过滤器介绍
什么是布隆过滤器？
简单来说，布隆过滤器是一种概率性数据结构，它的优点体现在高效的插入和查询中，用来表明这个东西一定不存在或者可能存在的问题，它的底层是用多个哈希函数，将一个数据映射到多个位图中，这样可以提高查找效率，也能节省空间
布隆过滤器的查找
布隆过滤器的查找与位图的查找极为相似，不同的是，因为位图只能存储整型，所以布隆过滤器需要先将传进来的数据通过多个哈希函数，将其转化为多个整型值，将位图上这些整型值都置为1，代表这个数据存在，查找的时候，通过相同的哈希函数进行映射，看看所有位是否都为1，有一个不为1，则可以确定，这个数据一定不存在
布隆过滤器的误判情况
有下面的误判情况，比如说，现在有三个哈希函数，如果去这三个哈希函数对应的哈希值来到布隆过滤器中查找，会出现一些情况：如果有一个为0，那么绝对可以说明这个值是不存在的，但是反之却不能这么说，如果全都存在，也依旧会有不存在的可能，可能程序计算出的哈希值已经被映射过了，这样去对应得到的结果也依旧是存在的，但是很显然它本身是不存在的，所以布隆过滤器是存在误判的现象的
因此，使用合适的哈希函数可以尽可能的把误判的情况减少，减少它出现的概率，但是想要真正的出现一次都不进行误判还是有一定的难度，只能是尽可能的降低这种情况出现的概率与可能性
布隆过滤器的删除
看完上面的查找与误判情况，大体上我们也能感觉出来，布隆过滤器的删除是有问题的，因为存在无判定情况，所以我们很可能在删除一个元素的时候，这个元素并不存在，但是我们将它所映射出来的位图位置置为1，就会导致后面想查找一个存在的数据时可能显示不存在。
解决⽅案：可以考虑计数标记的⽅式，加入引用计数，⼀个位置⽤多个位标记，记录映射这个位的计数值，删除时， 仅仅减减计数，那么就可以某种程度⽀持删除。但是这个⽅案也有缺陷，如果⼀个值不在布隆过滤器中，我们去删除，减减了映射位的计数，那么会影响已存在的值，也就是说，⼀个确定存在的值，可能会变成不存在，这⾥就很坑。当然也有⼈提出，我们可以考虑计数⽅式⽀持删除，但是定期重建⼀ 下布隆过滤器，这样也是⼀种思路。
布隆过滤器的缺陷
- 不能确定这个元素是不是真正的存在于布隆过滤器中
- 可能存在计数回绕的问题
布隆过滤器的优点
- 可以完全确定一个不存在的数据
- 布隆过滤器的优点还是很明显的，它的优点主要就是体现在查找相当快，只需要根据哈希函数计算出哈希值然后进行比对就可以了
- 布隆过滤器不需要存储元素本身，它存储的是这个元素所对应的哈希值，因此对于隐秘数据可以做很好的保护
- 如果可以接受一定程度的误判的情况下，过滤器还是比其他的数据结构的比对要方便很多
- 数据量很大的时候，布隆过滤器可以表示全集
- 使用同一组散列函数的布隆过滤器可以进行交并差集运算
布隆过滤器的实现
struct HashFuncBKDR { size_t operator()(const std::string& s) { size_t hash = 0; for (auto ch : s) { hash *= 31; hash += ch; } return hash; } }; struct HashFuncAP { size_t operator()(const std::string& s) { size_t hash = 0; for (size_t i = 0; i < s.size(); i++) { if ((i & 1) == 0) { hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5))); } } return hash; } }; struct HashFuncDJB { size_t operator()(const std::string& s) { size_t hash = 5381; for (auto ch : s) { hash = hash * 33 ^ ch; } return hash; } }; template<size_t N, size_t X = 5, class K = std::string, class Hash1 = HashFuncBKDR, class Hash2 = HashFuncAP, class Hash3 = HashFuncDJB> class bloomfilter { public: void Set(const K& key) { size_t hash1 = Hash1()(key) % M; size_t hash2 = Hash2()(key) % M; size_t hash3 = Hash3()(key) % M; _bs.set(hash1); _bs.set(hash2); _bs.set(hash3); } bool Test(const K& key) { size_t hash1 = Hash1()(key) % M; if (!_bs.test(hash1)) { return false; } size_t hash2 = Hash2()(key) % M; if (!_bs.test(hash2)) { return false; } size_t hash3 = Hash3()(key) % M; if (!_bs.test(hash3)) { return false; } return true; // 可能存在误判 } // 获取公式计算出的误判率 double getFalseProbability() { double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0); return p; } private: static const size_t M = N * X; std::bitset<M> _bs; };上述代码中N代表的是插入布隆过滤器元素的个数X代表的是为每一个元素所分配的位大小M代表的是位图的总位数最后的计算误判率，也是有严格的数学证明的，有兴趣的朋友可以去了解一下。
位图和布隆过滤器的应用
位图的实际应用
给定100亿个数字，请设计算法找出只出现一次的整数
- 对于这个题目，我们在位图的设计模式上稍加思考即可得到答案，可以使用两个位图来表示一个数字出现的次数，让第一个位图表示低位，第二个位图表述高位，只有当一个数字只有第一个位图（低位）中存在，第二个位图（高位）中不存在的时候，说明这个数字只出现了一次，在实际代码中使用 00、01、10、11 来分别表示这个数字的出现次数，需要注意的是我们开的不是100亿个比特位，而是开整型大小，因为即使是100亿个数字，但是数字最大的也就是 2^32 次方，所以在开位图的时候，大小只用开整型的大小即可（开范围不开数据量）
给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件的交集
- 大体思路与上一个问题一致，将两个文件的内容分别读到两个位图中，然后遍历两个位图，找交集即可
一个⽂件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数
- 与第一个问题考法一致，就是在具体判断的时候判断高位图即可
布隆过滤器实际应用
⾸先我们分析⼀下布隆过滤器的优缺点： 优点：效率⾼，节省空间，相⽐位图，可以适⽤于各种类型的标记过滤 缺点：存在误判(在是不准确的，不在是准确的)，不好⽀持删除
爬⾍系统中URL去重：
- 在爬⾍系统中，为了避免重复爬取相同的URL，可以使⽤布隆过滤器来进⾏URL去重。爬取到的URL可 以通过布隆过滤器进⾏判断，已经存在的URL则可以直接忽略，避免重复的⽹络请求和数据处理。
垃圾邮件过滤：
- 在垃圾邮件过滤系统中，布隆过滤器可以⽤来判断邮件是否是垃圾邮件。系统可以将已知的垃圾邮件的特征信息存储在布隆过滤器中，当新的邮件到达时，可以通过布隆过滤器快速判断是否为垃圾邮件，从⽽提⾼过滤的效率。
预防缓存穿透：
- 在分布式缓存系统中，布隆过滤器可以⽤来解决缓存穿透的问题。缓存穿透是指恶意⽤⼾请求⼀个不存在的数据，导致请求直接访问数据库，造成数据库压⼒过⼤。布隆过滤器可以先判断请求的数据是 否存在于布隆过滤器中，如果不存在，直接返回不存在，避免对数据库的⽆效查询。
对数据库查询提效
- 在数据库中，布隆过滤器可以⽤来加速查询操作。例如：⼀个app要快速判断⼀个电话号码是否注册过，可以使⽤布隆过滤器来判断⼀个⽤⼾电话号码是否存在于表中，如果不存在，可以直接返回不存 在，避免对数据库进⾏⽆⽤的查询操作。如果在，再去数据库查询进⾏⼆次确认。
 ；CSNLSTCVLGKLSQELHKLQTYPRTNTGSGTP-NH₂)
 Debugger可视化调试：从数据到图形的嵌入式开发利器)
