我的编程空间,编程开发者的网络收藏夹
学习永远不晚

Java布隆过滤器怎么使用

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

Java布隆过滤器怎么使用

本文小编为大家详细介绍“Java布隆过滤器怎么使用”,内容详细,步骤清晰,细节处理妥当,希望这篇“Java布隆过滤器怎么使用”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。

通常你判断某个元素是否存在用的是什么?

很多人想到的是HashMap。

确实可以将值映射到 HashMap 的 Key,然后可以在 O(1) 的时间复杂度内返回结果,效率奇高。但是 HashMap 的实现也有缺点,例如存储容量占比高,考虑到负载因子的存在,通常空间是不能被用满的,而一旦你的值很多例如上亿的时候,那 HashMap 占据的内存大小就变得很可观了。

一、布隆过滤器简介

布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中

如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为O(n),O(log n),O(1)。

布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。 –引自《维基百科,自由的百科全书》

本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure)高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的。

当你往简单数组或列表中插入新数据时,将不会根据插入项的值来确定该插入项的索引值。这意味着新插入项的索引值与数据值之间没有直接关系。这样的话,当你需要在数组或列表中搜索相应值的时候,你必须遍历已有的集合。若集合中存在大量的数据,就会影响数据查找的效率。

针对这个问题,你可以考虑使用哈希表。利用哈希表你可以通过对 “值” 进行哈希处理来获得该值对应的键或索引值,然后把该值存放到列表中对应的索引位置。这意味着索引值是由插入项的值所确定的,当你需要判断列表中是否存在该值时,只需要对值进行哈希处理并在相应的索引位置进行搜索即可,这时的搜索速度是非常快的。

二、布隆过滤器的结构

Java布隆过滤器怎么使用

根据定义,布隆过滤器可以检查值是 “可能在集合中” 还是 “绝对不在集合中”。“可能” 表示有一定的概率,也就是说可能存在一定为误判率。那为什么会存在误判呢?下面我们来分析一下具体的原因。

布隆过滤器(Bloom Filter)本质上是由长度为 m 的位向量或位列表(仅包含 0 或 1 位值的列表)组成,最初所有的值均设置为 0,如下图所示。

Java布隆过滤器怎么使用

为了将数据项添加到布隆过滤器中,我们会提供 K 个不同的哈希函数,并将结果位置上对应位的值置为 “1”。在前面所提到的哈希表中,我们使用的是单个哈希函数,因此只能输出单个索引值。而对于布隆过滤器来说,我们将使用多个哈希函数,这将会产生多个索引值。

Java布隆过滤器怎么使用

如上图所示,当输入 “semlinker” 时,预设的 3 个哈希函数将输出 2、4、6,我们把相应位置 1。假设另一个输入 ”kakuqo“,哈希函数输出 3、4 和 7。你可能已经注意到,索引位 4 已经被先前的 “semlinker” 标记了。此时,我们已经使用 “semlinker” 和 ”kakuqo“ 两个输入值,填充了位向量。当前位向量的标记状态为:

Java布隆过滤器怎么使用

当对值进行搜索时,与哈希表类似,我们将使用 3 个哈希函数对 ”搜索的值“ 进行哈希运算,并查看其生成的索引值。假设,当我们搜索 ”fullstack“ 时,3 个哈希函数输出的 3 个索引值分别是 2、3 和 7:

Java布隆过滤器怎么使用

从上图可以看出,相应的索引位都被置为 1,这意味着我们可以说 ”fullstack“ 可能已经插入到集合中。事实上这是误报的情形,产生的原因是由于哈希碰撞导致的巧合而将不同的元素存储在相同的比特位上。

那么我们如何选择哈希函数个数和布隆过滤器长度很显然,过小的布隆过滤器很快所有的bit位均为1,那么查询任何值都会返回“可能存在”,起不到过滤的目的了。布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。

另外,哈希函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置位 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变高。

Java布隆过滤器怎么使用

如何选择适合业务的 k 和 m 值呢,幸运的是,布隆过滤器有一个可预测的误判率(FPP):

Java布隆过滤器怎么使用

n 是已经添加元素的数量;

k 哈希的次数;

m 布隆过滤器的长度(如比特数组的大小);

极端情况下,当布隆过滤器没有空闲空间时(满),每一次查询都会返回 true 。这也就意味着 m 的选择取决于期望预计添加元素的数量 n ,并且 m 需要远远大于 n 。

实际情况中,布隆过滤器的长度 m 可以根据给定的误判率(FFP)的和期望添加的元素个数 n 的通过如下公式计算:

Java布隆过滤器怎么使用

了解完上述的内容之后,我们可以得出一个结论:当我们搜索一个值的时候,若该值经过 K 个哈希函数运算后的任何一个索引位为 ”0“,那么该值肯定不在集合中。但如果所有哈希索引值均为 ”1“,则只能说该搜索的值可能存在集合中。

三、布隆过滤器应用

在实际工作中,布隆过滤器常见的应用场景如下:

  • 网页爬虫对 URL 去重,避免爬取相同的 URL 地址;

  • 反垃圾邮件,从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱;

  • Google Chrome 使用布隆过滤器识别恶意 URL;

  • Medium 使用布隆过滤器避免推荐给用户已经读过的文章;

  • Google BigTable,Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。

除了上述的应用场景之外,布隆过滤器还有一个应用场景就是解决缓存穿透的问题。所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据,这样每次服务调用都会到数据库中进行查询,如果这类请求比较多的话,就会导致数据库压力增大,这样缓存就失去了意义。

利用布隆过滤器我们可以预先把数据查询的主键,比如用户 ID 或文章 ID 缓存到过滤器中。当根据 ID 进行数据查询的时候,我们先判断该 ID 是否存在,若存在的话,则进行下一步处理。若不存在的话,直接返回,这样就不会触发后续的数据库查询。需要注意的是缓存穿透不能完全解决,我们只能将其控制在一个可以容忍的范围内。

四、布隆过滤器的优缺点

优点

相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数(O(k))。另外,散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集,其它任何数据结构都不能;

k和m相同,使用同一组散列函数的两个布隆过滤器的交并运算可以使用位操作进行。

缺点

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。

另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。

五、布隆过滤器实战

布隆过滤器有很多实现和优化,由 Google 开发著名的 Guava 库就提供了布隆过滤器(Bloom Filter)的实现。在基于 Maven 的 Java 项目中要使用 Guava 提供的布隆过滤器,只需要引入以下坐标:

<dependency>   <groupId>com.google.guava</groupId>   <artifactId>guava</artifactId>   <version>28.0-jre</version></dependency>

在导入 Guava 库后,我们新建一个 BloomFilterDemo 类,在 main 方法中我们通过 BloomFilter.create 方法来创建一个布隆过滤器,接着我们初始化 1 百万条数据到过滤器中,然后在原有的基础上增加 10000 条数据并判断这些数据是否存在布隆过滤器中:

import com.google.common.base.Charsets;import com.google.common.hash.BloomFilter;import com.google.common.hash.Funnels;public class BloomFilterDemo {    public static void main(String[] args) {        int total = 1000000; // 总数量        BloomFilter<CharSequence> bf =           BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);        // 初始化 1000000 条数据到过滤器中        for (int i = 0; i < total; i++) {            bf.put("" + i);        }        // 判断值是否存在过滤器中        int count = 0;        for (int i = 0; i < total + 10000; i++) {            if (bf.mightContain("" + i)) {                count++;            }        }        System.out.println("已匹配数量 " + count);    }}

当以上代码运行后,控制台会输出以下结果:

已匹配数量 1000309

很明显以上的输出结果已经出现了误报,因为相比预期的结果多了 309 个元素,误判率为:

309/(1000000 + 10000) * 100 &asymp; 0.030594059405940593

如果要提高匹配精度的话,我们可以在创建布隆过滤器的时候设置误判率 fpp:

BloomFilter<CharSequence> bf = BloomFilter.create(
  Funnels.stringFunnel(Charsets.UTF_8), total, 0.0002
);

在 BloomFilter 内部,误判率 fpp 的默认值是 0.03:

// com/google/common/hash/BloomFilter.classpublic static &lt;T&gt; BloomFilter&lt;T&gt; create(Funnel&lt;? super T&gt; funnel, long expectedInsertions) {  return create(funnel, expectedInsertions, 0.03D);}

在重新设置误判率为 0.0002 之后,我们重新运行程序,这时控制台会输出以下结果:

已匹配数量 1000003

通过观察以上的结果,可知误判率 fpp 的值越小,匹配的精度越高。当减少误判率 fpp 的值,需要的存储空间也越大,所以在实际使用过程中需要在误判率和存储空间之间做个权衡。

读到这里,这篇“Java布隆过滤器怎么使用”文章已经介绍完毕,想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会,如果想了解更多相关内容的文章,欢迎关注编程网行业资讯频道。

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

Java布隆过滤器怎么使用

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

Java布隆过滤器怎么使用

本文小编为大家详细介绍“Java布隆过滤器怎么使用”,内容详细,步骤清晰,细节处理妥当,希望这篇“Java布隆过滤器怎么使用”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。通常你判断某个元素是否存在用的是什么?很多
2023-06-29

如何在 Java 中实现布隆过滤器?(java怎么实现布隆过滤器)

在Java开发中,布隆过滤器是一种用于快速判断元素是否存在的数据结构。它具有高效的空间和时间复杂度,特别适用于大规模数据的去重和判断。下面将详细介绍如何在Java中实现布隆过滤器。一、了解布隆过滤器的原理布隆过滤器的核心
如何在 Java 中实现布隆过滤器?(java怎么实现布隆过滤器)
Java2024-12-22

Java怎么实现布隆过滤器

这篇“Java怎么实现布隆过滤器”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“Java怎么实现布隆过滤器”文章吧。什么是布隆
2023-07-05

什么是布隆过滤器?如何实现布隆过滤器?

以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?

什么是布隆过滤器?

布隆过滤器是一种基于哈希函数的概率性数据结构,用于判断元素是否属于给定集合。其原理是将元素映射到位数组中,并通过查询这些位置来判断元素是否可能存在于集合中。布隆过滤器以其空间效率和快速查询著称,广泛应用于网络安全、缓存系统和数据库等领域。其缺点是可能出现假阳性,但可以通过调整其参数来控制假阳性率。扩展版本的布隆过滤器,如可计数布隆过滤器和局部敏感哈希布隆过滤器,可用于解决特定问题,如近似最近邻搜索和动态集合维护。
什么是布隆过滤器?
2024-04-02

Java的布隆过滤器如何实现

今天小编给大家分享一下Java的布隆过滤器如何实现的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。BitMap现代计算机用二进
2023-06-29

redis布隆过滤器的作用是什么

Redis布隆过滤器是一种数据结构,用于快速判断一个元素是否存在于一个集合中。它可以高效地判断一个元素是否可能在集合中,但无法确保元素一定在集合中或者排除元素已经在集合中。布隆过滤器通常用于减少对数据库的查询次数,节省资源和时间。常见的应用
redis布隆过滤器的作用是什么
2024-04-09

布隆过滤器,你用对了吗?

布隆过滤器是一种简单但非常有效的数据结构,特别适用于大规模数据的快速查找和去重等场景。

Java中的布隆过滤器,你知道吗?

布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

牛哄哄的布隆过滤器,有什么用?

日常开发中,大家经常使用缓存,但是你知道大型的互联网公司面对高并发流量,要注意缓存穿透问题吗?

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录