场景引入
首先，我们先来看一个场景。比如现在需要判断数据是否存在，你会用什么方式。有的小伙伴觉得查DB啊，呃，如果面试你这样子很可能会被out。有小机灵鬼有方案了，那我用HashMap吧。将值映射到HashMap的KEY再用上Redis这种内存级的缓存，时间复杂度O（1），效率杠杠的。嗯，听起来好像是没啥问题，但是如果数据量非常大，比如上亿，那HashMap占据的内存大小就很值得关注了。这个时候，布隆过滤器出现了，相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少。它是如何做到比HashMap还要优秀的呢？我们来一层一层剥开。
什么是布隆过滤器
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好很多，缺点是有一定的误识别率和删除困难。
其实它本质上是一种数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。缺点是其返回的可能存在结果是概率性的，而不是确切的。值得一提的是，这里的删除困难其实智慧的人类早就有找到解决方案了。
布隆过滤器为什么这么优秀
布隆过滤器是一个bit向量或者说bit 数组，如下借用一张图。当然这只是个示例，实际上的位数是N倍。
我们回顾上面的百科定义。如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的bit位置1。
比如我们现在对“xiaoma”这个值进行多个函数的哈希，得到的哈希值为3、5、7，好的，我们将3,5,7号位置为1。我们再来一个值，比如“大胖”得到三个值为1、5、6，于是我们对1,5,6号位置为1。我们注意到5号位是被两个值的哈希都落位到的。
此时如果我们要开始查找了，假设查找“xiaomanong”这个值，哈希后得到1、2、6，我们发现2号位是0，于是我们很果断地说，“xiaomanong”这个值是不存在的。那话又说回来，假如我们此时查找“xiaoma”自然会得到3、5、7，我们发现这几号位上全是1，于是我们就可以果断地说“xiaoma”这个值就一定存在了？自然不行，因为你刚也看到了，5号的1有可能是其他值的哈希置为1的，所以只能说，可能存在。这就为什么它只能告诉你“一定不存在或者可能存在”的原理，也就是布隆会误判的原因。
Redis布隆过滤器要怎么实现
笔者也没有亲践，但整理了两个实现方案供参考。
1、Redis的rebloom模块扩展
下载并编译git clone git://github.com/RedisLabsModules/rebloom。配置文件中加载rebloom：loadmodule /your_path/rebloom.so。重启Redis服务器即可。
接下来就是一系列的操作命令了。大致可分为添加元素，判断元素是否存在，增量保存持久化。比如命令：
BF.EXISTS {key} {item}
判断单个元素是否存在
如果存在，返回1，否则返回0
2、redis-lua-scaling-bloom-filter
利用Redis的Bitmaps实现布隆过滤器，GitHub上已经开源了类似的方案可以自行搜索git（这里就不方便贴链接了），这种方法适用于数据命中不高、数据相对固定、实时性低（通常是数据集较大）的应用场景，代码维护较为复杂，但是缓存空间占用少。
总而言之，错误率越小(即对误差的容忍度越低)，每个过滤器条目的空间消耗就越大。布隆过滤器是可以牺牲准确率换空间，当然这个准确率大小是可以通过参数调整的，也和本身数组的大小以及hash函数的个数以及每个hash函数本身的好坏有关。
应用场景
1、爬虫中对大量页面URL判断，已经爬过的就不再爬了，当然这个是存在误判的，有些没爬过的URL可能被错过；
2、垃圾邮件的过滤，普遍都用了布隆过滤器。如果邮箱存在于垃圾邮件的布隆中就放入垃圾邮箱列表。同样存在误判，所以有些正常的邮箱也被放入垃圾列表中，但一般这种概率比较低。那么试想一下，可不可以把正常邮箱放入布隆中进行过滤呢能不能解决误判问题，留给观者思考哈；
3、防止缓存击穿和过滤一些黑客攻击。
