推荐阅读：
布隆过滤器的方式解决缓存穿透问题
Redis缓存击穿解决办法之bloom filter布隆过滤器
guava 中含有 BloomFilter 的实现
1、简介
布隆过滤器的巨大用处就是，能够迅速判断一个元素是否在一个集合中。
具有快速，比哈希表更节省空间等优点，而缺点在于有一定的误识别率（false-positive，假阳性），亦即，它可能会把不是集合内的元素判定为存在于集合内，不过这样的概率相当小，在大部分的生产环境中是可以接受的；
三个使用场景:
- 网页爬虫对URL的去重，避免爬取相同的URL地址
- 过滤黑名单，比如有100亿个URL的黑名单，要求对输入的URL进行检测，并判断输入的URL是否属于黑名单中的URL。
- 缓存穿透，将所有可能存在的数据缓存放到布隆过滤器中，当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。
2. 布隆过滤器的实现
(1) 建立bit数组
使用布隆过滤器，首先要建立布隆过滤器，布隆过滤器的建立需要一个bit数组，而bit数组可采用类似于位图的方式，利用基本类型的数组来实现。设bit数组的长度为m，数组中的元素全部初始化为0。
(2) 哈希函数
除了bit数组之外，实现布隆过滤器还需要一组哈希函数f1,f2,...,fn。
假设现在给定一个集合汇总的样本x，那么利用x来建立布隆过滤器时，首先要将它分别输入到f1,f2,...,fn这n个函数中，分别计算出n个哈希值，然后将这n个哈希值分别模m之后得出一个索引值，最后将bit数组中的索引值上的bit全部置位1.
(3) 使用布隆过滤器来检测输入
在完成布隆过滤器的建立后，就可以使用布隆过滤器来检测输入了。设输入为x，则检测x是否属于黑名单的过程为：
①将x分别输入到f1,f2,...,fn这n个函数中，得到n个哈希值c1,c2,...,cn
②将c1,c2,...,cn分别模m，计算出来n个bit数组的索引index1,index2,....,indexn
③利用这n个index获取bit数组上的值，如果n个值全为1，则表明x在黑名单中；否则不在黑名单
3. 布隆过滤器的参数选取与失误率的控制问题
使用布隆过滤器时，虽然有一定的失误率，但是通过合适地配置布隆过滤器的参数，可以将布隆过滤器的失误率降到一个很低的水平。
所涉及到的参数主要有：bit数组的大小m，哈希函数的个数n，预期失误率p，样本个数N
(1) bit数组的大小m
如果bit数组的大小M过小，那么将用于建立布隆过滤器的样本全部输入进去之后，所建立出来的布隆过滤器中bit数组中的大部分、乃至全部bit都被标为1，此时误报率将非常高，甚至达到100%，相当于把任何输入放进去，都会判定为true。
反之，如果bit数组的大小M过大，又会浪费内存，这与使用布隆过滤器的初衷就相违背了。
(2) 哈希函数的个数n
如果哈希函数的个数过多，那么在利用样本建立布隆过滤器的过程中，bit数组中的大部分位置会被迅速填满，导致误报率变大。
如果哈希函数的个数过少，那么对各个样本采集的特征过少，也会影响失误率。
因此，一定存在一个比较合适的n，使得在bit数组大小M和样本个数N确定的情况下，使得失误率降到一个很低的水平。
