布隆过滤器
布隆过滤器是一个BIT数组，可以用来判断一个元素是否在一个集合中已存在。很常用的一个功能是用来去重。例如在爬虫中，我们要爬取的目标网站 URL 千千万，怎么判断某个 URL 爬虫是否已经爬取过？简单点可以爬虫每采集过一个 URL，就把这个 URL 存入数据库中，每次一个新的 URL 过来就到数据库查询下是否访问过。但是随着爬虫爬过的 URL 越来越多，每次请求前都要访问数据库一次，并且对于这种字符串的 SQL 查询效率并不高。除了数据库之外，使用 Redis 的 set 结构也可以满足这个需求，并且性能优于数据库。但是 Redis 也存在一个问题：耗费过多的内存。相比于数据库和 Redis，使用布隆过滤器可以很好的避免性能和内存占用的问题。
实现原理
布隆过滤器实现非常简单，如下图所示，在存入元素a、b和c时，分别通过3个hash算法h1()、h2()和h2()计算出相应的hash值，并将BIT数组对应位置设为1。之后在判断新元素是否已存在时，也只需要使用这3个hash算法h1()、h2()和h2()计算出对应的hash值，然后通过hash值判断BIT数组对应位置，如果都为1，这就能够说明：d可能存在集合中（因为可能出现hash冲突）。如果有一个为0，那么说明：d一定不存在集合中。所以布隆过滤器对于一个元素是否已存在会存在误判，但如果某个元素经过布隆过滤器判断不存在，那说明这个元素真的不存在，不会发生误判。
布隆过滤器非常适合那种不需要 100% 准确的、允许存在小概率误判的大规模判重场景。除了爬虫网页去重这个例子，还有比如统计一个大型网站的每天的 UV 数，也就是每天有多少用户访问了网站，我们就可以使用布隆过滤器，对重复访问的用户进行去重。
Redis 中的布隆过滤器
redis 在 4.0 的版本中加入了 module 功能，布隆过滤器可以通过 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通过加载 module来使用 redis 中的布隆过滤器。但是这不是最简单的方式，使用 docker 可以直接在 redis 中体验布隆过滤器。
> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli
redis 布隆过滤器主要就两个命令：
-
bf.add添加元素到布隆过滤器中：bf.add urls https://jaychen.cc。 -
bf.exists判断某个元素是否在过滤器中：bf.exists urls https://jaychen.cc。
