csdn 文章专栏
前言
在「面试」Redis 这一篇就够了 这篇文中有提到用布隆过滤器来解决缓存穿透。那么，今天，他来了，他来了，他脚踏七彩祥云来了（手动狗头）
布隆
是什么？
弗雷尔卓德之心布隆是 LOL 中偏辅助的英雄，下面给大家带来他的技能和出装介绍，这时一个拖鞋啪的一声打在了我的脸上......
布隆过滤器(Bloom Filter) 是一种节省空间的概率数据结构，由 Burton Howard Bloom 在 1970 年提出，用来测试一个元素是否在一个集合里。它实际上是一个很长的二进制向量和一系列随机映射函数。相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。
原理
可以拆分成两个环节：
- 插入，当一个元素被加入集合时，通过 K 个散列（Hash）函数将这个元素映射成一个位数组中的 K 个点，把它们置为 1。
- 查找，当需要判断这个元素是否存在时，我们只要看看这些点是不是都是 1 就，大约知道集合中有没有它了，如果这些点有任何一个 0，则被检元素一定不在；如果都是 1，则被检元素很可能存在。
举个栗子：
S 集合中有 a、b、c 三个元素，过滤器中有三个散列（Hash）函数 h1、h2、h3，当要判断元素 a 是否存在时，则用 a 通过 h1、h2、h3 三个函数进行 hash，如果结果都是 1，那么说明 1 可能存在，反之则不存在
查询原理
优点
1.节省存储空间
2.查找速度快。
缺点
1.存在误判，可能要查到的元素并没有在容器中，但是 hash 之后得到的 k 个位置上值都是 1。
2.删除困难。一个放入容器的元素映射到 bit 数组的 k 个位置上是 1，删除的时候不能简单的直接置为 0，可能会影响其他元素的判断。
运用场景
1.解决 redis 等其他缓存穿透的问题，可以看这篇「面试」Redis 实现分布式锁这一篇就够了
2.判断是否存在该行（rows）或（colums），以减少对磁盘的访问，提高数据库的访问性能
3.分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列，以减少磁盘查找的 IO 次数
4.其他需要判断元素是否存在的场景
JAVA 实现
guava 工具包中已经包含了对布隆过滤器的实现，要使用 BloomFilter，需要引入 guava 包：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>23.0</version>
</dependency>
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import lombok.extern.slf4j.Slf4j;
@Slf4j
public class Bloom {
/**
* 总个数
*/
private static int total = 1000000;
/**
* 创建布隆过滤器
*/
private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total);
public static void main(String[] args) {
// 初始化1000000条数据到过滤器中
for (int i = 0; i < total; i++) {
bf.put(i);
}
int j = 5000;
// 判断是否存在
boolean flag = bf.mightContain(j);
log.info("{} 判断结果为：{}", j, flag);
// 匹配已在过滤器中的值，是否有匹配不上的
for (int i = 0; i < total; i++) {
if (!bf.mightContain(i)) {
log.info("有坏人逃脱了~~~");
}
}
// 匹配不在过滤器中的10000个值，有多少匹配出来
int count = 0;
for (int i = total; i < total + 10000; i++) {
if (bf.mightContain(i)) {
count++;
}
}
log.info("误伤的数量：" + count);
}
}
执行结果：
5000 判断结果为：true
误伤的数量：320
运行结果表示，遍历这一百万个在过滤器中的数时，都被识别出来了。一万个不在过滤器中的数，误伤了 320 个，错误率是 0.03 左右。
本期就到这啦，有不对的地方欢迎好哥哥们评论区留言，另外求关注、求点赞
