5分钟教你认识布隆过滤器

前言：

当我们谈论到redis缓存穿透问题的时候，其中一个解决方法就是使用布隆过滤去，那么布隆过滤器到底是什么呢？ 关注公主号thisjava，今天就带大家初识布隆过滤器

正文：

什么是布隆过滤器？

布隆过滤器，简单理解就是一个固定大小的位图（bitmap）和映射函数构成。在初始状态下所有的位置都是0。我们一般是在某个需要去判断是否重复的业务场景去使用布隆过滤器。

布隆过滤器的原理

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]假设我们初始化一个固定长度的布隆过滤器，假设一个变量进入布隆过滤器，我们将使用k个映射函数将这个变量映射进bitmap并且把0变成1.[0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0]在查询这个变量是否存在的时候，只需要判断是否有1，如果这个变量进行函数后所有的位置都是1，那么说明该变量有可能存在如果有0，那么该变量肯定不存在

为什么布隆过滤器说存在，那么是可能存在

如果多个变量进入了一定大小的布隆过滤器，就会存在一定概率的误判假设：[1,0,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,1,0,1,0]假设此时我进入一个变量，在进行函数运算后得到的位数是1,4,6那么4,6的位置是本来已经就是1了，无法判断究竟是哪个变量输入的，这就是导致误判的原因。

为什么布隆过滤器说不存在，那么是一定不存在

当我们用布隆过滤器进行过滤的时候，如果查询到其中一位的值为0，说明在这个布隆过滤器的bitmap中从来没有变量在函数运算后使该位置变为1，所以我们就确定该变量是肯定不存在的。

布隆过滤器的优点

我们使用布隆过滤器最常见的用处就是查看是否重复，像平常使用hashmap或者hashset是可以去实现的，但是在数据量非常庞大的时候，使用hashmap或者hashset占用的存储空间都是很大的。相反布隆过滤器占用的空间就很小，因为他是bitmap位图实现的。布隆过滤器插入查询的效率也很高。

布隆过滤器的缺点

布隆过滤器的缺点就是，有一定误判的概率。布隆过滤器不能去删除元素。我们只能去开新的bitmap去使用

对于布隆过滤器，无法删除，有两个解决办法，一个是计数布隆过滤器，另一个就是布谷鸟过滤器，在文末做补充。

布隆过滤器的使用场景

redis缓存穿透问题：大量查询不存在数据库的数据，用布隆过滤器就可以直接屏蔽这些查询，避免并发打进数据库黑白名单校验判断用户是否有某些浏览记录等等

拓展：计数布隆过滤器

为了解决布隆过滤器无法删除的问题，就出现了一个计数布隆过滤器或者叫做增强版布隆过滤器，这个过滤器简单来说就是原来的布隆过滤器采用bitmap，而计数过滤器使用的是数组。当变量进入布隆过滤器那么就+1，当删除时就-1.这样就解决了布隆过滤器不能删除的问题，但是这个计数过滤器依旧也还是有误判的概率

拓展：布谷鸟过滤器

布谷鸟过滤器的原理简单来说就是，一个变量进行函数运算，算出两个位置，如果有空位则插入，如果没有空位就会挤走一个指纹，并且为这个指纹重新去寻找新的位置（当然不会去无限寻找的情况，一般会设置一个阈值，超过阈值就会去扩容）布谷鸟过滤器是可以进行删除的。之后我将新开一篇文章给大家详细讲一下布谷鸟过滤器的原理。

总结

5分钟教你认识布隆过滤器，你会了吗？