本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
一、布隆过滤器简介
上一次 我们学会了使用 HyperLogLog 来对大数据进行一个估算，它非常有价值，可以解决很多精确度不高的统计需求。但是如果我们想知道某一个值是不是已经在 HyperLogLog 结构里面了，它就无能为力了，它只提供了
pfadd 和
pfcount 方法，没有提供类似于
contains 的这种方法。
就举一个场景吧，比如你 刷抖音：
你有 刷到过重复的推荐内容 吗？这么多的推荐内容要推荐给这么多的用户，它是怎么保证每个用户在看推荐内容时，保证不会出现之前已经看过的推荐视频呢？也就是说，抖音是如何实现 推送去重 的呢？
你会想到服务器 记录 了用户看过的 所有历史记录，当推荐系统推荐短视频时会从每个用户的历史记录里进行 筛选，过滤掉那些已经存在的记录。问题是当 用户量很大，每个用户看过的短视频又很多的情况下，这种方式，推荐系统的去重工作 在性能上跟的上么？
实际上，如果历史记录存储在关系数据库里，去重就需要频繁地对数据库进行
exists 查询，当系统并发量很高时，数据库是很难抗住压力的。
你可能又想到了 缓存，但是这么多用户这么多的历史记录，如果全部缓存起来，那得需要 浪费多大的空间 啊.. (可能老板看一眼账单，看一眼你..) 并且这个存储空间会随着时间呈线性增长，就算你用缓存撑得住一个月，但是又能继续撑多久呢？不缓存性能又跟不上，咋办呢？
如上图所示，布隆过滤器(Bloom Filter) 就是这样一种专门用来解决去重问题的高级数据结构。但是跟 HyperLogLog 一样，它也一样有那么一点点不精确，也存在一定的误判概率，但它能在解决去重的同时，在 空间上能节省 90% 以上，也是非常值得的。
布隆过滤器是什么
布隆过滤器（Bloom Filter） 是 1970 年由布隆提出的。它 实际上 是一个很长的二进制向量和一系列随机映射函数 **(下面详细说)**，实际上你也可以把它 简单理解 为一个不怎么精确的 set 结构，当你使用它的
contains 方法判断某个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对足够精确，只会有小小的误判概率。
当布隆过滤器说某个值存在时，这个值 可能不存在；当它说不存在时，那么 一定不存在。打个比方，当它说不认识你时，那就是真的不认识，但是当它说认识你的时候，可能是因为你长得像它认识的另外一个朋友 **(脸长得有些相似)**，所以误判认识你。
布隆过滤器的使用场景
基于上述的功能，我们大致可以把布隆过滤器用于以下的场景之中：
二、布隆过滤器原理解析
布隆过滤器 本质上 是由长度为
m 的位向量或位列表（仅包含
0 或
1 位值的列表）组成，最初所有的值均设置为
0，所以我们先来创建一个稍微长一些的位向量用作展示：
当我们向布隆过滤器中添加数据时，会使用 多个
hash 函数对
key 进行运算，算得一个证书索引值，然后对位数组长度进行取模运算得到一个位置，每个
hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为
1 就完成了
add 操作，例如，我们添加一个
wmyskxz：
向布隆过滤器查查询
key 是否存在时，跟
add 操作一样，会把这个
key 通过相同的多个
hash 函数进行运算，查看 对应的位置 是否 都 为
1，**只要有一个位为
0**，那么说明布隆过滤器中这个
key 不存在。如果这几个位置都是
1，并不能说明这个
key 一定存在，只能说极有可能存在，因为这些位置的
1 可能是因为其他的
key 存在导致的。
就比如我们在
add 了一定的数据之后，查询一个 不存在 的
key：
很明显，
1/3/5 这几个位置的
1 是因为上面第一次添加的
wmyskxz 而导致的，所以这里就存在 误判。幸运的是，布隆过滤器有一个可以预判误判率的公式，比较复杂，感兴趣的朋友可以自行去阅读，比较烧脑.. 只需要记住以下几点就好了：
三、布隆过滤器的使用
Redis 官方 提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。下面我们来体验一下 Redis 4.0 的布隆过滤器，为了省去繁琐安装过程，我们直接用 Docker 吧。
docker pull redislabs/rebloom # 拉取镜像
docker run -p6379:6379 redislabs/rebloom # 运行容器
redis-cli # 连接容器中的 redis 服务
如果上面三条指令执行没有问题，下面就可以体验布隆过滤器了。
布隆过滤器的基本用法
布隆过滤器有两个基本指令，
bf.add 添加元素，
bf.exists 查询元素是否存在，它的用法和 set 集合的
sadd 和
sismember 差不多。注意
bf.add 只能一次添加一个元素，如果想要一次添加多个，就需要用到
bf.madd 指令。同样如果需要一次查询多个元素是否存在，就需要用到
bf.mexists 指令。
127.0.0.1:6379 bf.add codehole user1
(integer) 1
127.0.0.1:6379 bf.add codehole user2
(integer) 1
127.0.0.1:6379 bf.add codehole user3
(integer) 1
127.0.0.1:6379 bf.exists codehole user1
(integer) 1
127.0.0.1:6379 bf.exists codehole user2
(integer) 1
127.0.0.1:6379 bf.exists codehole user3
(integer) 1
127.0.0.1:6379 bf.exists codehole user4
(integer) 0
127.0.0.1:6379 bf.madd codehole user4 user5 user6
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379 bf.mexists codehole user4 user5 user6 user7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0
上面使用的布隆过过滤器只是默认参数的布隆过滤器，它在我们第一次
add 的时候自动创建。Redis 也提供了可以自定义参数的布隆过滤器，只需要在
add 之前使用
bf.reserve 指令显式创建就好了。如果对应的
key 已经存在，
bf.reserve 会报错。
bf.reserve 有三个参数，分别是
key、
error_rate (错误率) 和
initial_size：
如果不适用
bf.reserve，默认的
error_rate 是
0.01，默认的
initial_size 是
100。
四、布隆过滤器代码实现
自己简单模拟实现
根据上面的基础理论，我们很容易就可以自己实现一个用于
简单模拟 的布隆过滤器数据结构：
public static class BloomFilter {
private byte[] data;
public BloomFilter(int initSize) {
this.data = new byte[initSize * 2]; // 默认创建大小 * 2 的空间
}
public void add(int key) {
int location1 = Math.abs(hash1(key) % data.length);
int location2 = Math.abs(hash2(key) % data.length);
int location3 = Math.abs(hash3(key) % data.length);
data[location1] = data[location2] = data[location3] = 1;
}
public boolean contains(int key) {
int location1 = Math.abs(hash1(key) % data.length);
int location2 = Math.abs(hash2(key) % data.length);
int location3 = Math.abs(hash3(key) % data.length);
return data[location1] * data[location2] * data[location3] == 1;
}
private int hash1(Integer key) {
return key.hashCode();
}
private int hash2(Integer key) {
int hashCode = key.hashCode();
return hashCode ^ (hashCode 3);
}
private int hash3(Integer key) {
int hashCode = key.hashCode();
return hashCode ^ (hashCode 16);
}
}
这里很简单，内部仅维护了一个
byte 类型的
data 数组，实际上
byte 仍然占有一个字节之多，可以优化成
bit 来代替，这里也仅仅是用于方便模拟。另外我也创建了三个不同的
hash 函数，其实也就是借鉴
HashMap 哈希抖动的办法，分别使用自身的
hash 和右移不同位数相异或的结果。并且提供了基础的
add 和
contains 方法。
下面我们来简单测试一下这个布隆过滤器的效果如何：
public static void main(String[] args) {
Random random = new Random();
// 假设我们的数据有 1 百万
int size = 1_000_000;
// 用一个数据结构保存一下所有实际存在的值
LinkedListInteger existentNumbers = new LinkedList();
BloomFilter bloomFilter = new BloomFilter(size);
for (int i = 0; i size; i++) {
int randomKey = random.nextInt();
existentNumbers.add(randomKey);
bloomFilter.add(randomKey);
}
// 验证已存在的数是否都存在
AtomicInteger count = new AtomicInteger();
AtomicInteger finalCount = count;
existentNumbers.forEach(number - {
if (bloomFilter.contains(number)) {
finalCount.incrementAndGet();
}
});
System.out.printf("实际的数据量：%d, 判断存在的数据量: %d n", size, count.get());
// 验证10个不存在的数
count = new AtomicInteger();
while (count.get() 10) {
int key = random.nextInt();
if (existentNumbers.contains(key)) {
continue;
} else {
// 这里一定是不存在的数
System.out.println(bloomFilter.contains(key));
count.incrementAndGet();
}
}
}
输出如下：
实际的数据量：1000000, 判断存在的数据量: 1000000
false
true
false
true
true
true
false
false
true
false
这就是前面说到的，当布隆过滤器说某个值 存在时，这个值 可能不存在，当它说某个值 不存在时，那就 肯定不存在，并且还有一定的误判率…
手动实现参考
当然上面的版本特别 low，不过主体思想是不差的，这里也给出一个好一些的版本用作自己实现测试的参考：
import java.util.BitSet;
public class MyBloomFilter {
/**
* 位数组的大小
*/
private static final int DEFAULT_SIZE = 2 24;
/**
* 通过这个数组可以创建 6 个不同的哈希函数
*/
private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};
/**
* 位数组。数组中的元素只能是 0 或者 1
*/
private BitSet bits = new BitSet(DEFAULT_SIZE);
/**
* 存放包含 hash 函数的类的数组
*/
private SimpleHash[] func = new SimpleHash[SEEDS.length];
/**
* 初始化多个包含 hash 函数的类的数组，每个类中的 hash 函数都不一样
*/
public MyBloomFilter() {
// 初始化多个不同的 Hash 函数
for (int i = 0; i SEEDS.length; i++) {
func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
}
}
/**
* 添加元素到位数组
*/
public void add(Object value) {
for (SimpleHash f : func) {
bits.set(f.hash(value), true);
}
}
/**
* 判断指定元素是否存在于位数组
*/
public boolean contains(Object value) {
boolean ret = true;
for (SimpleHash f : func) {
ret = ret && bits.get(f.hash(value));
}
return ret;
}
/**
* 静态内部类。用于 hash 操作！
*/
public static class SimpleHash {
private int cap;
private int seed;
public SimpleHash(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}
/**
* 计算 hash 值
*/
public int hash(Object value) {
int h;
return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h 16)));
}
}
}
使用 Google 开源的 Guava 中自带的布隆过滤器
自己实现的目的主要是为了让自己搞懂布隆过滤器的原理，Guava 中布隆过滤器的实现算是比较权威的，所以实际项目中我们不需要手动实现一个布隆过滤器。
首先我们需要在项目中引入 Guava 的依赖：
dependency
groupIdcom.google.guava/groupId
artifactIdguava/artifactId
version28.0-jre/version
/dependency
实际使用如下：
我们创建了一个最多存放 最多 1500 个整数的布隆过滤器，并且我们可以容忍误判的概率为百分之（0.01）
// 创建布隆过滤器对象
BloomFilterInteger filter = BloomFilter.create(
Funnels.integerFunnel(),
1500,
0.01);
// 判断指定元素是否存在
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
// 将元素添加进布隆过滤器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
在我们的示例中，当
mightContain() 方法返回
true 时，我们可以 99％ 确定该元素在过滤器中，当过滤器返回
false 时，我们可以 100％ 确定该元素不存在于过滤器中。
Guava 提供的布隆过滤器的实现还是很不错的 （想要详细了解的可以看一下它的源码实现），但是它有一个重大的缺陷就是只能单机使用 （另外，容量扩展也不容易），而现在互联网一般都是分布式的场景。为了解决这个问题，我们就需要用到 Redis 中的布隆过滤器了。
相关阅读
参考资料
-
本文已收录至我的 Github 程序员成长系列 **【More Than Java】，学习，不止 Code，欢迎 star：https://github.com/wmyskxz/MoreThanJava** -
**个人公众号** ：wmyskxz，**个人独立域名博客**：wmyskxz.com，坚持原创输出，下方扫码关注，2020，与您共同成长！
非常感谢各位人才能 看到这里，如果觉得本篇文章写得不错，觉得 「我没有三颗心脏」有点东西 的话，求点赞，求关注，求分享，求留言！
创作不易，各位的支持和认可，就是我创作的最大动力，我们下篇文章见！
原文始发于微信公众号（我没有三颗心脏）：
