电商网站开发设计方法,营销手段,沈阳网站建设工作室,wordpress 管理后台#x1f466;个人主页#xff1a;Weraphael ✍#x1f3fb;作者简介#xff1a;目前学习C和算法 ✈️专栏#xff1a;C航路 #x1f40b; 希望大家多多支持#xff0c;咱一起进步#xff01;#x1f601; 如果文章对你有帮助的话 欢迎 评论#x1f4ac; 点赞#x1… 个人主页Weraphael ✍作者简介目前学习C和算法 ✈️专栏C航路 希望大家多多支持咱一起进步 如果文章对你有帮助的话 欢迎 评论 点赞 收藏 加关注✨ 目录 一、问题引入二、布隆过滤器的概念三、布隆过滤器的实现3.1 基本结构3.2 插入3.3 查找3.4 删除3.5 测试3.6 优化 四、总结五、代码 一、问题引入
随着玩王者荣耀的用户越来越多想要取一个心悦的名字是非常难的。当名字重复的时候系统非常快的提示“名字已被使用”那么它是如何做到快速查找名字是否被使用了呢 在如此大的数据下首先可以想到使用位图 但由于位图的数据必须是size_t的那么需要先将名字字符串映射成整型然后再存入位图中。然而我们对位图开空间是根据数据范围的但字符串的长度是可变的使用位图来表示长度不固定的数据会带来很大的挑战。比如开少了可能引发冲突那么就会导致误判。比如说李白和百里都占同一个比特位并且都标记成1当有人将修改了百里这一名称那么其实就是reset操作那么李白也同样会被reset那么就会有第二个人可以取李白这个名字。 并且字符串在计算机中是以字符集编码的方式存储的一个字符可能由一个或多个字节组成。而位图一般用于表示集合中元素的存在与否对于字符集编码来说字符的种类和编码范围非常广泛使用位图来表示所有可能的字符将需要非常大的存储空间并且不实际。
这时候就需要我们本文中的主角 布隆过滤器Bloomfilter
二、布隆过滤器的概念
布隆过滤器是由布隆在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询。可以用来告诉你 “某样东西一定不存在或者可能存在”
布隆过滤器是如何做到的呢
这里举一个小故事假设布隆有一天要去线下见网友前提是他不知道网友的任何特征那怎么办只能发一个消息问对方今天的穿搭而网友说今天带了一个黑色的帽子然而布隆一眼望去今天穿戴黑色帽子的人也特别的多于是再次向网友询问更多的特征来过滤掉更多穿搭相识的人。
于是布隆过滤器就是 使用多个哈希函数将一个数据映射到位图结构中也就是 一个数据映射位图的多个位置哈希与位图结合即布隆过滤器)。只有当映射的比特位全为1则说明字符串存在。 三、布隆过滤器的实现
3.1 基本结构
既然需要多个哈希函数这里我只模板中添加三个哈希函数的模板参数以及待存储的数据类型不过布隆过滤器最常见存储的类型是字符串所以可以给一个缺省值。 显然这三个 哈希函数 的选择是十分重要的我们在这里提供三种较为优秀的哈希函数字符串哈希算法分别是 BKDRHash、APHash 以及 DJBHash struct BKDRHash
{size_t operator()(const string str){register size_t hash 0;for (auto ch : str){hash hash * 131 (size_t)ch; }return hash;}
};struct APHash
{size_t operator()(const string str){size_t hash 0;for (auto e : str){if (((size_t)e 1) 0){hash ^ ((hash 7) ^ (size_t)e ^ (hash 3));}else{hash ^ (~((hash 11) ^ (size_t)e ^ (hash 5)));}}return hash;}
};struct DJBHash
{size_t operator()(const string str){if (str.empty())return 0;size_t hash 5381;for (auto e : str){hash (hash 5) (size_t)e;}return hash;}
};templatesize_t N, class K string, class Hashfunc1 BKDRHash, class Hashfunc2 APHash, class Hashfunc3 DJBHash
class bloomfilter
{
public:private:bitsetN _bt;
};3.2 插入
步骤 通过三个哈希函数计算不同的哈希值 最后再调用bitset中的set在位图中标记即可 3.3 查找
判断在不在也非常简单我们可以再次计算出三个哈希值只要它们对应的二进制位上是1说明要查找的字符串存在只要有一个为0说明要查找的字符串一定不存在。 这里需要注意的是布隆过滤器判断不在是准确的判断 在是不准确的
比如“李白“映射了位置0 1 3”百里“映射了位置3 5 7虽然这两个字符串不会相互影响但原本”妲己“不存在位图中并且通过调用test发现三个位置都是1那么就会误判存在。 因此 布隆过滤器并不是非常可靠那该怎么办呢有人想到了使用 布隆过滤器 数据库 的方式进行双重验证
如果 布隆过滤器 判断字符串不存在那么就是真的不存在因为这是绝对准确的但如果在布隆过滤器中存在可以去数据库里搜索再反馈给用户。
3.4 删除
布隆过滤器支持删除吗其实一般是不支持的。因为支持删除会存在重大问题删除一个值会影响其他字符串。 虽然成功删除了 “李白”但同时也影响了 “百里”当要验证“百里”是否存在时会被判断为不存在所以布隆过滤器一般是不支持删除操作的。
3.5 测试 3.6 优化
如果真的误判存在了那该怎么办呢有的人想增加哈希函数的个数那么问题来了增加多少个合适呢
还有一个比较合适的方案扩大布隆过滤器的长度使数据更分散来降低误判的概率。
那么如何选择合适的布隆过滤器的长度呢对此有大佬做出了研究 我们可以来估算一下假设用3个哈希函数即K 3ln2 的值我们取 0.7那么 m 和 n 的关系大概是 m n×k/ln24.2n 也就是过滤器长度应该是插入元素个数的 4 -5倍 四、总结
优点 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关 哈希函数相互之间没有关系方便硬件并行运算 布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势 在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势 数据量很大时布隆过滤器可以表示全集其他数据结构不能 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
缺点 有误判率不能准确判断元素是否在集合中(补救方法再建立一个白名单存储可能会误判的数据) 不能获取元素本身 一般情况下不能从布隆过滤器中删除元素
实际应用场景 注册时对于 昵称、用户名、手机号的验证 减少磁盘 IO 或者网络请求因为一旦一个值必定不存在的话我们可以不用进行后续昂贵的查询请求
五、代码
本篇博客相关代码点击跳转
