版权归原作者所有。本文最后更新于：2023年12月5日凌晨

布隆过滤器

可以判断某个值是否在集合中

推荐系统去重

当压力很大时，频繁查询数据库就会有很大的压力，去重工作的性能就跟不上了

Bloom Filter

就是为了专门解决这个去重问题，在空间上还能节省90%以上的空间

只是稍微有那么点不准确，也就是有一定的误判概率

可以把布隆过滤器理解为一个不怎么精确的set结构，contains方法判断某个对方是否存在时，可能会误判，但是也不是特别不精准，只要设置参数合理，精确度也可以设置的足够精确，只会有小小的误判。

可以保证过滤掉用户已经看过的内容，但是没有看过的可能也会有极小一部分被过滤，但是大部分新内容进行准确精准识别，保证可以推荐给用户的内容是无重复的。

命令

bf.add k1 u1
bf.add k1 u2
bf.exists k1 u1
bf.madd k1 u3 u4 u5
bf.mexists k1 u3 u4 u5

错误率

误判率大约1%多一点，有点高，可以优化

redis提供了自定义参数的布隆过滤器，需要我们再add之前bf.reserve指令显示创建

如果key已经存在了，会报错

有三个参数 key error_rate((错误率) initial_size（预计放入的元素数量，当实际数量超出这个数值，误判率会上升，需要提前设置一个较大的数值避免超出导致误判率升高）
error_rate越低，需要的空间就越大

如果不显示创建，默认错误率为 0.01 默认initial_size 100

初始值设置的过大也会浪费存储空间，设置过小，会影响准确率，使用之前一定尽可能的估计元素数量，还需要加上一定量的冗余空间，避免实际元素意外高出估计值过多。

有些对于不需要过于精确的场景，错误率稍微大一点也无伤大雅。

原理

每个布隆过滤器对应Redis的数据结构就是一个大型的位数组和几个不一样的无偏hash函数

无偏就是能够把元素的hash值算的比较均匀，让元素被hash映射到位数组中的位置比较随机。

例如 hello 把 hello经过hash之后计算出hash值，通过hash值取模。得出的数值作为位数组的索引，找到对应数组位置之后，设置为1，这个时候完成了add操作

如果查询是否存在时，也是先hash进行取模获取到位数组的位置，然后判断是否为1，如果位0，则不存在，如果为1 不一定存在，因为h是index e是一个index，他是一个组合，所以，有可能很多种组合组成了一个hello的位置，造成了一个hello存在的假象，这个时候，就看出如果这个index计算的越稀疏，就越准确，越稠密越不准确。（也就是说错误率越小，占用空间越大的原因）

使用时不能让实际元素数量大于初始化适量过大，当过于大时，应该重建过滤器，重新分配一个size更大的过滤器，再将所有历史元素add进去（这就要求在其他存储中存历史元素），因为error_rate不会因为数量刚已超出就急剧增加，给我们重建过滤器提供了较为宽松的时间。

空间占用估计

简单公式：

k=0.7*(1/n)  //约等于
f=0.6185^(1/n)   // ^ 表示次方计算，也就是Math.pow()

总结

1、位数组相对越长（1/n），错误率f越低。

2、位数组相对越长，hash函数需要的最佳数量也越多，影响计算效率。

3、当一个元素需要1个字节（8bit）的指纹空间时（1/n=8）,错误率大约为2%。

4、错误率为10%时，一个元素需要平均指纹空间为4.792个bit，大约为5bit。

5、1%，9.585bit/个，~10bit

6、0.1%，14.377bit/个，大约为15bit

set和布隆过滤器空间占用说明：

set是存储的元素内容，过滤器只是元素的指纹，所以，set占用4或者8字节，取决于32位或者64位系统，本身还需要一个指针倍set集合引用，指纹空间一个元素才需要不足2个字节，所以布隆过滤器空间占用还是很有优势的。

计算地址

计算麻烦，现有在线计算器可以计算

https://krisives.github.io/bloom-calculator/

实际元素超出时，误判率会如何变化？

通过公式可以计算出实际元素超出预计元素个数是，错误的变化情况？

f=(1-0.5^t)^k // 极限近似，k是hash函数的最佳数量

当t增大时，错误率f也跟着增大，分别选择错误率为10%，1%，0.1%的k值，

1、10%，倍数比为2时，错误率回升至接近40%， 这个值就比较危险了
2、1%，倍数比为2时，-> 15% , 也挺可怕
3、0.1%，倍数比为2时，-> 5%， 也是比较高的