布隆过滤器的基本思想是使用多个哈希函数将元素映射到一个大的位数组中。当需要判断一个元素是否存在时,我们对该元素进行哈希运算,并查看对应位置的位是否都为1。如果有一个位置为0,则可以确定该元素一定不存在;如果所有位置都为1,则可能存在(因为有可能是其他元素的哈希冲突),这时需要进一步检查。

布隆过滤器可以判断的是可能存在。所以存在一定的误差性。

这个误差率取决于布隆过滤器的大小和元素多少。如果取的合适误差率是非常小的。

使用场景

缓存穿透 过滤恶意/非法请求

已有海量用户 用户名注册 判断是否存在

布隆过滤器中容量的计算

先说一下各个参数的含义:

• m: 布隆过滤器中二进制 bit 数组的长度
• n :需要对多少个元素进行存储,比如说我们要存储 1000 万个用户名,那么 n = 1000 万
• p: 期望的误判率,可以设置 p = 0.001(%0.1) 或者 p = 0.0001(%0.01)

m = (n * lnp) / ((ln2)^2)

将 n、p 带入上述公式即可计算出来理想情况下布隆过滤器的二进制数组的长度,也可以根据此公式算出来存储这么多元素大概需要占用多少内存空间,比如需要存储 10 亿个用户名,期望误判率为 0.001,也就是将 n = 10亿、p = 0.001 带入,得到 m 约为 1.67GB ,因此这个布隆过滤器大约占用 1.67GB 的空间(可以搜索在线布隆过滤器容量计算)

删除

不支持删除。(基于这个结论,最好是只用于 id 的过滤或者不会发生变化的字段)

如果一定要删除。

1、重建。(bloom 本来就是解决海量数据的,重建成本太大了吧

2、加计数器。之所以不能删除,因为删 A 如果直接把 A 命中的几个位置置为 0,则会误伤和 A hash 到一样结果的 B,导致 B 也不存在了。bloom 就是判断不存的,这样 B 不存在直接就是错误了!
所以搞一个计数器。不再存 0/1 ,删除就是 -1,新增就+1
但是搞笑的是。bitmap 就是因为存 0/1 才省。现在又要存 234 ,也是本末倒置罢了!