布隆过滤器用来判断一个 key 是否存在于已知集合中.
算法流程:
- 构建一个长度为 n 的数组,每个比特位初始化为 0
- 需要 k 个 hash 函数,每个函数可以把 key 散列为一个整数
- 插入m 个已知的 key,循环进行下面的操作
a. 分别用 k 个 hash 函数对key 进行散列
b. 将散列值对应的二进制位置为 1 - 查找 key 是否存在
a. 分别用 k 个 hash 函数对key 进行散列
b. 查看对应的二进制位是否都为 1
特点
- 只需要少量的存储空间(n)
- 通过布隆过滤器后也有一定的概率不存在这个 key
- 无法删除
- 判断key 是否 一定不存在 或 可能存在
典型应用场景:
分布式缓存中,如果 redis 缓存没有命中就需要访问数据库,但如果请求不存在的数据(也就是缓存穿透),那么每次攻击都会请求数据库,使得数据库的压力过大.可以在数据库和 redis 中构建一个布隆过滤器,需要访问数据库时先要通过布隆过滤器,这就可以解决缓存穿透问题.
False positives
假设 Hash 函数以等概率选择并设置 Bit Array中的某一位,m 是该数组的大小,k 是 hash 函数的个数
某一特定位在一次操作后为'0'的概率是
某一特定位在k 次hash 操作后为'0'
插入了 n 个元素,某一特定位仍然为'0'
该位为 '1'的概率为
某一元素被错误的认为在集合中的概率
可以看出随着 m 的增加,False positives 的概率会下降,随着插入元素 n 的增加,False positives 的概率会上升
