什么是布隆过滤器

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

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

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

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

布隆过滤器的优点

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

布隆过滤器的缺陷

布隆过滤器会有误判的情况
无法删除元素，也不是无法删除，只是在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).divide(BigDecimal.valueOf(total)).toString());
    }
}

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

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

布谷鸟过滤器

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

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