Redis 布隆过滤器

1. 布隆过滤器简介

1970 年布隆提出了一种布隆过滤器的算法，用来判断一个元素是否在一个集合中。 这种算法由一个二进制数组和一个 Hash 算法组成。

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

实际上，布隆过滤器广泛应用于网页黑名单系统、垃圾邮件过滤系统、爬虫网址判重系统等，Google 著名的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列，以减少磁盘查找的IO次数，Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。

2. 布隆过滤器的误判问题

Ø通过hash计算在数组上不一定在集合

Ø本质是hash冲突

Ø通过hash计算不在数组的一定不在集合（误判）

优化方案

增大数组(预估适合值)

增加hash函数

3. Redis中的布隆过滤器

Redisson

Maven引入Redisson

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.12.3</version>
</dependency>

自行实现

就是利用Redis的bitmaps来实现。

单机下无Redis的布隆过滤器

使用Google的Guava的BloomFilter。

Maven引入Guava

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>30.1.1-jre</version>
</dependency>