2019-11-21 布隆过滤器

https://blog.csdn.net/tlk20071/article/details/78336407

布隆过滤器的巨大用处就是，能够迅速判断一个元素是否在一个集合中。因此他有如下三个使用场景:

1.网页爬虫对URL的去重，避免爬取相同的URL地址

2.反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信）

3.缓存穿透，将所有可能存在的数据缓存放到布隆过滤器中，当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。

我们知道检查一个元素是否在某一个集合中，使用HashSet是比较好的选择，因为在不发生Hash碰撞的情况下它的时间复杂度为常数级别，但是在数据量比较大的情况下，使用HashSet将会占用大量的内存空间

原理

其内部维护一个全为0的bit数组，需要说明的是，布隆过滤器有一个误判率的概念，误判率越低，则数组越长，所占空间越大。误判率越高则数组越小，所占的空间越小。

误判计算

优点

思路简单

保证一致性

性能强

缺点

代码复杂度增大

需要另外维护一个集合来存放缓存的Key

布隆过滤器不支持删值操作

安装使用

redis布隆过滤器的使用

Redis的布隆过滤器作为一个插件，在Redis在4.0中的提供了插件功能后才可以使用。使用前需要先安装插件。

这里主要介绍一下他的几个命令。

bf.add: 添加元素；

bf.exists: 查询元素是否存在

bf.madd: 添加多个

bf.mexists: 查询多个元素是否存在

代码参见

https://gitee.com/sohikoryuu/codeExamples/tree/master/redisbf