Redis-布隆过滤器（Bloom Filter）

一、什么是布隆过滤器
布隆过滤器，Bloom Filter是1970年由Bloom提出的，它是由一组哈希（Hash）函数和一个位阵列组成。布隆过滤器可以用于查询一个元素是否存在于一个集合当中，查询结果为以下二者之一：

这个元素可能存在于这个集合当中。
这个元素一定不存在于这个集合当中。
布隆过滤器的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
其他问题由于错误率影响hash函数的数量，当hash函数越多，每次插入、查询需做的hash操作就越多。
布隆过滤器在实际中主要用来解决网页URL去重复，垃圾邮件检测，大集合中重复元素判断和缓存击穿等问题。
二、布隆过滤器
数据结构：
布隆过滤器是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。

对于长度为 m 的位数组，在初始状态时，它所有位置都被置为0
增加元素：
当一个元素加入布隆过滤器中的时候，会进行如下操作：

使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值)
根据得到的哈希值，在位数组中把对应下标的值置为 1

用哈希计算来判断是否存在总是避免不了哈希碰撞，降低碰撞概率有两个方法
1.增加哈希函数
2.增加位数组容量
可以通过下面这个网站技术需要多少哈希函数和位数组容量达到多少的容错率
https://hur.st/bloomfilter/?n=1000000&p=0.03&m=&k=
删除元素：
布隆过滤器不支持元素的删除，会出现问题删除的哈希点位可能是别的元素依赖的点，删除后导致缓存无法命中。
可以使用定期重建布隆过滤器来规避这个问题。