Redis 中的布隆过滤器

原文链接：https://jaychen.cc/redis/2018...
作者：JayChen

什么是『布隆过滤器』

布隆过滤器是一个神奇的数据结构，可以用来判断一个元素是否在一个集合中。很常用的一个功能是用来去重。在爬虫中常见的一个需求：目标网站 URL 千千万，怎么判断某个 URL 爬虫是否宠幸过？简单点可以爬虫每采集过一个 URL，就把这个 URL 存入数据库中，每次一个新的 URL 过来就到数据库查询下是否访问过。

select id from table where url = 'https://jaychen.cc'

但是随着爬虫爬过的 URL 越来越多，每次请求前都要访问数据库一次，并且对于这种字符串的 SQL 查询效率并不高。除了数据库之外，使用 Redis 的 set 结构也可以满足这个需求，并且性能优于数据库。但是 Redis 也存在一个问题：耗费过多的内存。这个时候布隆过滤器就很横的出场了：这个问题让我来。

相比于数据库和 Redis，使用布隆过滤器可以很好的避免性能和内存占用的问题。

布隆过滤器本质是一个位数组，位数组就是数组的每个元素都只占用 1 bit 。每个元素只能是 0 或者 1。这样申请一个 10000 个元素的位数组只占用 10000 / 8 = 1250 B 的空间。布隆过滤器除了一个位数组，还有 K 个哈希函数。当一个元素加入布隆过滤器中的时候，会进行如下操作：

• 使用 K 个哈希函数对元素值进行 K 次计算，得到 K 个哈希值。
• 根据得到的哈希值，在位数组中把对应下标的值置为 1。

举个