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

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

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

北京

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

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

看不清楚,换张图片

免费获取短信验证码

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

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

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

布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。

图片

检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。

图片

接下来,我们看下在Java中怎么使用。

单机版:Guava

首先引入依赖:


    com.google.guava
    guava
    33.2.1-jre

然后使用Guava中的BloomFilter类开始实现:

@Test
public void testBloomFilter() {
    final List itemsToInsert = Arrays.asList("apple", "banana", "cherry", "elderberry");

    // 创建布隆过滤器
    BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 100, 0.01);
    // 当前元素数量为0
    Assertions.assertEquals(0, bloomFilter.approximateElementCount());

    // 向布隆过滤器中插入数据
    for (String item : itemsToInsert) {
        bloomFilter.put(item);
    }
    // 当前元素数量为4
    Assertions.assertEquals(4, bloomFilter.approximateElementCount());

    // 测试已插入的数据
    for (String item : itemsToInsert) {
        Assertions.assertTrue(bloomFilter.mightContain(item), "Item should be in the Bloom Filter: " + item);
    }

    // 测试未插入的数据
    final List itemsNotInserted = Arrays.asList("grape", "orange", "peach", "quince", "raspberry");
    for (String item : itemsNotInserted) {
        Assertions.assertFalse(bloomFilter.mightContain(item), "Item should not be in the Bloom Filter: " + item);
    }
}

Guava实现的是单机版,虽然提供了文件写出的功能,可以将文件分发到分布式系统中,但是这种方式只能是补充。推荐只在单机场景中使用Guava的布隆过滤器。

如果想要在分布式服务中使用,可以选择Redission。

分布式版:Redission

引入依赖:


    org.redisson
    redisson
    3.11.5

使用Docker在本地启一个Redis服务,用来验证:

docker run -d -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest

然后编码测试:

@Test
public void testBloomFilter() {
    // 使用Docker本地启动一个Redis服务用来测试:
    //  docker run -d -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest

    Config config = new Config();
    config.useSingleServer().setAddress("redis://127.0.0.1:6379");

    // 生成key是 myBloomFilter 的存储
    // 会生成两个key,"myBloomFilter"、"{myBloomFilter}:config"
    // "myBloomFilter"是string类型,布隆过滤器的主存
    // "{myBloomFilter}:config"是hash结构,存储元信息,比如大小size、期望容量expectedInsertions、误报率falseProbability、使用的哈希函数数量hashIterations等。
    RBloomFilter bloomFilter = Redisson.create(config)
            .getBloomFilter("myBloomFilter");

    // 初始化布隆过滤器,定义期望容量和误报率
    bloomFilter.tryInit(1000000, 0.01);

    // 准备一些测试数据
    final List itemsToInsert = Arrays.asList("apple", "banana", "cherry", "elderberry");

    // 向布隆过滤器中插入数据
    for (String item : itemsToInsert) {
        bloomFilter.add(item);
    }

    // 测试已插入的数据
    for (String item : itemsToInsert) {
        Assertions.assertTrue(bloomFilter.contains(item), "Item should be in the Bloom Filter: " + item);
    }

    // 测试未插入的数据
    final List itemsNotInserted = Arrays.asList("grape", "orange", "peach", "quince", "raspberry");
    for (String item : itemsNotInserted) {
        Assertions.assertFalse(bloomFilter.contains(item), "Item should not be in the Bloom Filter: " + item);
    }
}

使用Redission的RBloomFilter,会根据布隆过滤器名字在Redis中生成两个key,比如上面代码的名字是“myBloomFilter”,生成的配置为:

  • "myBloomFilter"是string类型,布隆过滤器的主存,用来存储二进制数组;
  • "{myBloomFilter}:config"是hash结构,存储元信息,比如大小size、期望容量expectedInsertions、误报率falseProbability、使用的哈希函数数量hashIterations等。

免责声明:

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

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

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

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

下载Word文档

猜你喜欢

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

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

Java中的布隆过滤器你真的懂了吗

经常会听到大家说起布隆过滤器,但是很多人都只是听过名字,却并不知道其是怎么实现的。下面将详细介绍一下布隆过滤器,并且使用简单的代码演示
2023-05-18

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

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

你了解布隆过滤器的“大家族”吗?

布隆过滤器(Bloom Filter)是1970年由伯顿·霍华德·布隆(Burton Howard Bloom)提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。

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

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

什么是布隆过滤器?你学会了吗?

在对响应时间要求比较严格的情况下,如果我们有里面,那么随着集合中元素数量的增加,我们需要的存储空间越来越大,检索时间也越来越长,导致内存过多开销和时间效率变低。

Java的布隆过滤器如何实现

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

Redis中Bloomfilter布隆过滤器的学习

布隆过滤器是一个非常长的二进制向量和一系列随机哈希函数的组合,可用于检索一个元素是否存在,本文就详细的介绍一下Bloomfilter布隆过滤器,具有一定的参考价值,感兴趣的可以了解一下
2022-12-14

Java中的布隆过滤器原理实现和应用

Java中的布隆过滤器是一种基于哈希函数的数据结构,能够高效地判断元素是否存在于一个集合中。它广泛应用于缓存、网络协议、数据查询等领域,在提高程序性能和减少资源消耗方面具有显著优势
2023-05-17

Redis中Bloom filter布隆过滤器的学习

目录1.概念2.guava实现2.1.依赖2.2.初始化布隆过滤器2.3.布隆过滤器2.4.添加元素或者判断是否存在3.Redisson实现3.1.依赖3.2.注入或测试1.概念​ 布隆过滤器是一个高空间利用率的概率性数据结构,主要目的是
2022-12-14

Java布隆过滤器的原理和实现分析

数组、链表、树等数据结构会存储元素的内容,一旦数据量过大,消耗的内存也会呈现线性增长所以布隆过滤器是为了解决数据量大的一种数据结构。本文就来和大家详细说说布隆过滤器的原理和实现,感兴趣的可以了解一下
2022-11-13

布隆vs布谷鸟:哪种过滤器最适合你的大数据需求?

布隆过滤器(Bloom Filter)和布谷鸟过滤器(Cuckoo Filter)是两种概率型数据结构,用于快速而高效地检查一个元素是否属于一个集合。尽管它们都能够用于这一目的,但在实现细节、性能特点和使用场景上存在不同。

热门标签

编程热搜

编程资源站

目录