58同城网站建设要多少钱,哪个平台推广效果好,网站主页布局,免费相册视频制作软件本文旨在讲解布隆过滤器的原理以及实现方式#xff0c;希望通过本文能使读者对布隆过滤器有一定的认识#xff01;
一、布隆过滤器的引入
在讲解布隆过滤器之前#xff0c;我们还是先提及一下前面讲的位图行#xff0c;位图可以处理大量的数据#xff0c;广泛用于查找等…本文旨在讲解布隆过滤器的原理以及实现方式希望通过本文能使读者对布隆过滤器有一定的认识
一、布隆过滤器的引入
在讲解布隆过滤器之前我们还是先提及一下前面讲的位图行位图可以处理大量的数据广泛用于查找等操作但是对于位图而言起能处理的类型只能是整形那么对于字符串等其他类型位图是无法处理的那么这时就引进了我们下面要讲的布隆过滤器
下面来介绍什么是布隆器正如前面说的位图不能处理字符串等类型那么我们该怎么办呢因为我们前面学习过哈希所以我们可以使用哈希的思想将字符串类型先转化为整形利用哈希将字符串转化为整形的方法有很多下面来看一下常见的几种字符串哈希算法。
字符串哈希算法
1.BKDRhash 该算法就是该字符串的每个字符的ascii码值乘上一个数然后再进行相加 2. SDBMhash 3.DJBhash 4.APhash 通过观察上述字符串哈希我们可以发现基本上都是字符串中的每一位乘上一个数然后进行获取最终结果的 。 布隆过滤器的介绍以及应用场景
既然介绍了这些字符串哈希函数那么我们就来讲一下布隆过滤器是如何诞生以及实现的上面已经提到了因为位图不能处理非整形的数据那么面对一个非整形的数据我们就需要进行一次哈希函数将其转化为整形然后再进行映射到地址中去但是对于字符串哈希函数我们很难保证没有不同的字符串对应有相同的数字此时再进行某一位的映射时就会导致误差例如
对于上图如果middle与end的对应的整形相同那么就会映射在同一块区域那么当end不存在的时候但是middle存在的时候就会导致误判误判end也存在这时有人就想出来将一个字符串对应多个哈希函数这样误判会不会结束呢答案是否定的误判是肯定不会不存在的但是会减少字符串与对应值有着多对一的关系。我们也可以发现这种误判只会出现在‘存在的情况’对于“不存在”的情况是一定准确的所以就有人说了那么发明这种东西有什么用呢这时我们的大佬布隆在发明他的时候已经想到了应用场景即其可以筛选一定的情况从而加快查找的速率
布隆过滤器的应用
我们平时都玩过游戏有很多游戏都需要用户自己定义自己的名字但是还不能有重名的情况对于游戏中所有的用户名全部都存储在服务器中的数据库中但是如果我们每次起一个名字都要去访问服务器中的数据库那岂不是太浪费时间了 上图就是我们起一个名字的时候当我们点击提交昵称的时候会自动取服务器中的数据库中进行查询如果查询到了有重复就会给用户提示改昵称已经存在了请在换个名字这时每当用户起一个名字那岂不是都得取服务器中的数据库进行查找一番么
对与此问题我们布隆大佬就想到为何不在二者之间加上一个布隆过滤器呢可以大大减少我们的查找时间呀 当添加过了布隆过滤器的时候我们可以不用访问服务器中的数据库直接通过布隆过滤器的返回结果进行判断就像我们输入昵称的时候还没有点击提交的时候昵称旁边就是出现对号或错号的提示这其实就是利用了布隆过滤器但是布隆过滤器也存在问题就是其结果只能准确的判断一个字符不存在对与存在的情况会出现误判但是这时如果有的玩家好奇心强我起了十个名字8个不能用我非得查一查这些名字都是谁在用不查不知道一查吓一跳有的昵称竟然不存在也不让我起必须反手一波举报于是针对布隆过滤器的特性我们增加一下条件即可对于布隆过滤器中返回存在的昵称因为其不一定准确所以我们将这些昵称读取到服务器中即可再次进行一次准确的检查再反馈给用户即可
这样布隆过滤器的作用就起了很大的作用大大增加了我们工作的效率其实生活中也有很多存在使用布隆过滤器的场景例如大量的数据中查询某一个人的信息如果我们暴力查找挨个去服务器中的数据库一一进行查找那么效率会非常低下此时我们就会先将标记某一个人的唯一信息例如身份证号手机号 转化为整形再对相同的整形中进行服务器内部查询即可快速完成查询信息 二、布隆过滤器的实现
既然布隆过滤器的作用以及讲解完毕接下来我们看一下布隆过滤器是如何实现的吧
对于布隆过滤器而言其本质上还是一个位图只不过该位图对应的哈希值有多个而已所以我们只需要实现set函数将其对应的多个位都set为1即可进行test的时候我们只需要将其对应的位都进行检测一波如果有false就返回false即可全为true再返回true此时我们的true也不一定是准确的因为会存在不同字符串的映射值可能相同的情况但是我们的fasle是一定准确的
下面就来看一下我们实现的布隆过滤器吧
#pragma once
//布隆过滤器的实现
//其本质上还是一个位图
#includestring
#includebitsetstruct BKDRHash
{size_t operator()(const string key){// BKDRsize_t hash 0;for (auto e : key){hash * 31;hash e;}return hash;}
};struct APHash
{size_t operator()(const string key){size_t hash 0;for (size_t i 0; i key.size(); i){char ch key[i];if ((i 1) 0){hash ^ ((hash 7) ^ ch ^ (hash 3));}else{hash ^ (~((hash 11) ^ ch ^ (hash 5)));}}return hash;}
};struct DJBHash
{size_t operator()(const string key){size_t hash 5381;for (auto ch : key){hash (hash 5) ch;}return hash;}
};templatesize_t N,class K string,class HashFunc1 BKDRHash,class HashFunc2 APHash,class HashFunc3 DJBHash
class BloomFilter
{
public://set功能 因为布隆过滤器其对应有多个映射值所以我们使用多个哈希进行位映射将对应的位置为1即可void set(const K x){size_t hash1 HashFunc1()(x)%N; //对N进行取余保证其在这些空间上防止因转化为整形过大size_t hash2 HashFunc2()(x)%N; //对N进行取余保证其在这些空间上防止因转化为整形过大size_t hash3 HashFunc3()(x)%N; //对N进行取余保证其在这些空间上防止因转化为整形过大//对三个映射的位统统进行置一处理bt.set(hash1);bt.set(hash2);bt.set(hash3);}//test功能 检测该字符是否存在只需要将其对应的位进行test即可如果有一个不存在直接返回false//当三个都存在返回true即可但是此时的true也是一种不准确的值bool test(const K key){size_t hash1 HashFunc1()(key) % N; //对N进行取余保证其在这些空间上防止因转化为整形过大size_t hash2 HashFunc2()(key) % N; //对N进行取余保证其在这些空间上防止因转化为整形过大size_t hash3 HashFunc3()(key) % N; //对N进行取余保证其在这些空间上防止因转化为整形过大if (bt.test(hash1) false){return false;}else if (bt.test(hash2) false){return false;}else if (bt.test(hash3) false){return false;}//当三者都为true时才true!但是此时的true也是一个不准确的值else if (bt.test(hash1) true bt.test(hash2) true bt.test(hash3) true){return true;}}private:std::bitsetNbt; //本质上还是一个位图
};
我们首先做的就是实现三个字符串哈希函数用于我们的字符串映射的多个值问题
细心的小伙伴们可能发现了我没有实现reset函数我为什么没有实现呢对与布隆过滤器其大多是不支持删除的因为一个字符可能对应多个哈希值某一位可能与已经存在的一位相同如果将该位删除那么与其相同的位也会删除掉这就会导致误删的现象但是我们可以使用引用计数的方法来解决reset的问题
既然我们的布隆过滤器已经实现了那么我们就简单的进行测试一下其效果吧 我们将“数据结构”set到过滤器中然后找一个与其比较相似的字符串“数据结构 ”进行测试显然其不存在于我们的过滤器中看来我们的布隆过滤器效果还是蛮不错的嘛
1.相似字符串的误判率
下面我们来看一下大量的相似字符串的误判率 2.不相似字符串的误判率
我们把数据个数N调到1000来观察一下结果 根据结果还是容易看出来相似字符串的误判率还是比较大的那么这个误判率与什么有关系呢
我把文章链接贴在下面感兴趣的小伙伴可以看一下布隆过滤器的误判率的影响详解布隆过滤器的原理使用场景和注意事项 - 知乎 (zhihu.com) 至此布隆过滤器的知识讲述完毕下面来看一下另一个知识哈希切分
三、哈希切分 我们看一道例题来引出我们哈希切分!
例1给定两个100亿的query,我们只有1G内存如何快速找到两者的交集 那么我们传统的哈希/红黑树是肯定不行的。
这时我们就可以利用hash函数将两个大文件分割成500个小文件这时平均每个小文件占1G内存然后对相互对应的小文件利用set进行求交集即可 这时就会有小伙伴问为什么要找对应的小文件呢因为我们使用的是哈希函数字符串相同的肯定会映射在同一个位置那么这时该问题不就解决了么
但是还会存在一个小问题就是当小文件中的内存还是比较大的话该怎么办呢
小文件大分两种情况
1.都是一样的字符串这时直接利用set进行去重既可以解决问题
2.不是相同的字符串这时我们只需要进行换一种哈希函数重新进行分配即可 例2给定一个超过100G的log file,log中存储着ip地址求log file中最多的ip地址
本题也是相同的道理因为是100G的文件所以我们仍然可以采用哈希切分的思想进行切分为小文件然后一一处理即可这时我们大可不必再切500个小文件我们可以切割成100个小文件平均一个小文件占1G内存。
我们通过对ip地址的哈希进行哈希切分切分成100个小文件我们的哈希函数可以是这样的
hashiHash(ip)%100;
这样相同的ip地址肯定会分到相同的小文件中这时我们对每一个小文件进行map统计次数即可 至此我们的布隆过滤器和哈希切分讲解完毕希望读完本篇文章读者能有一定的收获也希望大大多多评论留言互相讨论一波
