概念
由一个初值都为零的bit数组和多个哈希函数构成，用来快速判断某个数据是否存在（类似set的数据结构，只是统计的结果不太准确）
特点：
- 高效的插入和查询，占用空间少，返回的结果是不确定的。
- 一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在
- 布隆过滤器可以添加元素，但是不能删除元素 因为删除元素会导致误判率增加
-
误判只会发生在过滤器没有添加过的元素，对于添加过的元素不会发生误判
布隆过滤器的使用场景：
1.缓存穿透
缓存穿透: 一般情况下，先查询缓存redis是否有该条数据，缓存中没有时，再查询数据库。当数据库也不存在该条数据时，每次查询都要访问数据库，这就是缓存穿透
当有大量请求查询数据库不存在的数据时，就会给数据库带来压力甚至会拖垮数据库
可以使用布隆过滤器解决缓存穿透的问题：
- 把已存在的数据的key存在布隆过滤器中，相当于redis前面挡着一个布隆过滤器
- 当有新的请求时，先到布隆过滤器中查询是否存在：
- 如果布隆过滤器中不存在该条数据则直接返回：
- 如果布隆过滤器已存在，才去查询缓存redis，如果redis里没查询到则穿透到数据库
2.黑名单校验
只要是邮箱在黑名单中的邮件，就识别为垃圾邮件。
把所有黑名单都放在布隆过滤器中，在收到邮件时，判断邮件地址是否在布隆过滤器中即可。
原理
- 哈希函数的概念是：将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码。
- 可能两个不同的值hash出同一个结果，导致hash碰撞
- 布隆过滤器是一种专门用来解决去重问题的高级数据结构。
- 实质上就是一个大型位数组和几个不同的hash函数。 由一个初值都为零的bit数组和多个哈希函数构成，用来快速判断某个数据是否存在。
- 查询某个变量的时候我们只要看到这些点是不是都是1，就可以大概率知道集合中有没有它了。
- 如果这些点，有任何一个为零，则被查询变量一定不在，如果都是1，则被查询变量很可能存在。
总结:
- 使用时最好不要让实际元素数量远大于初始化数量
- 当实际元素数量超过初始化数量时，应该对布隆过滤器进行重建，重新分配一个 size 更大的过滤器，再将所有的历史元素批量 add 进行
- 是否存在,–有，是很可能有—无，是肯定无,可以保证的是，如果布隆过滤器判断一个元素不在一个集合中，那这个元素一定不会在集合中
布谷鸟过滤器:
支持删除元素，布隆过滤器有以下不足：查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数
