布隆过滤器的作用是:可用来判断值 可能在集合中 和 绝对不在集合中
布隆过滤器(Bloom Filter)是 1970 年由布隆提出的。它实际上是一个很长的二进制向量(位图)和一系列随机映射函数(hash 函数)。
布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率且删除困难。
布隆过滤器的使用场景比较多,比如我们现在讲的防止缓存穿透、垃圾邮件的检测等。Google chrome 浏览器使用 Bloom Filter 识别恶意链接,Goolge 在 BigTable 中也使用 Bloom Filter 以避免在硬盘中寻找不存在的条目。我公司使用布隆过滤器来对爬虫抓取的 Url 进行重复检查等。
布隆过滤器广泛应用于网页黑名单系统、垃圾邮件过滤系统、爬虫网址判重系统等。
如果没有布隆过滤器,我们实现网页IP黑名单的思路就是创建一个黑名单配置表、或者一个Hash表进行存储,在未知IP访问时判断是否在黑名单,是则禁止访问。当数据量小的时候,是可以这么做的,但如果整个网页黑名单系统包含100亿个网页URL,在数据库查找是很费时的,并且如果每个URL空间为64B,那么需要内存为640GB,一般的服务器很难达到这个需求。
那么,在这种内存不够且检索速度慢的情况下,不妨考虑下布隆过滤器,但业务上要可以忍受判断失误率。
布隆过滤器其实就是位图,也叫位数组,因为这个数组中每一个位置只占有 1 个bit(位),而每个bit只有 0 和 1 两种状态,默认是 0。位数组的大小也就是布隆过滤器的大小。
假设现在我们有一个布隆过滤器,大小为 10,有 3 个 hash 函数。
为了将数据 A 添加到布隆过滤器中,需要经过这 3 个 hash 函数,每个 hash 函数可以产生一个 1 ~ 10 的随机值,也就是产生了 3 个值。我们将布隆过滤器中这 3 个值对应的位置的 0 改成 1,这样这个数据 A 就被添加到了布隆过滤器中。
当我们要判断数据 A 在不在布隆过滤器中时,我们就通过过滤器中的 3 个 hash 函数将数据 A 生成 3 个值,然后看过滤器中这 3 个值对应的位置的值是不是都是 1 ,如果都是 1 那么就说数据 A 可能存在于布隆过滤器中。注意!为什么说 “可能”,因为假设数据 A 通过 3 个 hash 生成的值为 1、5、7,数据 B 为 3、4、6,数据 C 为 1、3、4,当数据 A、B 添加到过滤器中时,判断数据 C 在过滤器中是否存在会得到 “是”。所以说,布隆过滤器会出现误判,只能判断值可能存在于过滤器中。
不得不说 Google Guava 真是一个万能的库,很多东西都封装好了,布隆过滤器也有封装好的实现,我们直接使用即可。
下面我们通过一个小案例来看看布隆过滤器怎么使用,代码如下所示。
<!-- Google Guava 依赖 -->
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>19.0</version>
</dependency>
public static void main(String[] args) {
int total = 1000000;
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
// 初始化 1000000 条数据到过滤器中
for (int i = 0; i < total; i++) {
bloomFilter.put("" + i);
}
// 判断 1~1010000 个数据有多少个在过滤器中
int count = 0;
for (int i = 0; i < total + 10000; i++) {
if(bloomFilter.mightContain("" + i)){
count ++;
}
}
System.out.println("匹配数量:" + count);;
}
通过 BloomFilter.create 创建一个布隆过滤器,初始化 1000000 条数据到过滤器中,然后判断 1~1010000 个数据有多少个在过滤器中,正常来说肯定是匹配到 1000000 个,事实上输出结果如下:
匹配数量:1000309
这里多了 309 条就是出现了误判。错误率调节是一个 double 类型的参数,默认值是 0.03% ,1010000 x (0.03%) = 303,这里的错误数量 309 处于这个范围内。
这里将错误率改成 0.0003%,如下:
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total, 0.0003);
错误数量应该是 1010000 × (0.0003/100) = 3.03 左右,输出结果如下:
匹配数量:1000004
满足!!!