篇首语：本文由小编为大家整理，主要介绍了布隆过滤器底层原理相关的知识，希望对你有一定的参考价值。

什么是布隆过滤器

是一个叫做布隆的小伙子发明出来的，底层使用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代码演示布隆过滤器

package com.filter;import com.google.common.collect.Lists;import com.google.common.hash.BloomFilter;import com.google.common.hash.Funnels;import java.math.BigDecimal;import java.util.List;/** * 布隆过滤器 */public class Bool     private static int size = 1000000;//预计要插入多少数据    private static double fpp = 0.01;//期望的误判率    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);    public static void main(String[] args)         List<Integer> list = Lists.newArrayList();        int total = 1000000; // 样本数据        //插入数据        for (int i = 0; i < total; i++)             bloomFilter.put(i);            list.add(i);                int count = 0; // 误判数量        int testNum = 100000;  // 用10万的数据去测试误判率        for (int i = total; i < total + testNum; i++)             // 判断元素是否存在            boolean b = bloomFilter.mightContain(i);            if(b)                 count ++;                System.out.println(i+"误判了");                            System.out.println("误判数量："+count);        System.out.println("误判率："+ BigDecimal.valueOf(count).pide(BigDecimal.valueOf(total)).toString());    

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

.........1099684误判了1099888误判了1099971误判了误判数量：947误判率：0.000947

布谷鸟过滤器

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

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

以上是关于布隆过滤器底层原理的主要内容，如果未能解决你的问题，请参考以下文章