布隆过滤器底层原理

发布时间:2022-03-01 10:16:11 作者:yexindonglai@163.com 阅读(60)

什么是布隆过滤器

是一个叫做布隆的小伙子发明出来的,底层使用bitmap(二进制位)实现,向bitmap中标记为1,表示这个元素已查询过,下次来查询的时候就不要再去数据库查了;

这里涉及到了一个问题, 就是说,如果我下次把这个不存在的数据插入到数据库了,那么也需要将布隆过滤器的bitmap刷新,因为数据库写了一篇,还需要在redis再写一遍,就涉及到双写了;

布隆过滤器能解决什么问题

布隆过滤器可以解决缓存穿透的问题;如果不知道缓存穿透,可以看我另一篇博客,有详细介绍:谈谈redis缓存击穿透和缓存击穿的区别,以及它们所引起的雪崩效应

布隆过滤器的优点

  1. 由一段二进制的数据来存储数据,所以它的占用空间非常小
  2. 插入和查询速度快,通过计算hash值找到所在二进制的位置;将0改为1即可,基于数组的特性,所以非常快
  3. 保密性非常好,因为里面存储都是0和1,别人根本就不知道它存储的是什么

布隆过滤器的缺陷

  1. 布隆过滤器会有误判的情况
  2. 无法删除元素,也不是无法删除,只是在hash冲突的情况下会将其他相同位置的元素数据一起删除;

布隆过滤器底层原理

比如下图,元素1经过3次hash函数分别计算出3个下标位置分别为0、2、4的位置,那么这时候0、2、4就代表了元素1,其他的元素也是经过这么计算得出来的;
在这里插入图片描述

布隆过滤器误判

比如我有一个元素内容为:你好,经过三次hash计算之后得出结果为二进制的下标位置为第0、1、2位,也就是这样的1110 0000,那么这时候我第二个元素内容为hello,经过三次hash计算之后得出结果也是下标位置的第0、1、2位,两个不同的元素经过三次hash之后得到了相同的结果,这种情况就叫做误判;

在这里插入图片描述

如何解决误判

布隆过滤器在数据量大的时候会有误判的情况,这种情况几乎是无法避免的;所以我们只能尽可能的减少误判率;最低可达到1%的误判率;这个误判率可以人为设置,误判率越小,性能就越低;因为误判率越小,布隆过过滤器在内部就会经过越多次数的hash函数;

java代码演示布隆过滤器

  1. package com.filter;
  2. import com.google.common.collect.Lists;
  3. import com.google.common.hash.BloomFilter;
  4. import com.google.common.hash.Funnels;
  5. import java.math.BigDecimal;
  6. import java.util.List;
  7. /**
  8. * 布隆过滤器
  9. */
  10. public class Bool {
  11. private static int size = 1000000;//预计要插入多少数据
  12. private static double fpp = 0.01;//期望的误判率
  13. private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
  14. public static void main(String[] args) {
  15. List<Integer> list = Lists.newArrayList();
  16. int total = 1000000; // 样本数据
  17. //插入数据
  18. for (int i = 0; i < total; i++) {
  19. bloomFilter.put(i);
  20. list.add(i);
  21. }
  22. int count = 0; // 误判数量
  23. int testNum = 100000; // 用10万的数据去测试误判率
  24. for (int i = total; i < total + testNum; i++) {
  25. // 判断元素是否存在
  26. boolean b = bloomFilter.mightContain(i);
  27. if(b) {
  28. count ++;
  29. System.out.println(i+"误判了");
  30. }
  31. }
  32. System.out.println("误判数量:"+count);
  33. System.out.println("误判率:"+ BigDecimal.valueOf(count).divide(BigDecimal.valueOf(total)).toString());
  34. }
  35. }

执行后结果如下,可以看到误判数量为947,已经将误判率保持在了1%之内

  1. .........
  2. 1099684误判了
  3. 1099888误判了
  4. 1099971误判了
  5. 误判数量:947
  6. 误判率:0.000947

布谷鸟过滤器

为了解决误判的情况,所以衍生出了一种西新的过滤器,也是布隆过滤器的升级版,布谷鸟过滤器,为什么叫布谷鸟过滤器呢,因为这个过滤器跟布谷鸟的生活习性很像,大家都知道鸠占鹊巢这个成语,这个鸠就是布谷鸟,布谷鸟从来不会自己去搭建鸟巢,所以每次要下蛋的时候就趁别的鸟外出的时候,把自己的蛋下到别的鸟巢里面,然后自己赶紧跑掉;其他鸟就会帮布谷鸟孵化鸟蛋;当布谷鸟蛋孵化后,因为布谷鸟的体型比较大,它就会把其他的鸟挤走,这就是鸠占鹊巢;

布谷鸟会 “布谷布谷”的叫,所以被称为布谷鸟; 布谷鸟过滤器原理将在以后的章节更新! 敬请期待

关键字Redis