布隆过滤器

what

布隆过滤器(Bloom Filter).是一个很长的 二进制向量 和 一系列随机映射 函数.

之所以叫 filter,是在缓存之前,把不存在的 key 给拦截掉.

本质是 一个位数组: 位数组 就是 数组 的 每个元素 都只占用 1 bit,并且每个元素只能是 0 或 1.

用于判断: 某个元素 一定不存在 或者 可能存在 于 一个集合中.

布隆过滤器除了一个位数组,还有 K 个哈希函数.

插入

一个元素加入布隆过滤器:
使用 K 个 哈希函数 对元素值 进行 K 次计算,得到 K 个哈希值.
根据得到的哈希值,在 位数组中 把对应下标的值置为 1.

查询

当查询 w 是否存在时,可以再通过这 k 个 哈希函数,如果算出来所在的位置均为1,则表示 w 可能存在(注意是可能存在),否则一定不存在.

优缺点

1.优点
空间效率 和 查询时间 都远远超过一般的算法.

2.缺点
有一定的 误识别率 和 删除困难

数组的容量即使再大,也是有限的.

随着元素的增加,插入的元素就会越多,位数组中被置为 1 的位置因此也越多.

这就会造成一种情况:
当一个不在布隆过滤器中的元素,经过同样规则的哈希计算之后,得到的值在位数组中查询,有可能这些位置因为之前其它元素的操作先被置为 1 了.

有可能一个不存在 布隆过滤器 中的 会被误判成 在布隆过滤器中.

布隆过滤器说某个元素在,可能会被误判.
布隆过滤器说某个元素不在,那么一定不在.

Guava BloomFilter

使用api

// 初始化 BloomFilter
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.unencodedCharsFunnel(), SIZE);
// 存入数据到 BloomFilter
bloomFilter.put(data);
// 查询s是否在 BloomFilter 中
bloomFilter.mightContain(s)

Redis BloomFilter

redis 布隆过滤器的插件 rebloom

BF.ADD 向布隆过滤器中插入数据的命令,插入成功返回 true

BF.EXISTS 判断布隆过滤器中是否存在该数据命令,存在返回true

Redis 引入 BloomFilter 的原因

数据量较大时,解决缓存穿透

参考

redis bloomFilter demo

bloom filter topic