布隆过滤器Bloom Filter

勤奋不是嘴上说说而已,而是实际的行动,在勤奋的苦度中持之以恒,永不退却。业精于勤,荒于嬉;行成于思,毁于随。在人生的仕途上,我们毫不迟疑地选择勤奋,她是几乎于世界上一切成就的催产婆。只要我们拥着勤奋去思考,拥着勤奋的手去耕耘,用抱勤奋的心去对待工作,浪迹红尘而坚韧不拔,那么,我们的生命就会绽放火花,让人生的时光更加的闪亮而精彩。

导读:本篇文章讲解 布隆过滤器Bloom Filter,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

概述

问题抛出:如何判断一个元素在亿级数据中是否存在?

常规思路:HashMap/HashSet。但是很容易内存溢出。

故而,最需要解决的是如何将庞大的数据load到内存中。而是否可以换种思路,因为只是需要判断数据是否存在,也不是需要把数据查询出来,所以完全没有必要将真正的数据存放进去。

BurtonHoward提出BloomFilter算法主要就是用于解决判断一个元素是否在一个集合中,优势在于只需占用很小的内存空间却有着极高的查询效率。最重要的两个方法是:add() 和contains()。不会存在false negative,即:如果contains()返回false,则该元素一定不在集合中,但会存在一定的true negative,即:如果contains()返回true,则该元素可能在集合中。

原理

一个保存很长的二级制向量,同时结合 Hash 函数实现的。
在这里插入图片描述
如图:

  • 首先需要初始化一个二进制的数组,长度设为 L,同时初始值全为 0 。
  • 当写入一个 A1=1000 的数据时,进行 H 次 hash 函数的运算(这里为 2 次);与 HashMap 有点类似,通过算出的 HashCode 与 L 取模后定位到 0、2 处,将该处的值设为 1。
  • A2=2000 也是同理计算后将 4、7 位置设为 1。
  • 当有一个 B1=1000 需要判断是否存在时,也是做两次 Hash 运算,定位到 0、2 处,此时他们的值都为 1 ,所以认为 B1=1000 存在于集合中。
  • 当有一个 B2=3000 时,第一次 Hash 定位到 index=4 时,数组中的值为 1,所以再进行第二次 Hash 运算,结果定位到 index=5 的值为 0,所以认为 B2=3000 不存在于集合中。

整个的写入、查询的流程就是这样,汇总起来就是:
对写入的数据做 H 次 hash 运算定位到数组中的位置,同时将数据改为 1 。当有数据查询时也是同样的方式定位到数组中。 一旦其中的有一位为 0 则认为数据肯定不存在于集合,否则数据可能存在于集合中。

几个特点:

  1. 只要返回数据不存在,则肯定不存在。
  2. 返回数据存在,但只能是大概率存在。
  3. 同时不能清除其中的数据。

为什么返回存在的数据却是可能存在呢,在有限的数组长度中存放大量的数据,即便是再完美的 Hash 算法也会有冲突,所以有可能两个完全不同的 A、B 两个数据最后定位到的位置是一模一样的。
删除数据也是同理,当我把 B 的数据删除时,其实也相当于是把 A 的数据删掉,这样也会造成后续的误报。
基于以上的 Hash 冲突的前提,所以 BloomFilter 有一定的误报率,这个误报率和 Hash算法的次数 H,以及数组长度 L 都是有关的。

测试

测试一个元素是否属于一个百万元素集合所需耗时

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

@Slf4j
public class Test {
    private static int size = 1000000;
    // 第三个参数为误判率;2个参数,默认误判率为;
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size);

    public static void main(String[] args) {
        for (int i = 0; i < size; i++) {
            bloomFilter.put(i);
        }
        long startTime = System.nanoTime();
        if (bloomFilter.mightContain(29999)) {
            System.out.println("命中了");
        }
        long endTime = System.nanoTime();
        log.info("程序运行时间: " + (endTime - startTime) + "纳秒");
    }
}

输出:命中了
程序运行时间: 219386纳秒
也就是说,判断一个数是否属于一个百万级别的集合,只要0.219ms即可。

Guava

应用

布隆过滤器至少有如下三个使用场景:

  1. 网页爬虫对URL的去重,避免爬取相同的URL地址
  2. 反垃圾邮件,从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱(垃圾短信)
  3. 缓存击穿,将已存在的缓存放到布隆过滤器中,当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。

其中第三点,具体来说:IO是很多系统的瓶颈。当请求消息查询某些信息时,可能先检查缓存中是否有相关信息,有的话返回,如果没有的话可能就要去数据库里面查询。问题:如果大量请求是在请求数据库根本不存在的数据,数据库就要频繁响应这种不必要的IO查询。布隆过滤器可以派生用场。

redis

参考

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/142075.html

(0)

相关推荐

发表回复

登录后才能评论
半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!