登录/注册
小码仔
805
占位
0
占位
2
浏览量
占位
粉丝
占位
关注
布隆过滤器的原理及应用
小码仔
2021-10-12 17:47:17 2021-10-12
18
0

布隆过滤器是1970年由布隆提出的。他其实是一个很长的二进制向量外加一系列的随机函数函数来组成。

在正式说到布隆过滤器时,我们要先聊这样一个话题: 在解决工程类问题时,很多问题的回答并不是只有这两种布尔状态: 是 or 否 而可能是这两种状态: 一定没有 or 可能有 亦或者可能是这两种状态: 一定有 or 可能没有

针对以上的背景,我们来举这样一个例子: 已知: 从火车站打车到机场,12点出发,在不堵车的情况下,耗时约50分钟 问题1,如果12点打车出发的话,12点10分会到么? 答:一定不会 问题2,如果12点打车出发的话,12点50会到么? 答:不一定会 针对于问题1,问题2的回答,对我们来说也是有帮助的,并不是说毫无用处。 比如你要给司机打电话,询问是否到达机场,12点10分你肯定不会打电话,这样的问题没有意义,还可能会影响司机的驾驶,而12点50你可能就会打电话了,因为这时候大概率是已经到了。 布隆过滤器就是这样的一种数据结构,他不像set或者map等判定是某样东西在或者不在,(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )而是用来判定某样东西在集合中: 1,一定不存在 2,可能存在 下面我们来给出一个布隆过滤器的简单实现:

如上图 第一步,像hashmap一样,我们需要准备一个长度为N的桶 第二步,准备三个hash方法,他们会根据传入对象的key,计算出一个index值 第三步,根据计算得到的3个index值,将桶上对应的位置的值设置为1 这样一个布隆过滤器就算做好了。 如何使用呢?

如图,我们先对对象A进行hash运算,得出3个index值,更新到桶中

接着我们可能还会添加不同的对象到桶中,像下图这个样子:

然后我们依次对要检测的对象A、B、C 进行hash1(),hash2() ,hash3()的运算,再根据运算结果匹配桶中相应位置的值时候为1,从而得出下边这张图,

比如在桶中,

index:1 (为1)3(为1)6(为0),因此对象B一定不存在

index:1 (为1)3(为1)5(为1),因此A对象可能存在

这样做对我们实际业务有什么用呢?换句话说布隆过滤器有什么应用场景呢? 在回答这个问题之前,我们要首先明确一点,布隆过滤器不是业务数据的缓存,只是一个用来判断数据不存在性的缓存, 所以我们才将其称为布隆过滤器,而不是布隆缓存。 因此我们可以将其作为一个后期需要复杂操作的一个前置过滤判断,如: 1、底层的查询逻辑非常复杂,而且性能低下,可以通过布隆过滤器先过滤掉一批请求,降低后台压力。 2、 白名单安全校验:如果过滤器中判定不存在的数据可以直接设定为安全数据,直接进行安全操作,否则才会近一步的进行安全管控。

如果数据的存在性发生变化,布隆过滤器是否允许对添加过的元素删除?

传统的布隆过滤器是不允许删除的! 原因如下: 1、无法确定元素是否存在,如果是可能存在的结果,此时会导致误删。 2、即使真的确定元素是存在的,也无法删除。因为不确定对应的value是否也存在其他元素的映射。

(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ ) 应该如何设置hash函数的个数和布隆过滤器的长度呢? 很显然,如果布隆过滤器的长度设置的过小的话,很快所有的位置都会为1, 此时过滤的结果都是可能存在, 模糊结果的概率就会加大。如果设置的过大的话,则大部分空间都是0,此时又浪费了空间。 就像hashmap一样,一方面要做到不浪费空间,另外一方面要做到尽可能的降低碰撞。 所以我们需要根据hash 的个数,过滤器的长度,可能存在的元素的数量,对模糊结果的概率(误判率)得出一个估算。 总体的形式如下: 上图是误判率的计算公式。 下图是对应的概率曲线。

k为hash公式个数,m为桶数,p为误判率的,n代表数据量

这里还有一些其他方面的问题:

1、布隆过滤器是不是更浪费空间?

并没有,传统过滤器的桶是使用bit来存值的,每个槽位只占用一个1个bit位

2、多个hash之前的计算有重叠怎么办,比如hash1和hash2的运算结果相同,这样就会使碰撞的概率变大?

这里可以采用每个hash值对应一个单独的小桶(或大桶的一部分)来存放,去除掉结果重复的影响。

 

原文: https://www.cnblogs.com/jilodream/p/15130946.html

暂无评论