文章详情

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

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2024-11-29 18:24

关注

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

如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,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”,生成的配置为:

来源:看山的小屋内容投诉

免责声明:

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

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

软考中级精品资料免费领

  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯