什么是布隆过滤器
在实际业务场景中，存在网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。而布隆过滤器就主要是用于检索一个元素是否在一个集合中。它的优点是空间效率和查询效率比较高，缺点是删除困难和有一定的误判率。
算法思想
- 通过n个hash算法对输入值分别进行hash计算
- 根据hash值来标记[[位图BitMap]]中的位置，比如hash值为5，则[[位图BitMap]]中index=5的值改为1
- 根据1可知，如果n=3，则会进行3次hash，对BitMap三个位置的值修改为1
- 对于输入的值，如果该元素任意一个hash结果在bitMap中的值为0，则表示该值在布隆过滤器中肯定不存在，只有所有hash结果在bitMap中均存在，才能表示该值在布隆过滤器中可能存在（由于hash冲突，导致不同的值，三个不同hash函数的结果依旧冲突）
算法实现
- Google开源guaua实现
- Redission实现
问题案例
布隆过滤器很重要的一个使用场景就是[[缓存穿透，缓存击穿和缓存雪崩的区别以及解决方案]]