布隆过滤器 (Bloom Filter) 是解决 缓存穿透 的一种常用方式，其特点是：
- 计算为不存在的值在集合中一定不存在；
- 计算为存在的值在集合中不一定存在，有一个存在的概率。
布隆过滤器由一个很长的 位数组 和一定数量的 哈希函数 组成。
缓存穿透：大量请求访问缓存和数据库中都不存在的数据导致数据库的性能被完全浪费掉
位数组：数组的每个元素占据一个 bit，只存储 0 或者 1
哈希函数：能够将任意对象映射到数值的函数，一个理想的哈希函数应该实现一一映射，即没有哈希冲突
应用场景：判断某个元素是否在集合中。
原理
判断元素是否在集合中，我们通常会想到的办法是 哈希。将集合的每个元素作为键，将任意一个常量（通常是 null）作为值，通过判断哈希中是否存在 key 来快速判断元素是否在集合中。哈希的查询速度是很快的（时间复杂度是 $\text(1)$），但是当集合元素数量达到一定规模时，这个查询哈希规模会变得异常庞大，甚至超过物理内存。此时寻求一些其他更加节省内存的方式旧更加必要，尤其是对于 查询精度不那么高 的操作，哪怕查询不那么准也是可以接受的。
布隆过滤器就是这样一种查询器，它显示存在的元素在集合中不一定真的存在，这个存在的概率受位数组和哈希函数的特征和规模影响。
构建
对于加入集合的每一个元素，使用一组哈希函数可以计算出一组不同的值，然后将位数组中对应值的索引位置的值改为1。如果数组中要修改的位置已经是1，则覆盖它（还是1）。
查询
对于要查询的元素，同样使用构建布隆过滤器的那一组哈希函数计算该元素的哈希值，然后索引位数组上这些值对应位置的值，有两种情况：
- 存在至少一个位置值为0，说明该元素肯定不在集合中；
- 所有位置都为1，说明该元素可能在集合中。
因为同一个哈希函数可能将不同的输入映射到同一个值，不同的哈希函数也可能将它们的输入映射到同一个值，所以布隆过滤器的哈希冲突概率非常大。所有位置全为1可能仅仅是个巧合，不能保证说一定存在。
增大这个存在的概率，就要选用合适规模的位数组和合适的哈希函数。
删除
布隆过滤器不支持删除操作，因为位数组的每个位置可能关系着很多元素，不能简单置为1。
但是可以对原始布隆过滤器进行改进，例如每个位置存储计数。来达到删除的目的。
性能
优势：
- 使用位数组存储数据，占用内存小；
- 插入和查询速度很快，时间复杂度为 $\text(k)$，k 为哈希函数的个数；
- 保密性，因为布隆过滤器本身不存储集合的原始数据；
缺点：
- 哈希冲突导致的误判；
- 不能删除；
实现 for Java
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>25.1-jre</version>
</dependency>
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.Charset;
public class BloomFilterDemo {
public static void main(String[] args) {
/**
* 创建一个插入对象为一亿，误报率为0.01%的布隆过滤器
* 不存在一定不存在
* 存在不一定存在
* ----------------
* Funnel 对象：预估的元素个数，误判率
* mightContain ：方法判断元素是否存在
*/
BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 100000000, 0.0001);
bloomFilter.put("死");
bloomFilter.put("磕");
bloomFilter.put("Redis");
System.out.println(bloomFilter.mightContain("Redis"));
System.out.println(bloomFilter.mightContain("Java"));
}
}
评论区