本文共 5250 字,大约阅读时间需要 17 分钟。
Java技术栈
www.javastack.cn
打开网站看更多优质文章
作者:CodeBear的园子
www.cnblogs.com/CodeBear/p/10911177.html
本文是站在小白的角度去讨论布隆过滤器,如果你是科班出身,或者比较聪明,又或者真正想完全搞懂布隆过滤器的可以移步。
不知道从什么时候开始,本来默默无闻的布隆过滤器一下子名声大燥,仿佛身在互联网,做着开发的,无人不知,无人不晓,哪怕对技术不是很关心的小伙伴也听过它的名号。
我也花了不少时间去研究布隆过滤器,看了不少博客,无奈不是科班出身,又没有那么聪明的头脑,又比较懒...经过“放弃,拿起,放弃,拿起”的无限轮回,应该算是了解了布隆过滤器的核心思想,所以想给大家分享下。
布隆过滤器的应用
我们先来看下布隆过滤器的应用场景,让大家知道神奇的布隆过滤器到底能做什么。
缓存穿透
大量数据,判断给定的是否在其中
现在有大量的数据,而这些数据的大小已经远远超出了服务器的内存,现在再给你一个数据,如何判断给你的数据在不在其中。
如果服务器的内存足够大,那么用是一个不错的解决方案,理论上的时间复杂度可以达到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实现布隆过滤器
现在相信你对布隆过滤器应该有一个比较感性的认识了,布隆过滤器核心思想其实并不难,难的在于如何设计随机映射函数,到底映射几次,二进制向量的长度设置为多少比较好,这可能就不是一般的开发可以驾驭的了。
好在大佬给我们提供了开箱即用的组件,来帮助我们实现布隆过滤器,现在就让我们看看怎么大佬送给我们的“礼物”吧。
首先在pom引入“礼物”:
com.google.guava guava 19.0
然后就可以测试啦:
private static int size = 1000000;//预计要插入多少数据private static double fpp = 0.01;//期望的误判率private static BloomFilterbloomFilter = 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实现布隆过滤器
可能有小伙伴会说,纳尼,布隆过滤器还没介绍完,怎么又出来一个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、
2、
3、
4、
5、
6、
7、
8、
9、
10、
扫码关注Java技术栈公众号阅读更多干货。
点击「」获取面试题大全~
转载地址:https://javastack.blog.csdn.net/article/details/107010941 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!