解决缓存穿透的办法之一，就是
布隆过滤器
布隆过滤器（Bloom Filter），是1970年，由一个叫布隆的小伙子提出的，距今已经五十年了，和老哥同样老。redis
它其实是一个很长的二进制向量和一系列随机映射函数，二进制你们应该都清楚，存储的数据不是0就是1，默认是0。算法
主要用于判断一个元素是否在一个集合中，0表明
不存在
某个数据，1表明
存在
某个数据。spring
懂了吗？
数组
布隆过滤器用途
-
解决Redis缓存穿透（今天重点讲解）缓存
-
在爬虫时，对爬虫网址进行过滤，已经存在布隆中的网址，不在爬取。微信
-
垃圾邮件过滤，对每个发送邮件的地址进行判断是否在布隆的黑名单中，若是在就判断为垃圾邮件。数据结构
布隆过滤器原理
存入过程
布隆过滤器上面说了，就是一个二进制数据的集合。当一个数据加入这个集合时，经历以下洗礼（这里有缺点，下面会讲）：
-
经过K个哈希函数计算该数据，返回K个计算出的hash值
-
这些K个hash值映射到对应的K个二进制的数组下标
-
将K个下标对应的二进制数据改为1。
例如，第一个哈希函数返回x，第二个第三个哈希函数返回y与z，那么：X、Y、Z对应的二进制改为1。
如图所示：
查询过程
布隆过滤器主要做用就是查询一个数据，在不在这个二进制的集合中，查询过程以下：
-
经过K个哈希函数计算该数据，对应计算出的K个hash值
-
经过hash值找到对应的二进制的数组下标
-
判断：若是存在一处位置的二进制数据是0，那么该数据不存在。若是都是1，该数据存在集合中。（缺点）
删除过程
通常不能删除布隆过滤器里的数据，这是一个缺点之一
布隆过滤器的优缺点
优势
-
因为存储的是二进制数据，因此占用的空间很小
-
它的插入和查询速度是很是快的，时间复杂度是O（K），能够联想一下HashMap的过程
-
保密性很好，由于自己不存储任何原始数据，只有二进制数据
缺点
这就要回到咱们上面所说的那些缺点了。
添加数据是经过计算数据的hash值，那么颇有可能存在这种状况：两个不一样的数据计算获得相同的hash值。
1、存在误判
2、删除困难
实现布隆过滤器
有不少种实现方式，其中一种就是
Guava
提供的实现方式。
1、引入Guava pom配置
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>29.0-jre</version>
</dependency>
2、代码实现
这里咱们顺便测一下它的误判率。
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterCase {
/**
* 预计要插入多少数据
*/
private static int size = 1000000;
/**
* 指望的误判率
*/
private static double fpp = 0.01;
/**
* 布隆过滤器
*/
private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
public static void main(String[] args) {
// 插入10万样本数据
for (int i = 0; i < size; i++) {
bloomFilter.put(i);
}
// 用另外十万测试数据，测试误判率
int count = 0;
for (int i = size; i < size + 100000; i++) {
if (bloomFilter.mightContain(i)) {
count++;
System.out.println(i + "误判了");
}
}
System.out.println("总共的误判数:" + count);
}
}
运行结果：
10万数据里有947个误判，约等于0.01%，也就是咱们代码里设置的误判率：fpp = 0.01。
深刻分析代码
核心
BloomFilter.create
方法
@VisibleForTesting
static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
。。。。
}
这里有四个参数：
-
funnel
：数据类型(通常是调用Funnels工具类中的) -
expectedInsertions
：指望插入的值的个数 -
fpp
：误判率(默认值为0.03) -
strategy
：哈希算法
咱们重点讲一下
fpp
参数
fpp误判率
情景一：
fpp = 0.01
-
误判个数：947
-
占内存大小：9585058位数
情景二：
fpp = 0.03
（默认参数）
-
误判个数：3033
-
占内存大小：7298440位数
情景总结
-
误判率能够经过
fpp
参数进行调节 -
fpp越小，须要的内存空间就越大：0.01须要900多万位数，0.03须要700多万位数。
-
fpp越小，集合添加数据时，就须要更多的hash函数运算更多的hash值，去存储到对应的数组下标里。（忘了去看上面的布隆过滤存入数据的过程）
上面的
numBits
，表示存一百万个int类型数字，须要的位数为7298440，700多万位。理论上存一百万个数，一个int是4字节32位，须要481000000=3200万位。若是使用HashMap去存，按HashMap50%的存储效率，须要6400万位。能够看出BloomFilter的存储空间很小，只有HashMap的1/10左右
上面的
numHashFunctions
表示须要几个hash函数运算，去映射不一样的下标存这些数字是否存在（0 or 1）。
解决Redis缓存雪崩
上面使用Guava实现的布隆过滤器是把数据放在了本地内存中。分布式的场景中就不合适了，没法共享内存。
咱们还能够用Redis来实现布隆过滤器，这里使用Redis封装好的客户端工具Redisson。
其底层是使用数据结构bitMap，你们就把它理解成上面说的二进制结构，因为篇幅缘由，bitmap不在这篇文章里讲，咱们以后写一篇文章介绍。
代码实现
pom配置：
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson-spring-boot-starter</artifactId>
<version>3.13.4</version>
</dependency>
java代码：
public class RedissonBloomFilter {
public static void main(String[] args) {
Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
config.useSingleServer().setPassword("1234");
//构造Redisson
RedissonClient redisson = Redisson.create(config);
RBloomFilter<String> bloomFilter = redisson.getBloomFilter("phoneList");
//初始化布隆过滤器：预计元素为100000000L,偏差率为3%
bloomFilter.tryInit(100000000L,0.03);
//将号码654321插入到布隆过滤器中
bloomFilter.add("654321");
//判断下面号码是否在布隆过滤器中
//输出false
System.out.println(bloomFilter.contains("123456"));
//输出true
System.out.println(bloomFilter.contains("654321"));
}
}