布隆过滤器讲解及基于Guava BloomFilter案例

这篇具有很好参考价值的文章主要介绍了布隆过滤器讲解及基于Guava BloomFilter案例。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1、布隆过滤器是什么

2、主要作用

3、存储过程

4、查询过程

5、布隆过滤器的删除操作

6、优点

7、缺点

8、测试误判案例

8.1、引入Guava依赖

8.2、编写测试代码

8.3、测试

8.4、BloomFilter实现原理

 9、总结


推荐博主视频,讲的很棒:布隆过滤器详解

1、布隆过滤器是什么

        布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制(0和1组成的)向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。

  • 布隆过滤器里面就是一个二进制(存储0和1)的数组,下标从0开始

布隆过滤器讲解及基于Guava BloomFilter案例

2、主要作用

  • 通过一个的hash函数,计算出数据的hash值,再把哈希值映射到数组中
  • 判断这个数据是不是存储在这个数组中,不存在则返回0,存在则返回1,其实就是用二进制(0和1)去表示数据是否存在这个数组中

3、存储过程


已下面案例为例:

布隆过滤器讲解及基于Guava BloomFilter案例

步骤:

  1. 布隆过滤器在没有存储任何数据时,默认都是0
  2. 布隆过滤器中有3个哈希(Hash)函数(这3个哈希函数一定是互不影响的),现在传入一个"你好"的值,通过这3个哈希函数,算出对应的哈希值
  3. Hash1函数通过计算得到哈希值,对应数组中下标为3的位置,从而把数据映射至index=3处
  4. 布隆过滤器会把下标为3的二进制向量改为1
  5. 同理,经过其他2个哈希函数,分别存储在下标为5、7的位置,并把0改为1 

4、查询过程

还是以上面的案例为例:

步骤:

  1. 布隆过滤器会根据传入的值,通过3个哈希函数计算出该值存储的下标
  2. 判断该下标是否为1,为1则表示该下标存储了该值,为0则表示没有存储
  3. 由于上述布隆过滤器有3个哈希函数,因此判断该值存不存在,必须满足得到的3个下标的二进制向量值等于1,才能证明该值存在于该数组中,布隆过滤器返回1,只要有一个等于1,则认为该数值中不存在该值,布隆过滤器返回0.

5、布隆过滤器的删除操作

  • 在布隆过滤器中,很难进行删除操作,如下:

布隆过滤器讲解及基于Guava BloomFilter案例

 现在有2个值:

  • 你好
  • hello
  1. 假设上述的2个值在经过Hash函数计算时,得到了相同的hash值(hash冲突),这时他们都存储在下标index=2的位置
  2. 之后,我们需要在布隆过滤器中,移除值"你好"的数据,经过Hash函数计算出该值存储在下标为2的位置
  3. 然后布隆过滤器会把该值删除,并把下标为2的二进值向量改为0
  4. 这时,当我们在查询"hello"是否存在时,布隆过滤器会得到0,认为不存在
  5. 也就是意味着,当多个值存储在同一处下标时,删除任意1个值,其他的值也会被删除
  6. 由于布隆过滤器会造成误删,因此布隆过滤器很难做删除操作

布隆过滤器讲解及基于Guava BloomFilter案例

6、优点

  • 由于布隆过滤器是由二进制数组组成的数据,所占用的空间很小
  • 插入和查询的速度快:布隆过滤器会经过hash函数,计算出哈希值,再映射至数组的下标即可;时间复杂度为O(K),K=hash函数的个数
  • 数据的保密性好,因为数组中存储的不是原始数据,而是0和1的二进制数据

7、缺点

  • 很难进行删除操作
  • 会对数据是否存在,进行误判:由于判断数据的hash值是可能相同的(hash冲突),对把不存在的数据的hash值,计算出于数组中已存储的哈希值相同,得到结果为1,从而造成误判

注意:误判是无法避免的,我们只能减少误判的概率

8、测试误判案例

8.1、引入Guava依赖

  • Guava工具包是由Google提供的,里面封装了布隆过滤器,直接使用即可
<dependency>
	<groupId>com.google.guava</groupId>
	<artifactId>guava</artifactId>
	<version>31.1-jre</version>
</dependency>

8.2、编写测试代码

使用到布隆过滤器的代码都在注释中进行说明了:

package com.shuizhu.test;

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

/**
 * @author 睡竹
 * @date 2023/4/8
 * 布隆过滤器误判率测试案例
 */
public class BloomFilterTest {

    //日志,用于执行记录时间
    private static final Log log = LogFactory.getLog(BloomFilterTest.class);
    
    //模拟布隆过滤器预计存储数据的大小,这里设置为100万
    private static int size = 1000000;
    //设置 期望的误判率
    private static double error = 0.000000000001;
    /**
     *  创建布隆过滤器
     *  Integer:表示过滤器存储的是整数类型的数据
     *  Funnels.integerFunnel():表示过滤器只对整数类型进行判断
     */
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, error);
    //设置样本数据为100万
    private static int total = 1000000;

    public static void main(String[] args) {
        //1、在布隆过滤器中,插入样本数据
        for (int i = 0; i < total; i++) {
            //使用put()插入即可
            bloomFilter.put(i);
        }
        //2、定义一个误判数据量的计量值
        int count = 0;
        //3、误判测试前,打印下一句话,用于测试误判测试时间
        log.warn("误判开始");
        /**
         * 4、添加10万个布隆过滤器中不存在的数据,用于测试误判率
         *
         *    这里直接在total的基础上,再加10万的数据
         */
        for (int i = total; i < total+100000; i++) {
            //mightContain()判断数据是否存在于布隆过滤器中
            if (bloomFilter.mightContain(i)) {
                count++;
                //System.out.println("数据:" + i + "误判了");
            }
        }
        log.warn("误判结束");
        //打印误判数据及耗时
        System.out.println("总共误判数为:" + count);
    }
}

8.3、测试

<1>在误判率为0.01下,执行结果为:

布隆过滤器讲解及基于Guava BloomFilter案例 

  • 在12ms内执行完成
  • 误判数为:947(测试总数为10万)
  • 真实误判率为:947 ÷ 10万 = 0.00947 0.01 ,符合预期

<2>修改误判率为0.03:

布隆过滤器讲解及基于Guava BloomFilter案例  

执行结果如下:

布隆过滤器讲解及基于Guava BloomFilter案例 

  • 在16ms内执行完成
  • 误判数为:3033
  • 真实误判率也与预期的0.03相近

总结:设置的误判率是能直接影响布隆过滤器最终的误判率的,误判率越低,耗时越多

问题:我们是不是把误判率设置为无限小,那么就不存在误判了呢?


<3>修改误判率为0.0000000001

布隆过滤器讲解及基于Guava BloomFilter案例 

该误判率比之前2个案例数值小很多,我们看下执行效果:

 布隆过滤器讲解及基于Guava BloomFilter案例

  • 在25ms内执行完成
  • 误判数为0 

注意:在测试机器上是特别快的,当在高并发下,误判率越小,耗时越多,会给服务器带来性能损耗。

因此:我们需要根据具体的业务需求,设置合理的误判率


8.4、BloomFilter实现原理

以8.3中的案例:

1>在误判率为0.01下,我们debug下:

布隆过滤器讲解及基于Guava BloomFilter案例

debug启动:

布隆过滤器讲解及基于Guava BloomFilter案例

 2>在误判率为0.03下,我们继续debug下:

布隆过滤器讲解及基于Guava BloomFilter案例

3>在误判率为0.0000000001下,我们继续debug下: 

布隆过滤器讲解及基于Guava BloomFilter案例

 9、总结

  • 误差率需要根据具体的业务需求进行设置
  • 误差率越小,所占用的空间就越大,需要的哈希函数也就越多

原因:文章来源地址https://www.toymoban.com/news/detail-407818.html

  1. 因为在一个hash函数下,只有一个函数对数据进行计算,hash值重复概率会很大,当多个hash函数计算同一个数据时,由于每个hash函数是相互隔离的(hash算法不同),因此重复的概率也随之减少。
  2. hash函数越多,计算出的hash值也就越多,hash值越多,对应的二进制数据也就越多,所有占用的空间也就越大

到了这里,关于布隆过滤器讲解及基于Guava BloomFilter案例的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 【SpringBoot篇】基于布隆过滤器,缓存空值,解决缓存穿透问题 (商铺查询时可用)

    缓存穿透是指在使用缓存机制时,大量的请求无法从缓存中获取到结果,导致请求都要直接访问后端存储系统,从而增加了系统的负载和响应时间。 通常的缓存机制是将请求的结果缓存在内存或其他高速存储介质中,当相同的请求再次到达时,可以直接从缓存中获取结果,避

    2024年02月04日
    浏览(42)
  • 算法~布隆过滤器

    布隆过滤器(Bloom Filter)是一种高效的概率数据结构,用于判断一个元素是否存在于集合中。它基于位数组和多个哈希函数,并具有以下特点: Bloom Filter 是一个基于概率的数据结构:它只能告诉我们一个 元素绝对不在集合内 或 可能在集合内 快速查询:布隆过滤器具有快速

    2024年02月05日
    浏览(45)
  • 布隆过滤器及其应用

    布隆过滤器是一种数据结构,具有快速插入和查找的特性,能确定某个字符串一定存在或者可能存在。布隆过滤器有着高效的空间利用率,它不存储具体数据,只存储数据的关键标识,所以占用的空间较小。它的查询结果可能会存在一定误差,但是误差总体可控,同时不支持

    2024年02月03日
    浏览(42)
  • 位图以及布隆过滤器

    本文主要讲解哈希思想的实际应用,位图和布隆过滤器。 讲解位图之前我们先来解答这样一道腾讯的面试题 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。【腾讯】 很多人立马就想到了用哈希表或者红黑树,因为足够

    2024年02月08日
    浏览(52)
  • 布隆过滤器的原理

    布隆过滤器是一种用于检索一个元素是否在一个集合中的数据结构,具有高效的查询性能和较小的内存占用。 布隆过滤器的底层实现主要涉及以下几个步骤: 初始化数组: 首先,初始化一个比较大的数组,数组中的元素用二进制表示,初始值都为0。 Hash计算: 当一个新的元

    2024年01月18日
    浏览(38)
  • Redis----布隆过滤器

    目录 背景 解决方案 什么是布隆过滤器 布隆过滤器的原理 一些其他运用 比如我们在观看新闻或者刷微博的时候,会不停地给我们推荐新的内容,我们发现几乎没有重复的,说明后台已经进行了去重处理,基于如何去重,Redis给出了高效的方案---布隆过滤器 1.记录已经浏览过

    2024年02月09日
    浏览(37)
  • 布隆过滤器详解

    本文全部代码地址 布隆过滤器是一种高效的数据结构,用于判断一个元素是否存在于一个集合中.它的主要优点是速度快,空间占用少,因此在需要快速判断某个元素是否在集合中的场合得到广泛引用. 布隆过滤器就是 一个大型的位数组和几个不一样的无偏hash函数. 所谓无偏就是

    2023年04月22日
    浏览(53)
  • Java实现布隆过滤器

    背景: 为预防大量黑客故意发起非法的时间查询请求,造成缓存击穿,建议采用布隆过滤器的方法解决。布隆过滤器通过一个很长的二进制向量和一系列随机映射函数(哈希函数)来记录与识别某个数据是否在一个集合中。如果数据不在集合中,能被识别出来,不需要到数据

    2024年02月01日
    浏览(46)
  • 哈希的应用——布隆过滤器

    上一篇文章,我们学习了位图,位图在某些场景下是非常适用的,非常快捷方便。 但是,在文章的最后,我们也提出了位图的一些缺陷——比如位图只能映射整型数据,其它类型的数据则不行。 因为位图里面的元素去映射的其实就是下标嘛,而下标的话都是整型啊。 那有没

    2024年02月09日
    浏览(41)
  • 布隆过滤器:原理与应用

    本文已收录至GitHub,推荐阅读 👉 Java随想录 微信公众号:Java随想录 原创不易,注重版权。转载请注明原作者和原文链接 目录 布隆过滤器简介 fpp 布隆过滤器原理 布隆过滤器的特点 布隆过滤器使用 布隆过滤器中的数据可不可以删除 布隆过滤器应该设计为多大 布隆过滤器应

    2024年02月08日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包