本文主要是介绍C++从零开始(day54)——位图，布隆过滤器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这是关于一个普通双非本科大一学生的C++的学习记录贴
在此前，我学了一点点C语言还有简单的数据结构，如果有小伙伴想和我一起学习的，可以私信我交流分享学习资料
那么开启正题
今天分享的是关于位图， 布隆过滤器相关的知识点
1.位图
1.1位图的概念
我们先来看一道面试题：
给40亿个不重复的无符号整数，无序，给一个无符号整数，如何迅速判断一个数是否存在这40亿个数当中？
在学习哈希之前我们可能会用sort排序后二分查找，学了哈希之后可以用set或者unordered_set解决，但是这个题目用这两种方法都不行，因为空间不够，那么如何解决呢？我们来看位图的概念
位图的概念：用每一位存放某种状态，适用于海量数据，处理无重复的场景，通常来判断某个数据是否存在
位图用到了哈希的思想
1.2位图的实现
位图的实现并不难，熟练掌握位操作运算符即可轻松写出，这里直接给出
namespace wkl
{class my_set{public:my_set(size_t N){_a.resize(N / 32 + 1, 0);_num = 0;}void set(size_t x){size_t index = x / 32;size_t pos = x % 32;_a[index] |= (1 << pos);}void reset(size_t x){size_t index = x / 32;size_t pos = x % 32;_a[index] &= ~(1 << pos);}bool test(size_t x){size_t index = x / 32;size_t pos = x % 32;return _a[index] & (1 << pos);}private:vector<int> _a;size_t _num;};void Test_my_set(){my_set ms(100);ms.set(2);ms.set(4);ms.set(96);ms.set(97);ms.set(98);//ms.reset(2);for (size_t i = 0; i < 100; ++i){printf("[%d]:%d\n", i, ms.test(i));}}
}1.3位图的应用
1.快速查找某个数据是否在一个集合当中
2.排序 + 去重
3.求两个集合的交集，并集
4.操作系统中的磁盘块标记
1.4位图的优缺点
优点：节约空间，效率高
缺点：只能处理整形数据
2.布隆过滤器
2.1布隆过滤器概念
在我们刷短视频时，是如何保证推送给我们的内容没有重复推送的呢？客户端会从用户历史记录里进行筛选，过滤掉已经存在的记录，那么何如快速查找呢？
1.使用哈希表存储用户记录，缺点：浪费空间
2.用位图存储用户记录，无法记录（位图只能处理整形数据）
那么这里就要引出布隆过滤器
布隆过滤器：1970由布隆提出的一种紧凑的，巧妙地概率性数据结构，特点是高效地插入和查找，用来告诉用户某数据不存在或者可能存在，它是由多个哈希函数，将一个数据映射到位图结构中，这种方法提高了查找效率，也极大地节省了内存
2.2布隆过滤器的实现
这里不给出代码只讲其原理
a.插入
用多个哈希函数找到数据映射位置，借助于set标记存储
b.查询
找到多个哈希函数映射的值，如果全被标记则可能存在，布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判
c.删除
布隆过滤器不能直接支持删除操作，因为在删除一个元素时，可能会影响到其他元素
2.3布隆过滤器的优缺点
优点：查找效率高，节省空间
缺点：不能删除元素，有误判率，不能获取元素本身
新手写博客，有不对的位置希望大佬们能够指出，也谢谢大家能看到这里，让我们一起学习进步吧！
这篇关于C++从零开始(day54)——位图，布隆过滤器的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
