布隆过滤器

布隆过滤器是二进制向量数据结构，它具有很好的空间和时间效率，被用来检测一个元素是不是集合中的一个成员

判定可能已存在和绝对不存在两种情况。

如果检测结果为是，该元素不一定在集合中

但如果检测结果为否，该元素一定不在集合中

应用场景：

ip黑名单，爬虫url过滤， 垃圾邮件过滤，去重

实现步骤：

1、开辟一个长度为m的bit数组，可以用文件来实现

2、通过hash函数计算得到位置值，并将数组里对应的位置的二进制置为1

3、查找时，通养通过hash计算得到位置，该位置的如果都是1，可能存在，如果有0，则一定不存在

优点：

有很好的空间和时间效率

不需要存储元素本身，在某些对保密要求非常严格的场合有优势

存储空间和插入查询都是常数复杂度

缺点：

误判率会随元素的增加而增加

不能从布隆过滤器中删除元素

redis 4.0以上支持布隆过滤器