作用 & 使用场景

用来判断一个元素是否在一个集合中

主要的使用场景是用来解决缓存穿透

判断一个元素是否在一个集合中。当数据量比较少时，我们使用list，map等集合即可，但是当数据量是海量时，集合就不能满足我们的需求了，此时就可以使用布隆过滤器

原理

布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数组成

插入元素

假设布隆过滤器的二进制数组长度为10，哈希函数为3个

二进制数组中的值一开始都是0

当我们向布隆过滤器插入元素"hello"时，步骤如下：

1. 分别计算插入元素的哈希值hash1(插入元素)，hash2(插入元素)，hash3(插入元素)

2. 把计算得到的hashcode % 二进制数组长度，得到对应的下标

3. 把对应下标的二进制值改为1

插入元素

判断元素是否存在

当我们判断元素"hello"是否存在时，步骤如下：

1. 分别计算插入元素的哈希值hash1(插入元素)，hash2(插入元素)，hash3(插入元素)

2. 把计算得到的hashcode % 二进制数组长度，得到对应的下标

3. 判断对应下标的二进制值是否都为1，若都为1，则元素可能存在，若不全是1，则元素一定不存在

优点

1. 存储空间和插入/查询时间都是常数

2. 可以表示数据全集

3. 安全性高，不是直接存储的元素

缺点

1. 删除困难，实际上应该是不支持删除

二进制向量

如上图，插入元素"hello"后，二进制数组中下标为2，4，7的二进制值为1，但是我们想在布隆过滤器中删除元素时，并不能直接把对应下标的二进制值改为0。

因为在插入其他元素时，经过哈希函数计算得到的下标也可能是这其中的一个或者全部，所以如果直接把二进制值改成0，可能会影响其他元素！！！

2. 存在误判，布隆过滤器说元素存在时，元素不一定存在！！！

假设"你好"经过哈希函数计算后得到的结果和"hello"相同，则判断元素是否存在时，"你好"也会被判断也存在，实际上不存在于布隆过滤器

总结

• 布隆过滤器说存在，不一定存在

• 布隆过滤器说不存在，则一定不存在

guava轮子演示

pom.xml

    com.google.guava
    guava
    23.0

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterDemo {
    public static void main(String[] args) {
        // 创建布隆过滤器，指定元素个数和误判率
        BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 500, 0.01);
        // 插入元素
        bloomFilter.put(1);
        bloomFilter.put(2);
        bloomFilter.put(3);
        // 判断元素是否存在
        System.out.println(bloomFilter.mightContain(1));
        System.out.println(bloomFilter.mightContain(2));
        System.out.println(bloomFilter.mightContain(3));
        System.out.println(bloomFilter.mightContain(4));
    }
}