网站备案的影布怎么做,视频链接怎么wordpress,wordpress 全图片,教育公司 网站建设Java技术栈www.javastack.cn打开网站看更多优质文章作者#xff1a;CodeBear的园子www.cnblogs.com/CodeBear/p/10911177.html本文是站在小白的角度去讨论布隆过滤器#xff0c;如果你是科班出身#xff0c;或者比较聪明#xff0c;又或者真正想完全搞懂布隆过滤器的可以移… Java技术栈www.javastack.cn打开网站看更多优质文章作者CodeBear的园子www.cnblogs.com/CodeBear/p/10911177.html本文是站在小白的角度去讨论布隆过滤器如果你是科班出身或者比较聪明又或者真正想完全搞懂布隆过滤器的可以移步。不知道从什么时候开始本来默默无闻的布隆过滤器一下子名声大燥仿佛身在互联网做着开发的无人不知无人不晓哪怕对技术不是很关心的小伙伴也听过它的名号。我也花了不少时间去研究布隆过滤器看了不少博客无奈不是科班出身又没有那么聪明的头脑又比较懒...经过“放弃拿起放弃拿起”的无限轮回应该算是了解了布隆过滤器的核心思想所以想给大家分享下。布隆过滤器的应用我们先来看下布隆过滤器的应用场景让大家知道神奇的布隆过滤器到底能做什么。缓存穿透我们经常会把一部分数据放在Redis等缓存比如产品详情。这样有查询请求进来我们可以根据产品Id直接去缓存中取数据而不用读取数据库这是提升性能最简单最普遍也是最有效的做法。面试常问缓存三大问题及解决方案一般的查询请求流程是这样的先查缓存有缓存的话直接返回如果缓存中没有再去数据库查询然后再把数据库取出来的数据放入缓存一切看起来很美好。但是如果现在有大量请求进来而且都在请求一个不存在的产品Id会发生什么既然产品Id都不存在那么肯定没有缓存没有缓存那么大量的请求都怼到数据库数据库的压力一下子就上来了还有可能把数据库打死。虽然有很多办法都可以解决这问题但是我们的主角是“布隆过滤器”没错“布隆过滤器”就可以解决(缓解)缓存穿透问题。至于为什么说是“缓解”看下去你就明白了。大量数据判断给定的是否在其中现在有大量的数据而这些数据的大小已经远远超出了服务器的内存现在再给你一个数据如何判断给你的数据在不在其中。如果服务器的内存足够大那么用HashMap是一个不错的解决方案理论上的时间复杂度可以达到O(1)但是现在数据的大小已经远远超出了服务器的内存所以无法使用HashMap这个时候就可以使用“布隆过滤器”来解决这个问题。但是还是同样的会有一定的“误判率”。什么是布隆过滤器布隆过滤器是一个叫“布隆”的人提出的它本身是一个很长的二进制向量既然是二进制的向量那么显而易见的存放的不是0就是1。现在我们新建一个长度为16的布隆过滤器默认值都是0就像下面这样现在需要添加一个数据我们通过某种计算方式比如Hash1计算出了Hash1(数据)5我们就把下标为5的格子改成1就像下面这样我们又通过某种计算方式比如Hash2计算出了Hash2(数据)9我们就把下标为9的格子改成1就像下面这样还是通过某种计算方式比如Hash3计算出了Hash3(数据)2我们就把下标为2的格子改成1就像下面这样这样刚才添加的数据就占据了布隆过滤器“5”“9”“2”三个格子。可以看出仅仅从布隆过滤器本身而言根本没有存放完整的数据只是运用一系列随机映射函数计算出位置然后填充二进制向量。这有什么用呢比如现在再给你一个数据你要判断这个数据是否重复你怎么做你只需利用上面的三种固定的计算方式计算出这个数据占据哪些格子然后看看这些格子里面放置的是否都是1如果有一个格子不为1那么就代表这个数字不在其中。这很好理解吧比如现在又给你了刚才你添加进去的数据你通过三种固定的计算方式算出的结果肯定和上面的是一模一样的也是占据了布隆过滤器“5”“9”“2”三个格子。但是有一个问题需要注意如果这些格子里面放置的都是1不一定代表给定的数据一定重复也许其他数据经过三种固定的计算方式算出来的结果也是相同的。这也很好理解吧比如我们需要判断对象是否相等是不可以仅仅判断他们的哈希值是否相等的。也就是说布隆过滤器只能判断数据是否一定不存在而无法判断数据是否一定存在。按理来说介绍完了新增、查询的流程就要介绍删除的流程了但是很遗憾的是布隆过滤器是很难做到删除数据的为什么你想想比如你要删除刚才给你的数据你把“5”“9”“2”三个格子都改成了0但是可能其他的数据也映射到了“5”“9”“2”三个格子啊这不就乱套了吗相信经过我这么一介绍大家对布隆过滤器应该有一个浅显的认识了至少你应该清楚布隆过滤器的优缺点了优点由于存放的不是完整的数据所以占用的内存很少而且新增查询速度够快缺点随着数据的增加误判率随之增加无法做到删除数据只能判断数据是否一定不存在而无法判断数据是否一定存在。可以看到布隆过滤器的优点和缺点一样明显。在上文中我举的例子二进制向量长度为16由三个随机映射函数计算位置在实际开发中如果你要添加大量的数据仅仅16位是远远不够的为了让误判率降低我们还可以用更多的随机映射函数、更长的二进制向量去计算位置。guava实现布隆过滤器现在相信你对布隆过滤器应该有一个比较感性的认识了布隆过滤器核心思想其实并不难难的在于如何设计随机映射函数到底映射几次二进制向量的长度设置为多少比较好这可能就不是一般的开发可以驾驭的了。好在Google大佬给我们提供了开箱即用的组件来帮助我们实现布隆过滤器现在就让我们看看怎么Google大佬送给我们的“礼物”吧。首先在pom引入“礼物”dependency groupIdcom.google.guavagroupId artifactIdguavaartifactId version19.0versiondependency然后就可以测试啦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) {//插入数据for (int i 0; i 1000000; i) { bloomFilter.put(i); }int count 0;for (int i 1000000; i 2000000; i) {if (bloomFilter.mightContain(i)) { count; System.out.println(i 误判了); } } System.out.println(总共的误判数: count);}代码简单分析我们定义了一个布隆过滤器有两个重要的参数分别是 我们预计要插入多少数据我们所期望的误判率误判率不能为0。我向布隆过滤器插入了0-1000000然后用1000000-2000000来测试误判率。运行结果1999501误判了1999567误判了1999640误判了1999697误判了1999827误判了1999942误判了总共的误判数:10314现在总共有100万数据是不存在的误判了10314次我们计算下误判率和我们定义的期望误判率0.01相差无几。redis实现布隆过滤器上面使用guava实现布隆过滤器是把数据放在本地内存中无法实现布隆过滤器的共享我们还可以把数据放在redis中用 redis来实现布隆过滤器我们要使用的数据结构是bitmap你可能会有疑问redis支持五种数据结构StringListHashSetZSet没有bitmap呀。没错实际上bitmap的本质还是String。可能有小伙伴会说纳尼布隆过滤器还没介绍完怎么又出来一个bitmap没事你可以把bitmap就理解为一个二进制向量。要用redis来实现布隆过滤器我们需要自己设计映射函数自己度量二进制向量的长度这对我来说无疑是一个不可能完成的任务只能借助搜索引擎下面直接放出代码把。public class RedisMain {static final int expectedInsertions 100;//要插入多少数据static final double fpp 0.01;//期望的误判率//bit数组长度private static long numBits;//hash函数数量private static int numHashFunctions;static { numBits optimalNumOfBits(expectedInsertions, fpp); numHashFunctions optimalNumOfHashFunctions(expectedInsertions, numBits); }public static void main(String[] args) { Jedis jedis new Jedis(192.168.0.109, 6379);for (int i 0; i 100; i) {long[] indexs getIndexs(String.valueOf(i));for (long index : indexs) { jedis.setbit(codebear:bloom, index, true); } }for (int i 0; i 100; i) {long[] indexs getIndexs(String.valueOf(i));for (long index : indexs) { Boolean isContain jedis.getbit(codebear:bloom, index);if (!isContain) { System.out.println(i 肯定没有重复); } } System.out.println(i 可能重复); } }/** * 根据key获取bitmap下标 */private static long[] getIndexs(String key) {long hash1 hash(key);long hash2 hash1 16;long[] result new long[numHashFunctions];for (int i 0; i numHashFunctions; i) {long combinedHash hash1 i * hash2;if (combinedHash 0) { combinedHash ~combinedHash; } result[i] combinedHash % numBits; }return result; }private static long hash(String key) { Charset charset Charset.forName(UTF-8);return Hashing.murmur3_128().hashObject(key, Funnels.stringFunnel(charset)).asLong(); }//计算hash函数个数private static int optimalNumOfHashFunctions(long n, long m) {return Math.max(1, (int) Math.round((double) m / n * Math.log(2))); }//计算bit数组长度private static long optimalNumOfBits(long n, double p) {if (p 0) { p Double.MIN_VALUE; }return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2))); }}运行结果88可能重复89可能重复90可能重复91可能重复92可能重复93可能重复94可能重复95可能重复96可能重复97可能重复98可能重复99可能重复本篇博客到这里就结束了谢谢大家。写作不易坚持更难如大家喜欢就帮忙推送给其他人最近热文1、Tomcat 又爆出高危漏洞8.5 10 中招…2、Spring Boot 干掉了 Maven 拥抱 Gradle3、打破你的认知数字除以0一定会崩溃吗4、写了个全局变量的bug被同事们打脸5、Java 14 祭出神器Lombok 被干掉了6、为什么 Redis 单线程能达到百万QPS7、Spring Boot 2.3 优雅关闭新姿势真香8、玩大发了Tomcat 8.5 升级有坑…9、我天xx.equals(null) 是什么骚操作10、Spring Boot 2.3.1 发布 10 个新特性扫码关注Java技术栈公众号干货。点击「」获取面试题大全
