前言
我以前提到过Redis的缓存雪崩、贯通和破坏。 文章论述了布隆过滤器作为解决缓存直通的方法之一，但上次没有讨论布隆过滤器的使用方法。
作为暖男的sxdwx添加到你们身上。 请叫我IT老暖男。
什么是布隆过滤器
布鲁姆过滤器(Bloom Filter )是一个叫布鲁姆的年轻人在1970年提出的，距今已有50年了。 和sxdwx一样旧。
这实际上是一个长二进制向量和一系列随机映射函数，二进制应该大家都知道。 保存的数据既不是0也不是1，默认值为0。
主要用于确定元素是否在集合中。 0意味着数据不存在，1意味着数据存在。
明白了吗？ 作为温暖的男人，sxdwx正在给你们画画帮助你们理解：
用于布隆过滤器的Redis缓存直通解决(今天重点说明) ) ) ) )。
对于爬行类，过滤爬行类网站时，布鲁姆中的网站已经存在，没有爬上去。
垃圾邮件过滤器根据发送邮件的每个地址判断是否在布鲁姆的黑名单中，如果有，则判断为垃圾邮件。
以上是简单用途的例子，大家可以举一反三，活用于工作中。
布隆过滤器原理
收款流程
如上所述，光晕过滤器是二进制数据的集合。 这个集合加上一个数据，就会经历以下洗礼。 (这里有缺点，后面会讲到。 )用k个散列函数计算该数据，并返回k个计算出的散列值。
这k个哈希值被映射到相应的k个二进制数组下标
将k个下标对应的二进制数据更改为1。
例如，如果第一个散列函数返回x，第二个第三个散列函数返回y和z，则与x、y和z对应的二进制文件将更改为1。
如图所示：
查询进程
布隆过滤器的主要作用是查询一个数据。 如果不在此二进制文件集合中，则查询过程如下： 用k个散列函数计算其数据，对应于计算出的k个散列值
从hash值中找到对应二进制的数组下标
判断：如果存在于1个位置的二进制数据为0，则该数据不存在。 在都为1的情况下，该数据存在于集合中。 (这里有缺点，以后再说) )。
删除进程
无法删除光晕滤波器的数据是缺点之一。 接下来分析。
布隆过滤器的优缺点
优点是存储二进制数据，所以占用空间小
其插入和检索速度非常快，时间复杂度为o(k )，可以联想到HashMap的过程
它的机密性很好。 因为没有保存任何原始数据，只有二进制数据
缺点
这将回到我们之前说的缺点。
添加数据是通过计算数据的哈希值，很可能在两个不同的数据计算中得到相同的哈希值。
例如，如果最终计算出hash值相同，图中的“你好”和“hello”将同一下标的二进制数据更改为1。
此时，不知道下标为2的二进制表示“你好”还是“hello”。
由此，可以得到以下缺点。
一、有误判
如果上面的图中没有保存“hello”，而只保存了“你好”，则在“hello”中进行调查时，系统会确定“hello”存在于集合中。
“你好”和“hello”的散列值相同，因此在相同的散列值中找到的二进制数据也相同，为1。
二.删除困难
不用说到这里也知道理由吧，作为你们温暖的男人sxdwx来说吧。
在上面的示例中，“你好”和“hello”的hash值相同，因此对应的数组下标也相同。
这时，sxdwx想删除“你好”，把下标为2里的二进制数据，从1改为0。
那么我们连“hello”都一起删除了吗？ (0表示有此数据，1表示没有此数据。)
你到这里明白布鲁姆过滤器了吗，我说我是个暖男。
实现布隆过滤器
有多种实现方法，其中之一是Guava提供的实现方法。
一、引入Guava pom配置
com.google.guava
瓜维亚
29.0-jre
二、代码实现
现在让我们顺便测量一下误判率。
import com.Google.com mon.hash.bloom filter；
import com.Google.com mon.hash.funnels；
公共类蓝牙
//*
*计划插入的数据数
*/
私密静态int size=1000000；
//*
*预期误判率
*/
私有静态双精度fpp=0.01；
//*
*布隆过滤器
*/
pri
vate static BloomFilter 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 BloomFilter 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配置：
org.redisson
redisson-spring-boot-starter
3.13.4
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 bloomFilter = redisson.getBloomFilter("phoneList");
//初始化布隆过滤器：预计元素为100000000L,误差率为3%
bloomFilter.tryInit(100000000L,0.03);
//将号码10086插入到布隆过滤器中
bloomFilter.add("10086");
//判断下面号码是否在布隆过滤器中
//输出false
System.out.println(bloomFilter.contains("123456"));
//输出true
System.out.println(bloomFilter.contains("10086"));
}
}
由于Guava那个版本，我们已经很详细的讲了布隆过滤器的那些参数，这里就不重复赘述了。
sxdwx在这里给大家准备了2020年最新Java面试题，涵盖Java各个技术领域。共80多个PDF，BAT面试必备