布隆过滤器(Bloom Filter)原理+实战

admin2024-09-11  21

布隆过滤器的作用是:可用来判断值 可能在集合中 和 绝对不在集合中

介绍

布隆过滤器(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

满足!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!