布隆过滤器的原理及应用

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

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

针对以上的背景,我们来举这样一个例子:
已知:
从火车站打车到机场,12点出发,在不堵车的情况下,耗时约50分钟
问题1,如果12点打车出发的话,12点10分会到么?
答:一定不会
问题2,如果12点打车出发的话,12点50会到么?
答:不一定会
针对于问题1,问题2的回答,对我们来说也是有帮助的,并不是说毫无用处。
比如你要给司机打电话,询问是否到达机场,12点10分你肯定不会打电话,这样的问题没有意义,还可能会影响司机的驾驶,而12点50你可能就会打电话了,因为这时候大概率是已经到了。
布隆过滤器就是这样的一种数据结构,他不像set或者map等判定是某样东西在或者不在,
而是用来判定某样东西在集合中:
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是否也存在其他元素的映射。


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

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

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwzjxf.html