#NoSQL #Redis #过滤器

什么是布隆过滤器

布隆过滤器 ，下称 BF，BloomFilter。

可以把 BF 理解成一个不精确的 set 结构，当你使用 contain 方法判断某个对象是否存在时，它可能存在误判。

WARNING

当布隆过滤器说某个值存在时，这个值可能不存在，但是当它说某个值不存在时，这个值一定不存在。

而且 BF 对见过的元素不会判断失误，只有面对没有见过的元素才会有判断失误的问题。

虽然 BF 会产生误差，但是只要参数设置合理，精确度会提高很多，方法是在第一次 add 之前，需要通过 bf.reserve 指令显式创建 BF；

bf.reserve 有 三个参数

• key
• error_rate 错误率。error_rate 设置越低，需要的空间就越大；
• initial_size 预计放入的元素数量。当实际数量超过这个数字时，误判率会上升。所以初始化时设置一个较大的数值。但是也不可过大，免得浪费存储空间。

假如不使用 bf.reserve 方法显式创建，bf 默认的 error_rate 是 0.01，默认的 initial_size 是 100；

布隆过滤器的实现原理

BF 对应到 Redis 的数据结构就是一个大型的[[bitmap 位图|位数组]]和几个不一样的无偏 Hash 函数。无偏 Hash 函数就是指 hash 的时候能够把元素的 hash 值算的比较均匀，让元素被 hash 映射到位数组的位置比较随机。

添加元素时 当向 BF 中添加 key 时，会使用多个 Hash 函数对 key 进行 hash，算得一个整数索引值，然后对位数组长度进行取模运算得到一个位置，每个 Hash 函数都会算得一个不同的位置。在把位数组的这几个位置都置为 1，就完成了 add 操作。

查询元素时 当向 BF 询问 key 是否存在时，会和 add 一样，也通过这些 Hash 算法将 key 进行 hash 算得一组位置值。然后看位数组中这几个位置是否都为 1，假如至少有一个为 0，则这个 key 不存在。假如全部都是 1，也不能说明这个 key 就一定存在，只能说极有可能存在。也有几率是其他 key 存在导致的。

使用时不要让实际元素的数量远大于初始化数量。假如实际元素开始超出初始化数量时，则对 BF 进行重建，重新分配一个 size 更大的过滤器。

空间占用估计

BF 参数预计元素数量 n、错误率 f 、位数组的长度也就是需要的存储空间大小（bit）l 和 Hash 函数的最佳数量 k

• $k = 0.7*(l/n)$
• $f=0.6185^{(l/n)}$

在线 BF 计算

实际元素超出时，误判率的变化

• $f=(1-0.5^t)^k$

t 为实际元素和预计元素的倍数，k 为 Hash 函数的最佳数量

布隆过滤器的使用场景

• 新闻推送，推送给用户看的是没看过的信息；
• 爬虫过滤，爬取过得网页就不再爬取了；
• 垃圾邮件过滤；
• 其他 NoSQL 数据库领域；