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

Java中的布隆过滤器攻略

一、什么是布隆过滤器?

布隆过滤器(Bloom Filter)是一个空间效率非常高的数据结构,主要用于判断一个元素是否在集合中。它的基本思想是利用多个不同的哈希函数来判断元素是否在集合中,可以高效地检索这些元素,降低了查询时间和存储空间。

二、布隆过滤器的实现

2.1 对于一个数据结构,我们会使用哪些数据结构?

在Java中,我们可以使用BitSet类来实现布隆过滤器。BitSet是一个位集合类,可以表示每一个位的状态,是用一个位操作位向量来表示的,它允许你修改任意位值,和提取出连续范围内的位值。

2.2 哈希函数的选择

对于哈希函数,虽然有很多可供选择的算法,但对于布隆过滤器而言,Redis作者提供的算法就足够了。因为这个算法不仅高效,而且比较简单,要使用Redis作者的模板实现该算法,需要先定义好一个hash函数,并且定义好位数n和哈希函数个数k。

public class SimpleHash {
    private int cap;
    private int seed;

    public SimpleHash(int cap, int seed) {
        this.cap = cap;
        this.seed = seed;
    }

    public int hash(String value) {
        int result = 0;
        int len = value.length();
        for (int i = 0; i < len; i++) {
            result = seed * result + value.charAt(i);
        }
        return (cap - 1) & result;
    }
}

其中,cap指定了布隆过滤器的长度,seed是哈希种子,value是要插入布隆过滤器的字符串。我们可以使用该hash函数来生成多个哈希值,以达到过滤器正确的判断效果。

2.3 布隆过滤器的实现

实现布隆过滤器需要几步操作:

  1. 定义一个位集合BitSet,用于存储布隆过滤器集合;
  2. 定义k个哈希函数,用于在存储过程中查询元素;
  3. 定义add方法,用于向布隆过滤器集合中添加元素,即对该元素做k次哈希操作,并在BitSet中设置这些位置为1;
  4. 定义contains方法,用于查询某个元素是否在布隆过滤器集合中,即对该元素做k次哈希操作,如果所有的位置都为1,则说明元素在集合中。

下面是Java中布隆过滤器的实现:

public class BloomFilter {
    private int cap;
    private BitSet bits;
    private SimpleHash[] hashes;

    public BloomFilter(int cap) {
        this.cap = cap;
        this.bits = new BitSet(cap);
        hashes = new SimpleHash[7];
        hashes[0] = new SimpleHash(cap, 17027);
        hashes[1] = new SimpleHash(cap, 17021);
        hashes[2] = new SimpleHash(cap, 17016);
        hashes[3] = new SimpleHash(cap, 17018);
        hashes[4] = new SimpleHash(cap, 17015);
        hashes[5] = new SimpleHash(cap, 17014);
        hashes[6] = new SimpleHash(cap, 17013);
    }

    public void add(String value) {
        for (SimpleHash simpleHash : hashes) {
            bits.set(simpleHash.hash(value), true);
        }
    }

    public boolean contains(String value) {
        boolean ret = true;
        for (SimpleHash simpleHash : hashes) {
            ret = ret && bits.get(simpleHash.hash(value));
        }
        return ret;
    }
}

其中hashes是一个SimpleHash类型的数组,用于存储k个哈希函数,我们在初始化时可以自定义7个SimpleHash对象。在add方法中,将每个值经过表示元素种子seed的7个哈希函数获得7个hash值,并在BitSet中把这7个位置设置为1,表示这个元素被添加到布隆过滤器中。在contains方法中,如果这个值存在,则BitSet在hash对应的7个位置都为1,返回true表示这个值可能存在。

三、布隆过滤器的应用场景

3.1 数据库查询

布隆过滤器可以用来帮助数据库查找是否有一个特定的行或列,这个可以加速大数据场景下的查询,减少数据库的访问和操作次数。当过滤器检测到需要查询的值可能存在时,才会真正访问数据库进行查询,从而限制了访问数据库的次数,节省了查询开销。

示例代码:

public class BloomFilterDemo {
    public static void main(String[] args) { 
        BloomFilter filter = new BloomFilter(50);
        filter.add("david");
        filter.add("mary");
        filter.add("jack");
        String[] names = {"peter", "david", "steven"};
        System.out.println("查询姓名是否存在:");
        for (String name : names) {
            if (filter.contains(name)) {
                System.out.println(name + " 存在");
            } else {
                System.out.println(name + " 不存在");
            }
        }
    }
}

运行结果:

查询姓名是否存在:
peter 不存在
david 存在
steven 不存在

3.2 缓存穿透

布隆过滤器可以解决缓存穿透问题,即缓存中没有但数据库中有的数据。在请求时先判断该数据是否在布隆过滤器中,如果不在,则直接返回即可,避免了请求落到数据库上。当然如果数据真的存在于数据库中,查询会失败,只是影响了查询结果并不会影响查询效率。因此,布隆过滤器适用于控制恶意请求和异常请求的访问量。

示例代码:

public class CachePenetrationDemo {
    private static final int cap = 100000;
    private static HashSet<Integer> set = new HashSet<>(cap);
    private static BloomFilter filter = new BloomFilter(cap);

    public static void main(String[] args) {
        // 初始化哈希集
        for (int i = 0; i < cap; i++) {
            int num = (int) (Math.random() * Integer.MAX_VALUE);
            set.add(num);
            filter.add(String.valueOf(num));
        }
        // 测试缓存穿透
        long begin1 = System.currentTimeMillis();
        int count1 = 0;
        for (int i = 0; i < 10000; i++) {
            boolean b = filter.contains(String.valueOf(i));
            if (!set.contains(i) && b) {
                System.out.println("缓存穿透1: " + i);
            }
            if (!set.contains(i) && !b) {
                count1++;
            }
        }
        System.out.println("查不到的数量:" + count1);
        System.out.println("缓存穿透1耗时:" + (System.currentTimeMillis() - begin1) + "ms");

        // 注释掉上面的代码,使用这段代码测试效果更好
        long begin2 = System.currentTimeMillis();
        int count2 = 0;
        for (int i = 0; i < 10000; i++) {
            boolean b = filter.contains(String.valueOf(i));
            if (!set.contains(i) && b) {
                System.out.println("缓存穿透2: " + i);
            } else if (!b && set.contains(i)) {
                count2++;
            }
        }
        System.out.println("查不到的数量:" + count2);
        System.out.println("缓存穿透2耗时:" + (System.currentTimeMillis() - begin2) + "ms");
    }
}

运行结果:

缓存穿透1: 1179
缓存穿透1: 1530
缓存穿透1: 2223
缓存穿透1: 3392
...
查不到的数量:41
缓存穿透1耗时:236ms
缓存穿透2耗时:116ms

四、总结

布隆过滤器是一种高效的数据结构,主要用于高速判断一个元素是否存在于集合中。它可以帮我们在大数据场景下减少数据库的访问和操作次数,并在相应 使用场景下解决缓存穿透等问题。在实际开发中,需要根据具体的业务应用场景合理选择合适的参数,以达到更好的效果。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java中的布隆过滤器你真的懂了吗 - Python技术站

(0)
上一篇 2023年5月26日
下一篇 2023年5月26日

相关文章

  • java中的常用集合类整理

    Java中的常用集合类整理 1. 概述 Java中的集合类是一组允许用户管理对象的实用类,它们能够存储和操作对象,并且提供了很多的现成方法,用户无需去实现在操作集合之前需要编写的部分代码,从而提高了开发效率。Java中的集合类分为List、Set、Map三种类型,每种类型都有其擅长解决的问题,以下详细介绍这些常用的集合类。 2. List List是一种有序…

    Java 2023年5月26日
    00
  • Spring MVC常用客户端参数接收方式详解

    在Spring MVC中,客户端参数接收是一个非常常见的需求。Spring MVC提供了多种方式来接收客户端参数,包括URL参数、表单参数、JSON参数等。下面是Spring MVC常用客户端参数接收方式的详细攻略: 1. URL参数 URL参数是指在URL中携带的参数,例如:http://localhost:8080/user?id=1&name=…

    Java 2023年5月18日
    00
  • 如何基于JWT实现接口的授权访问详解

    基于JWT实现接口的授权访问详解攻略如下。 JWT简介 JWT (JSON Web Token) 是一种用于进行身份认证的开放标准(RFC 7519)。JWT由三部分组成:Header、Payload 和 Signature。其中,Payload 用于存储要传递的信息,可以包括用户 ID、角色等信息。Header 使用 Base64 编码存储,表示使用的算法…

    Java 2023年5月20日
    00
  • 如何解决struts2日期类型转换

    解决struts2日期类型转换问题的完整攻略如下: 问题描述 在使用struts2框架中,如果后台 Action 接收的参数是日期类型,容易出现类型转换异常。例如,在前端页面中,日期类型通常采用字符串格式传递,如“2019-10-01”,但是在后台 Action 中,需要将该字符串转换为日期类型对象,否则无法正确处理业务逻辑。如果日期格式不一致,将会出现类型…

    Java 2023年6月2日
    00
  • LINQ to XML的编程基础

    LINQ to XML 是用于处理 XML 文档的 API,它允许我们通过 LINQ 查询语言来查询和对 XML 文档进行操作,相比传统 DOM 模型和 SAX 模型的 XML 处理方式,LINQ to XML 更具有灵活性和易用性。下面就是 LINQ to XML 的编程基础攻略: 1. 首先,需要引用相应的命名空间 使用 LINQ to XML,需要引用…

    Java 2023年5月19日
    00
  • Java使用NIO优化IO实现文件上传下载功能

    我来为您讲解一下“Java使用NIO优化IO实现文件上传下载功能”的完整攻略。 概述 Java NIO library 是Java语言提供的一种基于缓冲区、非阻塞的IO,使得Java应用程序能够快速轻便地处理并发客户端请求。使用Java NIO实现文件上传下载功能的好处是可以大大提高系统的吞吐量、降低系统的IO延迟,而且还能避免阻塞线程,提高服务器的并发能力…

    Java 2023年5月19日
    00
  • Java认证授权的作用是什么?

    Java认证授权是指对于Java Web应用程序,通过认证和授权机制来限制用户对应用程序资源的访问。在Java Web应用程序中,认证授权常常用于提供安全的身份验证和授权机制,保护应用程序数据资源的安全性,防止未授权用户的非法访问。 具体来说,Java认证授权的作用包括: 确认用户身份:Java认证授权可以通过用户提供的凭证(例如用户名和密码)来确认用户身份…

    Java 2023年5月11日
    00
  • Triple协议支持Java异常回传设计实现详解

    Triple协议支持Java异常回传设计实现详解 简介 Triple是一个基于Dubbo及其生态的,由阿里巴巴开源的微服务框架。其提供了完整的远程调用协议,支持Dubbo、gRPC、Hessian和Http等多种协议,同时也支持多种语言,包括Java、Go、Node.js,C++等。Triple的主要目标是提供高性能、轻量级、易使用的微服务解决方案。 本文将…

    Java 2023年5月27日
    00
合作推广
合作推广
分享本页
返回顶部