布隆过滤器是干什么的？

高效判断一个元素不在集合中

常见场景

1. 手机号是否重复注册
2. 用户是否参与过某秒杀活动
3. 伪造请求大量 id 查询不存在的记录，此时缓存未命中，如何避免缓存穿透
4. 网页 URL 去重
5. 大集合中重复元素的判断

针对以上问题常规做法是：查询数据库，数据库硬扛，如果压力并不大可以使用此方法，保持简单即可。

原理

布隆过滤器的原理是，当一个元素被加入集合时，通过 K 个散列函数将这个元素映射成一个位数组中的 K 个点（offset），把它们置为 1。检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了：如果这些点有任何一个 0，则被检元素一定不在；如果都是 1，则被检元素很可能在。这就是布隆过滤器的基本思想。

简单来说就是准备一个长度为 m 的位数组并初始化所有元素为 0，用 k 个散列函数对元素进行 k 次散列运算跟 len (m) 取余得到 k 个位置并将 m 中对应位置设置为 1。

布隆过滤器优缺点

优点：

空间占用极小，因为本身不存储数据而是用比特位表示数据是否存在，某种程度有保密的效果。 插入与查询时间复杂度均为 O (k)，常数级别，k 表示散列函数执行次数。 散列函数之间可以相互独立，可以在硬件指令层加速计算。

缺点：

误差（假阳性率 false positive）。

布隆过滤器可以 100% 判断元素不在集合中，但是当元素在集合中时可能存在误判，因为当元素非常多时散列函数产生的 k 位点可能会重复。

查询元素中，有可能k个hash值对应的位置都已经置一，但这都是其他元素的操作，实际上这个元素并不在布隆过滤器中，这就是false positive