如果想要判断一个元素是不是在一个集合中存在，一般的想法是将所有元素保存起来，然后再拿着这个元素在集合中一个一个进行比对。但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。 针对这种需要在大量数据中去判断某一个值是事否存在的情况，1970年由布隆提出了布隆过滤器的概念。布隆过滤器本质是一个位数组，位数组就是数组的每个元素都只占用 1 bit 。每个元素只能是 0 或者 1。这样申请一个 10000 个元素的位数组只占用 10000 / 8 = 1250 字节 的空间。布隆过滤器除了一个位数组，还有 n个哈希函数。
它具体的实现思想是并不将具体的数据存储在数组中，而是通过hash函数对要存储的数据进行三次Hash运算，并将hash运算的结果做为位数组的下标，将对应的数组元素修改为1。
例如：我们要将"oracle"、"database"、"filter"存储到布隆过滤器中可以这样做。如下图所示
从上图中可以看到，我们有三个hash函数（h1()、h2()、h3()）和一个位数组，oracle经过三个hash函数，得到第1、4、5位为1，database同理得到2、5、10位1，这样如果我们需要判断oracle是否在此位数组中，则通过hash函数判断位数组的1、4、5位是否均为1，如果均为1，则判断oracle在此位数组中，database同理。这就是布隆过滤器判断元素是否在集合中的原理。
但同学们也会发现，如果我们现在要判断"mysql"是否存在，例如它通过三次hash运算得到的值分别是4,5,10。现在即使你的位数中没有存储“mysql”,布隆过滤器也会判断它存在。这是因为"oracle"、"database"、"filter"算出的hash值已经导致上面的三个位置的值被改为了1，这样就会导致误判。但是可以保证的是，如果布隆过滤器判断一个元素不在一个集合中，那这个元素一定不会再集合中。
产生上面误判的主要原因是hash碰撞导致的。但如果我们将位数组设置的足够大，并且让hash运算执行的次数多一些，这样就会降低误判率。
布隆过率器还有另一个问题就是不能删除。这是因为在位数组上的同一个点有可能有多个输入值的映射，如果删除了会影响布隆过滤器里其他元素的判断结果。
所以我们可以总结出布隆过滤器的优缺点如下：
- 优点：
- 所占空间小（并不存储真正的数据），空间效率高
- 查询时间短
- 缺点:
- 元素添加到数组中后，不能被删除
- 有一定的误判率
- 解决缓存穿透问题，缓存穿透是指查询一个一定不存在的数据，由于缓存是不命中就到数据库中去查，并且出于容错考虑，如果从数据库中查不到数据则不写入缓存，这将导致这个不存在的数据每次请求都要到数据库中去查询，失去了缓存的意义。在流量大时，可能数据库就挂掉了，要是有人利用不存在的key频繁攻击我们的应用，这就是漏洞。这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则再到数据库中查。如果不在布隆器中，则直接返回
- 在业务场景中可以用来判断用户是否阅读过某些文章或视频，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。
- 黑名单：比如在邮件系统中可以使用布隆器设置黑名单，判断邮件地址是否在黑名单中。也可以设IP黑名单防止网格爬虫等。
- 垃圾邮件过滤，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱。
package com.heima.rbac.controller;
import java.util.BitSet;
public class MyBloomFilter {
/**
* 位数组的大小
*/
private static final int DEFAULT_SIZE = 2 << 24;
/**
* 通过这个数组可以创建 6 个不同的哈希函数
*/
private static final int[] SEEDS = new int[]{5, 17, 48, 73, 93, 132};
/**
* 位数组。数组中的元素只能是 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)));
}
}
}
redis 在 4.0 的版本中加入了 module 功能，布隆过滤器可以通过 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通过加载 module 来使用 redis 中的布隆过滤器。但是这不是最简单的方式，使用 docker 可以直接在 redis 中体验布隆过滤器。
> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli
redis 布隆过滤器主要就两个命令：
- bf.add 添加元素到布隆过滤器中：bf.add urls http://www.itcast.com。
- bf.exists 判断某个元素是否在过滤器中：bf.exists urls http://www.itcast.com。
上面说过布隆过滤器存在误判的情况，在 redis 中有两个值决定布隆过滤器的准确率：
- ERRor_rate：允许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间也就越大。
- initial_size：布隆过滤器可以储存的元素个数，当实际存储的元素个数超过这个值之后，过滤器的准确率会下降。
redis 中有一个命令可以来设置这两个值：
bf.reserve urls 0.01 100
三个参数的含义：
- 第一个值是过滤器的名字。
- 第二个值为 error_rate 的值。
- 第三个值为 initial_size 的值。
使用这个命令要注意一点：执行这个命令之前过滤器的名字应该不存在，如果执行之前就存在会报错：(error) ERR item exists