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 StackOverflowError详解

    Java StackOverflowError详解 什么是StackOverflowError? StackOverflowError是在Java虚拟机内存不足时抛出的错误之一,通常是由于方法调用栈溢出而引起的。当我们递归调用一个方法时,每次调用都会将方法运行时需要的一些数据压入调用栈中,包括方法参数、局部变量以及返回地址等,当调用栈已经满了而仍需要入栈时就…

    Java 2023年5月27日
    00
  • 浅析Java常用API(Scanner,Random)匿名对象

    那么让我们来浅析Java常用API(Scanner,Random)匿名对象的攻略。 什么是匿名对象 在Java中,我们可以通过new 关键字创建一个对象,然后用这个对象调用它所对应的方法。而匿名对象就是使用对象名称时,省略了对象的创建过程,直接调用对象方法或属性。称之为匿名对象。 匿名对象的优缺点 匿名对象的优点是可以方便快速的创建出对象,并且可以一次性调用…

    Java 2023年5月26日
    00
  • Spring Boot整合Spring Data JPA过程解析

    下面我会详细讲解“Spring Boot整合Spring Data JPA”的攻略,包括搭建环境、配置文件、实体类、DAO接口、Service接口和Controller等内容。并附加两个示例供您参考。 环境搭建 首先,你需要在Maven项目中添加以下依赖: <dependencies> <!–Spring Boot Web Starter…

    Java 2023年5月19日
    00
  • java加密解密示例分享

    下面是关于“java加密解密示例分享”的完整攻略。 一、背景介绍 在网络安全中,加密与解密算法是非常重要的。Java提供了很多加密与解密算法,如MD5、SHA-1、DES、AES等,本文将从这些加密算法介绍开始,分享Java加密解密的示例。不过,在使用加密解密算法的时候我们需要注意避免一些常见的错误,比如安全性的问题。 二、加密解密过程 加密解密过程可以分为…

    Java 2023年5月23日
    00
  • Java中Properties类的操作实例详解

    Java中Properties类的操作实例详解 Properties类是什么? Properties类是Java中常用的一个类,主要用于处理属性文件。属性文件是一种配置文件,其中包含了键值对,用于保存程序运行时需要动态设置的参数值,例如数据库连接参数、日志输出级别等等。 Properties类的基本用法 Properties类位于java.util包中,可以…

    Java 2023年6月15日
    00
  • Eclipse开发Hibernate应用程序

    Eclipse开发Hibernate应用程序攻略 Hibernate是一种流行的,开源的ORM(对象关系映射)框架,能够映射Java类到数据库表,使操作数据库更方便快捷。那么如何在Eclipse中使用Hibernate进行开发呢?下面是详细的攻略: 步骤一:创建Hibernate项目 打开Eclipse,点击File -> New -> Othe…

    Java 2023年5月20日
    00
  • Java 随机取字符串的工具类

    接下来我将为你讲解如何实现“Java 随机取字符串的工具类”,具体步骤如下: 1. 定义工具类 首先,在Java项目中,你需要定义一个名为StringRandomUtils的工具类,该类的作用是提供随机字符串相关的方法。 public class StringRandomUtils { } 2. 实现随机生成字符串的方法 在定义完工具类之后,你需要实现随机生…

    Java 2023年5月27日
    00
  • Java设计模式之观察者模式(Observer模式)介绍

    Java设计模式之观察者模式(Observer模式)介绍 观察者模式,也叫做发布订阅模式,是一种常用的设计模式。它定义了一种一对多的关系,让多个观察者对象同时监听某一个主题对象,当一个对象发生改变时,所有依赖于它的对象都将得到通知并被自动更新。 观察者模式的结构 观察者模式由四个角色组成:抽象主题角色、具体主题角色、抽象观察者角色和具体观察者角色。 抽象主题…

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