深圳网站seo优化公司,微信小程序广告投放价格表,网站 文件夹 上传,内蒙古网站seo前言我们之前讲了Redis的缓存雪崩、穿透、击穿。在文章里我们说了解决缓存穿透的办法之一#xff0c;就是布隆过滤器#xff0c;但是上次并没有讲如何使用布隆过滤器。作为暖男的老哥#xff0c;给你们补上#xff0c;请叫我IT老暖男。什么是布隆过滤器布隆过滤器(Bloom Fi…前言我们之前讲了Redis的缓存雪崩、穿透、击穿。在文章里我们说了解决缓存穿透的办法之一就是布隆过滤器但是上次并没有讲如何使用布隆过滤器。作为暖男的老哥给你们补上请叫我IT老暖男。什么是布隆过滤器布隆过滤器(Bloom Filter)是1970年由一个叫布隆的小伙子提出的距今已经五十年了和老哥一样老。它实际上是一个很长的二进制向量和一系列随机映射函数二进制大家应该都清楚存储的数据不是0就是1默认是0。主要用于判断一个元素是否在一个集合中0代表不存在某个数据1代表存在某个数据。懂了吗作为暖男的老哥在给你们画张图来帮助理解布隆过滤器用途解决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值。例如图中的“你好”和“hello”假如最终算出hash值相同那么他们会将同一个下标的二进制数据改为1。这个时候你就不知道下标为2的二进制到底是代表“你好”还是“hello”。由此得出如下缺点一、存在误判假如上面的图没有存hello只存了你好那么用hello来查询的时候会判断hello存在集合中。因为“你好”和“hello”的hash值是相同的通过相同的hash值找到的二进制数据也是一样的都是1。二、删除困难到这里我不说大家应该也明白为什么吧作为你们的暖男老哥还是讲一下吧。还是用上面的举例因为“你好”和“hello”的hash值相同对应的数组下标也是一样的。这时候老哥想去删除“你好”将下标为2里的二进制数据由1改成了0。那么我们是不是连“hello”都一起删了呀。(0代表有这个数据1代表没有这个数据)到这里是不是对布隆过滤器已经明白了都说了我是暖男。实现布隆过滤器有很多种实现方式其中一种就是Guava提供的实现方式。一、引入Guava pom配置com.google.guavaguava29.0-jre二、代码实现这里我们顺便测一下它的误判率。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 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方法VisibleForTestingstatic 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类型数字需要的位数为7298440700多万位。理论上存一百万个数一个int是4字节32位需要4810000003200万位。如果使用HashMap去存按HashMap50%的存储效率需要6400万位。可以看出BloomFilter的存储空间很小只有HashMap的1/10左右上面的numHashFunctions表示需要几个hash函数运算去映射不同的下标存这些数字是否存在(0 or 1)。解决Redis缓存雪崩上面使用Guava实现的布隆过滤器是把数据放在了本地内存中。分布式的场景中就不合适了无法共享内存。我们还可以用Redis来实现布隆过滤器这里使用Redis封装好的客户端工具Redisson。其底层是使用数据结构bitMap大家就把它理解成上面说的二进制结构由于篇幅原因bitmap不在这篇文章里讲我们之后写一篇文章介绍。代码实现pom配置org.redissonredisson-spring-boot-starter3.13.4java代码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);//构造RedissonRedissonClient redisson Redisson.create(config);RBloomFilter bloomFilter redisson.getBloomFilter(phoneList);//初始化布隆过滤器预计元素为100000000L,误差率为3%bloomFilter.tryInit(100000000L,0.03);//将号码10086插入到布隆过滤器中bloomFilter.add(10086);//判断下面号码是否在布隆过滤器中//输出falseSystem.out.println(bloomFilter.contains(123456));//输出trueSystem.out.println(bloomFilter.contains(10086));}}由于Guava那个版本我们已经很详细的讲了布隆过滤器的那些参数这里就不重复赘述了。老哥在这里给大家准备了2020年最新Java面试题涵盖Java各个技术领域。共80多个PDFBAT面试必备
