@[toc]
1. 什么是布隆过滤器
布隆过滤器（Bloom Filter）是一个叫做Bloom 于1970年提出的。我们可以把它看做由二进制向量（或者说位数组）和一系列随机映射函数（哈希函数）两部分组成的数据结构。相比于我们平时用的 List 、Map 、Set 等数据结构，它占用看见更少并且效率更高。但是缺点是其返回的结果是概率性的，而不是非常准确的。理论情况下添加到集合中的元素越多，误报的可能性就越大，并且，存放在布隆过滤器的数据不易删除。
位数组中的每个元素都只占用 1 bit , 并且每个元素只能是0 或 1 。这样申请一个 100w 个元素的位数组只占用 1000000Bit / 8 = 125000 Byte = 125000 / 10214 kb ≈ 122kb 的空间
2. 布隆过滤器使用场景
- 防止缓存穿透：用户查询一个数据导致缓存于数据库都未命中, 这就相当于缓存穿透， 布隆过滤器（判断请求的数据是否有效避免直接绕过缓存请求数据库）等等
- 去重：爬虫我们爬取的url千万，如何判断这个 url 我们是否爬过
- 邮箱过滤：判断是否为垃圾邮件
3. 布隆过滤器原理介绍
添加元素
当一个元素加入布隆过滤器中的时候：
- 使用布隆过滤器的哈希函数再次进行相同的 hash 计算，算出一个值
- 得到值之后判断位数组中每个元素是否都为1，如果值都为1，那么说明这个值在布隆过滤器中，如果存在一个值不为1，说明该元素不在布隆过滤器中
如图所示，当字符串要加入布隆过滤器中时，计算 hash(key) 值，然后将其对应的位数组的下表设置为1 （当数组初始化时，所有位置均为0）
获取元素
布隆过滤器中如果判断某个字符串是否在布隆过滤器中时，只需要对该 hash 值重新计算，得到值之后判断位数中的每个元素是否都为1，如果为1，说明这个值在布隆过滤器中，如果值不为1，该元素不在布隆过滤器中
不同的字符串可能哈希出来的位置相同，这种情况我们可以适当增加位数组大小或者调整我们的哈希函数。
4. Java手写布隆过滤器
- 实现初始化的数组保存数据
- 计算 hash 值
- 添加到布隆过滤器数组
- 判断元素是否存在
public class BloomFileter {
/**
* 初始化大小
*/
private static final int DEFAULT_SIZE = 2 << 24;
/**
* 位数组。数组中到元素只能是 0 和 1
*/
private BitSet bits = new BitSet(DEFAULT_SIZE);
/**
* 计算hash值
* @param key
* @return
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : Math.abs((h = key.hashCode()) ^ (h >>> 16));
}
public BloomFileter(){
}
/**
* 添加元素到位数组
*/
public void add(Object value) {
bits.set(hash(value), true);
}
/**
* 判断指定元素是否存在于位数组
*/
public boolean contains(Object value) {
return bits.get(hash(value));
}
}
测试
public static void main(String[] args) {
String value1 = "https://javaguide.cn/";
String value2 = "https://github.com/Snailclimb";
BloomFileter filter = new BloomFileter();
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
filter.add(value1);
filter.add(value2);
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
}
false
false
true
true
5. 利用Google开源的Guava中自带的布隆过滤器
Guava 中布隆过滤器的实现算是比较权威的
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>28.0-jre</version>
</dependency>
public class GuavaBloomFilter {
public static void main(String[] args) {
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,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));
}
}
6. Redis中的布隆过滤器
我们知道计算机是以二进制作为底层存储到基础单位，一个字节等于8位在 Redis 中，Bitmaps 提供了一套命令操作类似上面字符串的每一位
setbit :
getbit :
bitcount
Redisson:
public class RedissonBloomFilter {
public static void main(String[] args) {
Config config = new Config();
config.useSingleServer().setAddress("redis://192.168.14.104:6379");
config.useSingleServer().setPassword("123");
//构造Redisson
RedissonClient redisson = Redisson.create(config);
RBloomFilter<String> bloomFilter = redisson.getBloomFilter("phoneList");
//初始化布隆过滤器：预计元素为100000000L,误差率为3%
bloomFilter.tryInit(100000000L,0.03);
//将号码10086插入到布隆过滤器中
bloomFilter.add("10086");
//判断下面号码是否在布隆过滤器中
System.out.println(bloomFilter.contains("123456"));//false
System.out.println(bloomFilter.contains("10086"));//true
}
}
个人博客地址：http://blog.yanxiaolong.cn ｜ <font color = "orange"> 『纵有疾风起，人生不言弃』 </font>
