编辑
2023-10-30
缓存中间件
0
请注意,本文编写于 201 天前,最后修改于 50 天前,其中某些信息可能已经过时。

目录

布隆过滤器的原理
说说布隆过滤器的使用场景?

布隆过滤器的原理

​ 布隆过滤器是一个很长的二进制数组 + 一系列随机hash算法映射函数,主要用于判断一个元素是否在集合中。能高效的插入和查询,占用空间少,返回的结果是不确定性的。**一个元素如果判断结果为存在的时候元素不一定存在,但是判断结果为不存在时则一定不存在。**布隆过滤器可以添加元素但是不能删除元素,因为删掉元素会导致误判率增加。误判只会发生在过滤器没有添加过的元素,对于添加过的元素不会发生误判。没错就是使用Redis的Bitmap数据类型。

在添加key时:使用多个hash函数对key进行hash运算得到一个整数索引值,对位数组长度进行取模运算得到一个位置,每个hash函数会得到一个不同的位置,将这几个位置都置1就完成了add操作。

查询key时:向布隆过滤器查询某个key是否存在时,先把这个key通过相同的多个hash函数进行运算,查看对应的位置是否都为1,只要有一个位置是0,则表明不存在,如果这几个位置都为1,则说明可能存在。(因为这些位置的1可能是其他的key导致的)

​ 使用布隆过滤器时,最好不要让实际元素数量远大于初始化数量。

​ 当实际元素数量超过初始化数量时,应该对布隆过滤器进行重建,重新分配一个size更大的过滤器,再将所有的历史元素批量add进行。

​ 布隆过滤器是不能删除数据的,因为无法保证hash之后的位置没有别的key在使用(难免会出现hash冲突,多个key共用某些hash位置)。如果删除了,那么别的key也会受影响。这样会导致误判率增加。

说说布隆过滤器的使用场景?

​ 1、主要是解决缓存穿透问题

​ 把已存在的数据的key存在布隆过滤器中,相当于在redis前面挡了一层布隆过滤器。

​ 当有新的请求时,先到布隆过滤器中查询是否已经存在;

​ 如果布隆过滤器中不存在该数据则直接返回;

​ 如果布隆过滤器中已存在,才去查询缓存redis,如果redis里没有查到则到MySQL数据库中查询。

​ 2、黑名单校验

本文作者:whitebear

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!