1.什么是布隆过滤器
Bloom Filter 会使用一个较大的 bit 数组来保存所有的数据，数组中的每个元素都只占用 1 bit ，并且每个元素只能是 0 或者 1（代表 false 或者 true），用于检索元素是否存在于大集合中的数据结构。
缺点是：有一定的错误识别率
2.原理介绍
核心原理：
数据结构：二进制数组+多个哈希函数组成
添加元素：通过多个哈希函数计算得到多个位数组位置，将这些位置设为1
查询元素：进行相同的哈希计算，判断数组中每个位置的元素是否都为1，如果都为1，则可能存在，如果有一个值不为1，则一定不存在。
不同的字符串可能哈希出来的位置相同，这种情况我们可以适当增加位数组大小或者调整我们的哈希函数。
综上，我们可以得出：布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。
3.使用场景
主要是两种场景：
-
判断给定数据是否存在
缓存穿透防护（拦截不存在的数据请求，避免频繁查询数据库）
邮箱垃圾邮件过滤（判断一个邮件地址是否在垃圾邮件列表中）
黑名单功能（判断一个IP或者手机号等是否在黑名单中）
-
去重
爬虫URL去重（爬给定网址时对已爬过的URL去重）
对巨量QQ号、订单号去重
抖音推荐功能，推荐的视频不重复
4.具体实现（java手写）
了解了布隆过滤器的原理，可以手动实现一个，关键步骤有：
一个合适大小的位数组
几个不同的哈希函数
添加元素到位数组的方法实现
查询方法，即判断元素是否在位数组的方法实现
直接贴一个代码案例：
<pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="java" cid="n93" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">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((cap - 1) & seed * ((h = value.hashCode()) ^ (h >>> 16)));
}
}
}</pre>
5.中间件实现
Guava实现的布隆过滤器
Guava 中布隆过滤器的实现算是比较权威的，缺陷是只能单机使用。要想在分布式场景使用，需要用redis的布隆过滤器。
具体代码实现可以自行搜索
Redis的布隆过滤器
Redis官网推荐了一个 RedisBloom 作为 Redis 布隆过滤器的 Module，地址：https://github.com/RedisBloom/RedisBloom
除此之外，还有其他模块的布隆过滤器。
基础操作命令
| 命令 | 作用 | 示例 |
|---|---|---|
| BF.ADD | 向布隆过滤器添加单个元素，若key不存在则自动创建（默认参数：error_rate=0.01, capacity=100）。 | BF.ADD user_filter "user:1001" |
| BF.MADD | 批量添加多个元素到布隆过滤器。 | BF.MADD user_filter "user:1002" "user:1003" |
| BF.EXISTS | 判断单个元素是否可能存在于过滤器中（返回1可能存在，0一定不存在）。 | BF.EXISTS user_filter "user:1001" |
| BF.MEXISTS | 批量判断多个元素是否存在。 | BF.MEXISTS user_filter "user:1001" "invalid_user" |
实际使用：
<pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="shell" cid="n139" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">127.0.0.1:6379> BF.ADD myFilter java
(integer) 1
127.0.0.1:6379> BF.ADD myFilter javag
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter java
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter javag
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter github
(integer) 0</pre>
