海量数据如何解决？位图和布隆过滤器来帮你

位图的介绍下面有这样一个场景给定40亿个数现在要找这当中的一个数如何寻找遍历一个一个进行比对排序 二分进行查找位图在使用位图前要先明确计算机中的大小是如何计算的1 Byte 8 Bits1 KB 1024 Bytes1 MB 1024 KB1 GB 1024 MB按照上面的换算关系我们可以大致的算一下1GB大约是10亿字节那么在这个情景下很明显哪怕这40亿个数都不一样也仅仅占用了40亿个比特位也只是500MB左右的量级位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的位图的实现templatesize_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::vectorint _bs; };从上面的代码可以看出位图的实现逻辑是非常简单的只需要通过位运算就可以实现对数字状态的存储位图的注意点在使用标准库中的bitset的时候无法开大位图因为vs等IDE有些在实现标准库的时候使用的是静态数组开大的位图的时候可能会直接栈溢出所以在使用的时候最好直接开到对上防止程序直接崩溃掉为了防止忘记delete直接使用智能指针管理起来#include memory std::unique_ptrstd::bitset10000 bs std::make_uniquestd::bitset10000();位图的应用快速查找某个数据是否在一个集合中排序 去重求两个集合的交集、并集等操作系统中磁盘块标记看到这里想必大家会觉得位图简直是查找利器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; } }; templatesize_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::bitsetM _bs; };上述代码中N代表的是插入布隆过滤器元素的个数X代表的是为每一个元素所分配的位大小M代表的是位图的总位数最后的计算误判率也是有严格的数学证明的有兴趣的朋友可以去了解一下。位图和布隆过滤器的应用位图的实际应用给定100亿个数字请设计算法找出只出现一次的整数对于这个题目我们在位图的设计模式上稍加思考即可得到答案可以使用两个位图来表示一个数字出现的次数让第一个位图表示低位第二个位图表述高位只有当一个数字只有第一个位图低位中存在第二个位图高位中不存在的时候说明这个数字只出现了一次在实际代码中使用 00、01、10、11 来分别表示这个数字的出现次数需要注意的是我们开的不是100亿个比特位而是开整型大小因为即使是100亿个数字但是数字最大的也就是 2^32 次方所以在开位图的时候大小只用开整型的大小即可开范围不开数据量给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件的交集大体思路与上一个问题一致将两个文件的内容分别读到两个位图中然后遍历两个位图找交集即可一个⽂件有100亿个整数1G内存设计算法找到出现次数不超过2次的所有整数与第一个问题考法一致就是在具体判断的时候判断高位图即可布隆过滤器实际应用⾸先我们分析⼀下布隆过滤器的优缺点 优点效率⾼节省空间相⽐位图可以适⽤于各种类型的标记过滤 缺点存在误判(在是不准确的不在是准确的)不好⽀持删除爬⾍系统中URL去重在爬⾍系统中为了避免重复爬取相同的URL可以使⽤布隆过滤器来进⾏URL去重。爬取到的URL可 以通过布隆过滤器进⾏判断已经存在的URL则可以直接忽略避免重复的⽹络请求和数据处理。垃圾邮件过滤在垃圾邮件过滤系统中布隆过滤器可以⽤来判断邮件是否是垃圾邮件。系统可以将已知的垃圾邮件的特征信息存储在布隆过滤器中当新的邮件到达时可以通过布隆过滤器快速判断是否为垃圾邮件从⽽提⾼过滤的效率。预防缓存穿透在分布式缓存系统中布隆过滤器可以⽤来解决缓存穿透的问题。缓存穿透是指恶意⽤⼾请求⼀个不存在的数据导致请求直接访问数据库造成数据库压⼒过⼤。布隆过滤器可以先判断请求的数据是 否存在于布隆过滤器中如果不存在直接返回不存在避免对数据库的⽆效查询。对数据库查询提效在数据库中布隆过滤器可以⽤来加速查询操作。例如⼀个app要快速判断⼀个电话号码是否注册过可以使⽤布隆过滤器来判断⼀个⽤⼾电话号码是否存在于表中如果不存在可以直接返回不存 在避免对数据库进⾏⽆⽤的查询操作。如果在再去数据库查询进⾏⼆次确认。