概述
布隆过滤器是一个应用非常广泛的概率型数据结构，一般用于判断一个元素是否存在一个集合中，比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；在 缓存系统中，判断一个元素是否在缓存中；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。关于这个，只需要根据元素的数量和大小简单的计算一下就知道了。虽然可以适用分布式K-V系统（如Redis）来承载，但是成本仍然高昂。布隆过滤器只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题，以一定的误判率为代价。所需要的内存大小可以通过公式精确的计算出来：Bloom Filter Calculator。
布隆过滤器其实是一个比较简单的数据结构，不难实现，接口简单，代码也不长。已经有很多开源的实现，像谷歌的guava基础库就有实现。 布隆过滤器有许多的变种，像 Counting Bloom Filter, 可以支持删除元素。
布隆过滤器可以处理的类似问题：
垃圾邮件过滤
文字处理中的错误单词检测
网络爬虫重复URL检测
会员抽奖
判断一个元素在亿级数据中是否存在
缓存穿透
优点
它的优点是空间效率和查询时间都远远超过一般的算法，布隆过滤器存储空间和插入 / 查询时间都是常数O(k)。另外, 散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
缺点
- 随着数据的增加，误判率随之增加；；只能判断数据是否一定不存在，而无法判断数据是否一定存在。
如果数据A，经过hash1（A）、hash2（A）、hash3（A），得到其hash值1、3、5，然后我们在其二进制向量位置1、3、5设置1，然后数据B，经过hash1（B）、hash2（B）、hash3（B）,其实hash值也是1、3、5，我们在做业务处理的时候判断B是否存在的时候发现 其二进制向量位置返回1，认为其已经存在，就跳过相关业务处理，实际上根本不存在，这就是由于hash碰撞引起的问题。也就存在了误差率。
- 无法做到删除数据
一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。
布隆过滤器的三种实现
- guava单机版实现布隆过滤器
- redis分布式布隆过滤器的实现（基于guava的实现）
- Rebloom插件方式实现布隆过滤器（redis 4.0 以后）
参考链接：
https://juejin.im/post/6844903959061069831
http://arganzheng.life/bloom-filter-for-distributed-system.html
