布隆过滤器

avatar
作者
猴君
阅读量:0

布隆过滤器

布隆过滤器就是测试一个元素是否属于一个集合。

特点

空间利用率高:布隆过滤器可以用较少的空间表示较大的集合。

**快速查找:**查询操作的时间复杂度为O(k),其中k是hash function的数量。

**存在误判:**它可能认为某个不在集合中的元素在集合中,但是不会出现某个在集中的元素说不在。(缺点,元素越多,错误率越高,不支持删除(改进版本如计数布隆过滤器可能支持)

结构

布隆过滤器由一个位数组和一组独立的hash function组成。他的工作原理是:

1.**初始化:**初始化一个大小为m的位数组,所有位都设置0。选择k哥独立的hash function。

  1. 添加元素: 对于每个要添加的元素,使用k个hash function分别计算该元素的k个hash值,将这个hash 值对应的位置都设置1.
  2. 查询元素: 对于查询的元素,同样适用k个hash函数计算其k个hash值,检查这个k个位置。如果所有位置都是1.则认为该元素可能存在集合中;如果任何一个位置为0,那么这个元素一定不在集合中。
模拟实现

假设你有一个集合,用来存储一些学生的名字,你需要快速判断一个名字是否在这个集合中。

假设你要添加名字"Alex"到集合中:

  1. 你使用哈希函数A对"Alex"进行哈希运算,得到值2。

  2. 使用哈希函数B对"Alex"进行哈希运算,得到值4。

  3. 使用哈希函数C对"Alex"进行哈希运算,得到值7

    然后你把数组中第2、4、7位设为1。现在位数组可能是这样的:[0, 0, 1, 0, 1, 0, 0, 1, 0, 0]

这时候我们要查bob

  1. 使用哈希函数A对"Bob"进行哈希运算,得到值3。
  2. 使用哈希函数B对"Bob"进行哈希运算,得到值5。
  3. 使用哈希函数C对"Bob"进行哈希运算,得到值8。

然后你检查数组中第3、5、8位:

  • 第3位是0
  • 第5位是0
  • 第8位是0

说明bob不在

这时候在查alex发现

使用哈希函数A对"Alex"进行哈希运算,得到值2。

使用哈希函数B对"Alex"进行哈希运算,得到值4。

使用哈希函数C对"Alex"进行哈希运算,得到值7。

所以alex在。

使用场景

网络缓存和数据库的快速查找。

黑名单过滤

爬虫对已访问URL的记录

分布式系统中的数据同步。

为什么存在错误判定

因为多个名字的hash值可能会碰撞,导致同一个位置被设置为1.但是布隆过滤器不会漏任何在集合中的元素。

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!