布隆过滤器的原理及应用，2021年一起努力应对互联网寒冬吧

一定没有 or 可能有

亦或者可能是这两种状态：

一定有 or 可能没有

针对以上的背景，我们来举这样一个例子：

已知：

从火车站打车到机场，12点出发，在不堵车的情况下，耗时约50分钟

问题1，如果12点打车出发的话，12点10分会到么？

答：一定不会

问题2，如果12点打车出发的话，12点50会到么？

答：不一定会

针对于问题1，问题2的回答，对我们来说也是有帮助的，并不是说毫无用处。

比如你要给司机打电话，询问是否到达机场，12点10分你肯定不会打电话，这样的问题没有意义，还可能会影响司机的驾驶，而12点50你可能就会打电话了，因为这时候大概率是已经到了。

布隆过滤器就是这样的一种数据结构，他不像set或者map等判定是某样东西在或者不在，(防盗连接：本文首发自http://www.cnblogs.com/jilodream/ )而是用来判定某样东西在集合中：

1，一定不存在

2，可能存在

下面我们来给出一个布隆过滤器的简单实现：

如上图

第一步，像hashmap一样，我们需要准备一个长度为N的桶

第二步，准备三个hash方法，他们会根据传入对象的key，计算出一个index值

第三步，根据计算得到的3个index值，将桶上对应的位置的值设置为1

这样一个布隆过滤器就算做好了。

如何使用呢？

如图，我们先对对象A进行hash运算，得出3个index值，更新到桶中

接着我们可能还会添加不同的对象到桶中，像下图这个样子：

然后我们依次对要检测的对象A、B、C 进行hash1()，hash2() ,hash3()的运算，再根据运算结果匹配桶中相应位置的值时候为1，从而得出下边这张图，

比如在桶中，

index：1 （为1）3（为1）6（为0），因此对象B一定不存在

index：1 （为1）3（为1）5（为1），因此A对象可能存在

总结

总的来说，面试是有套路的，一面基础，二面架构，三面个人。

最后，小编这里收集整理了一些资料，其中包括面试题（含答案）、书籍、视频等。希望也能帮助想进大厂的朋友

CodeChina开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频】