布隆过滤器的使用及原理

布隆过滤器

布隆过滤器本质是一个二进制向量,初始化的时候每一个位置都是0,可以参考下图,比如说A经过hash算法后得到一个下标位置,接下来就会把下标的值改为1,图中所示的是没一个元素经过三次hash运算,每一个箭头都是一次Hash运算,为什么要运算三次呢,这是为了减少hash冲突,当然hash算法不一定是三次,经过多次hash运算后,就把A值映射到了二进制向量中

如果布隆过滤器判断元素存在,则不一定存在,如果不存在,则一定不存在
一个值通过hash运算后得到的下标地址可能会和其他值的地址相冲突。如果经过运算后布隆过滤器判断不存在,那么说明没有一个地址是为1的,那么肯定不存在

布隆过滤器在缓存中的使用

用Google的guava包已经有了布隆过滤器算法的实现,注意的是布隆过滤器有一定的误判率,不可能达到100%的精准,首先初始化项目的时候从数据库查询出来所有的key值,然后放到布隆过滤器中,guava包都实现了相应的put方法和hash算法。

加了布隆过滤器的过程如下


1、当应用访问查询key的时候先去布隆过滤器中判断是否存在
2、如果key值在布隆过滤器中存在,则去访问redis,存在直接返回,由于布隆过滤器有一定记录误判所以不存在的时候
3、去数据库中查询,如果数据库中不存在那么就直接返回空就行

Redis中的布隆过滤器

redis 在 4.0 的版本中加入了 module 功能,布隆过滤器可以通过 module 的形式添加到 redis 中,所以使用 redis 4.0 以上的版本可以通过加载 module 来使用 redis 中的布隆过滤器
详情请查看:REDIS中布隆过滤器安装及使用

添加新评论

评论列表