什么是布隆过滤器？
首先我们需要谅解布隆过滤器的概念。
布隆过滤器是一个叫做Bloom的老哥1970年提出的。我们可以把它看作由二进制向量(或者说数组)和一系列随即映射函数(哈希函数 )两部分组成的数据结构。相比于我们平时常用的list，map，set等数据结构，它占用空间更少且效率更好。但是缺点是其返回的结果是概率性且不是非常准确的。理论情况下添加到集合中的元素越多，误报的可能性就越大。并且存放在布隆过滤器的数据不容易删除。
总结：一个叫Bloom的人提出了一种来检索元素是否在给定大集合中的数据结构。这种数据结构是高效且性能很好的，但是缺点是具有一定的错误识别率和删除难度。并且理论情况下添加到集合中的 元素越多，误报的可能性就越大。
布隆过滤器原理介绍
当一个元素加入布隆过滤器中的时候，会进行如下操作：
- 使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值(有几个哈希函数得到几个哈希值)。
- 根据得到的哈希值在位数组中把对应下标的值置为1.
当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作：
- 对给定元素再次进行相同的哈希计算
- 得到值之后判断位数组中的每个元素是否都为1，如果都为1说明这个值在布隆过滤器中存在。如果存在一个值不为1的，说明该元素不在布隆过滤器中存在。
举个例子：
image.png
如图所示，当字符串要加入布隆过滤器中时，该字符串由多个哈希函数生成不同的哈希值，然后对应的位数组下标设置为1.当第二次存储相同的字符串时，因为之前对应位置的值已经是1，所以知道此值已存在。
不同的字符串可能哈希出来的位置相同，这种情况我们可以只当增加位数组大小或者调整我们的哈希函数。
综上，布隆过滤器判断某元素存在，有小概率会误判。但是判断某元素不存在，那么这个元素一定不在。
布隆过滤器使用场景
- 判断给定数据是否存在。比如用户登录，当用户量足够多的时候先判断此用户存在，再走登录逻辑.
- 防止缓存穿透(判断请求是否有效避免直接绕过缓存请求数据库)
- 去重：比如爬给定网址的时候对已爬取过的url去重
编码实战
通过java编程手动实现布隆过滤器
我们上面已经说了布隆过滤器的原理，知道了布隆过滤器原理之后就可以自己手动实现一个了。
实现布隆过滤器需要：
- 一个合适大小的位数组保存数据
- 几个不同的哈希函数
- 添加元素到位数组的方法实现
- 判断给定元素是否存在于位数组的方法实现
下面是简单实现的代码demo:
public class MyBloomFilter {
/**
* 初始位数组大小
*/
private static final int DEFAULT_SIZE = 2<<24;
/**
* 六种计算哈希值的给定值
*/
private static final int[] SEEDS = new int[]{3,13,46, 71, 91, 134};
/**
* 位数组
*/
private BitSet bits = new BitSet(DEFAULT_SIZE);
/**
* 计算哈希数组
*/
private SimpleHash[] func = new SimpleHash[SEEDS.length];
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;
}
/**
* 静态内部类。根据给定值计算哈希值
*/
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中的布隆过滤器比较权威。首先我们要在项目中引入：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>28.0-jre</version>
</dependency>
实际使用如下:
// 创建布隆过滤器对象
BloomFilter<Integer> 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));
注意初始化的时候会指定类型，存放元素数和能容忍的误差范围。这几点是为了更好的去定义位数组的大小。
Guava提供的布隆过滤器还是很不错的，但是有个缺陷是只能单机使用，另外扩容很麻烦。现在互联网一般都是分布式的场景，为了解决这个问题，我们就需要用到Redis中的布隆过滤器了。
Redis中的布隆过滤器
介绍
Redis 4.0之后有个Module功能，使其可以使用外部模块扩展其功能。布隆过滤器就是其中的Module。详情可以查看 Redis 官方对 Redis Modules 的介绍 ：https://redis.io/modules
另外，官网推荐了一个 RedisBloom 作为 Redis 布隆过滤器的 Module，地址：https://github.com/RedisBloom/RedisBloom 其他还有：
- redis-lua-scaling-bloom-filter（lua 脚本实现）：https://github.com/erikdubbelboer/redis-lua-scaling-bloom-filter
- pyreBloom（Python 中的快速 Redis 布隆过滤器） ：https://github.com/seomoz/pyreBloom
- ......
RedisBloom 提供了多种语言的客户端支持，包括：Python、Java、JavaScript 和 PHP。
常用命令一览
注意：key:布隆过滤器名称，item:添加的元素
- BF.ADD key item:将元素添加到布隆过滤器中。如果过滤器不存在则创建过滤器
- BF.MADD key item数组：将一个或者多个元素添加到布隆过滤器中。
- BF.EXISTS key item:确定此元素是否存在布隆过滤器中
- BF.MEXISTS key item数组：确定一个或者多个元素是否在布隆过滤器中存在。返回多列结果
- BF.RESERVE key 错误率 容量：创建一个布隆过滤器，名称，容错率，过滤器容量。其实这个命令的参数类似上面Guava创建时候的参数
- BF.INFO key :返回这个布隆过滤器的信息，包括容量，容错率之类的。
反正都是简单的命令，感兴趣的可以自己去redis看下：https://redis.io/commands/bf.add/
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利！
网友评论