布隆过滤器(Bloom Filter)

布隆过滤器用来判断一个 key 是否存在于已知集合中.

算法流程:

  1. 构建一个长度为 n 的数组,每个比特位初始化为 0
  2. 需要 k 个 hash 函数,每个函数可以把 key 散列为一个整数
  3. 插入m 个已知的 key,循环进行下面的操作
    a. 分别用 k 个 hash 函数对key 进行散列
    b. 将散列值对应的二进制位置为 1
  4. 查找 key 是否存在
    a. 分别用 k 个 hash 函数对key 进行散列
    b. 查看对应的二进制位是否都为 1

特点

  1. 只需要少量的存储空间(n)
  2. 通过布隆过滤器后也有一定的概率不存在这个 key
  3. 无法删除
  4. 判断key 是否 一定不存在 或 可能存在

典型应用场景:
分布式缓存中,如果 redis 缓存没有命中就需要访问数据库,但如果请求不存在的数据(也就是缓存穿透),那么每次攻击都会请求数据库,使得数据库的压力过大.可以在数据库和 redis 中构建一个布隆过滤器,需要访问数据库时先要通过布隆过滤器,这就可以解决缓存穿透问题.

False positives

假设 Hash 函数以等概率选择并设置 Bit Array中的某一位,m 是该数组的大小,k 是 hash 函数的个数

某一特定位在一次操作后为'0'的概率是

1 - \frac{1}{m}

某一特定位在k 次hash 操作后为'0'
(1 - \frac{1}{m})^k

插入了 n 个元素,某一特定位仍然为'0'
(1 - \frac{1}{m})^{kn}

该位为 '1'的概率为
1- [1 - \frac{1}{m}]^{kn}

某一元素被错误的认为在集合中的概率
(1- [1 - \frac{1}{m}]^{kn})^k

可以看出随着 m 的增加,False positives 的概率会下降,随着插入元素 n 的增加,False positives 的概率会上升

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容