布隆过滤器四种实现(Java,Guava,hutool,Redisson)

发布时间:2024年01月15日

1.背景

为预防大量黑客故意发起非法的时间查询请求,造成缓存击穿,建议采用布隆过滤器的方法解决。布隆过滤器通过一个很长的二进制向量和一系列随机映射函数(哈希函数)来记录与识别某个数据是否在一个集合中。如果数据不在集合中,能被识别出来,不需要到数据库中进行查询,所以能将数据库查询返回值为空的查询过滤掉。
缓存穿透: 缓存穿透是查询一个根本不存在的数据,由于缓存是不命中时需要从数据库查询,这将导致这个不存在的数据每次请求都要到数据库去查询,进而给数据库带来压力。

2.布隆过滤器介绍

1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列的随机映射函数(哈希函数)两部分组成的数据结构。
用途: 用于检索一个元素是否在一个集合中。
优点:
时间复杂度低,增加及查询元素的时间复杂度都是O(k),k为Hash函数的个数;
占用存储空间小,布隆过滤器相对于其他数据结构(如Set、Map)非常节省空间。
缺点:
存在误判,只能证明一个元素一定不存在或者可能存在,返回结果是概率性的,但是可以通过调整参数来降低误判比例;
删除困难,一个元素映射到bit数组上的k个位置为1,删除的时候不能简单的直接置为0,可能会影响到其他元素的判断。

3.原理

当一个元素加入布隆过滤器中的时候,会进行如下操作:

使用布隆过滤器中的哈希函数对元素进行计算,得到哈希值(有几个哈希函数得到几个哈希值)。
根据得到的哈希值,在位数组中把对应下标的值置为1。
当我们需要判断一个元素是否位于布隆过滤器的时候,会进行如下操作:

对给定元素再次进行相同的哈希计算;
得到值之后判断位数组中的每个元素是否都为1,如果值都为1,那么说明这个值在布隆过滤器中,如果存在一个值不为1,说明该元素不在布隆过滤器中。
举个例子:
在这里插入图片描述
如图所示,当字符串存储要加入到布隆过滤器中时,该字符串首先由多个哈希函数生成不同的哈希值,然后将对应的位数组的下标设置为1(当位数组初始化时,所有位置均为 0)。当第二次存储相同字符串时,因为先前的对应位置已设置为 1,所以很容易知道此值已经存在(去重非常方便)。
如果我们需要判断某个字符串是否在布隆过滤器中时,只需要对给定字符串再次进行相同的哈希计算,得到值之后判断位数组中的某个元素是否都为1,如果值都为1,那么说明这个值在布隆过滤器中,如果存在一个值不为1,说明该元素不在布隆过滤器中。
不同的字符串可能哈希出来的位置相同,这种情况我们可以适当增加位数组大小或者调整我们的哈希函数。

综上:布隆过滤器说某个元素存在,小概率会误判。布隆过滤器说某个元素不存在,那么这个元素一定不在。

4.使用场景

4.1判断给定数据是否存在:
比如判断一个数字是否在于包含大量数字的数字集中(数字集很大,5亿以上)、防止缓存穿透(判断请求的数据是否有效避免直接绕过缓存请求数据库)、邮箱的垃圾邮件过滤、黑名单功能等。
4.2去重:
爬给定网址的时候对已经爬取过的URL去重。

5.代码实现

5.1Java实现
package com.fandf.test.redis;

import java.util.BitSet;

/**
 * java布隆过滤器
 */
public class MyBloomFilter {

    /**
     * 位数组大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;

    /**
     * 通过这个数组创建多个Hash函数
     */
    private static final int[] SEEDS = new int[]{4, 8, 16, 32, 64, 128, 256};

    /**
     * 初始化位数组,数组中的元素只能是 0 或者 1
     */
    private final BitSet bits = new BitSet(DEFAULT_SIZE);

    /**
     * Hash函数数组
     */
    private final MyHash[] myHashes = new MyHash[SEEDS.length];

    /**
     * 初始化多个包含 Hash 函数的类数组,每个类中的 Hash 函数都不一样
     */
    public MyBloomFilter() {
        // 初始化多个不同的 Hash 函数
        for (int i = 0; i < SEEDS.length; i++) {
            myHashes[i] = new MyHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    /**
     * 添加元素到位数组
     */
    public void add(Object value) {
        for (MyHash myHash : myHashes) {
            bits.set(myHash.hash(value), true);
        }
    }

    /**
     * 判断指定元素是否存在于位数组
     */
    public boolean contains(Object value) {
        boolean result = true;
        for (MyHash myHash : myHashes) {
            result = result && bits.get(myHash.hash(value));
        }
        return result;
    }

    /**
     * 自定义 Hash 函数
     */
    private class MyHash {
        private int cap;
        private int seed;

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

        /**
         * 计算 Hash 值
         */
        int hash(Object obj) {
            return (obj == null) ? 0 : Math.abs(seed * (cap - 1) & (obj.hashCode() ^ (obj.hashCode() >>> 16)));
        }
    }

    public static void main(String[] args) {
        String str = "好好学技术";
        MyBloomFilter myBloomFilter = new MyBloomFilter();
        System.out.println("str是否存在:" + myBloomFilter.contains(str));
        myBloomFilter.add(str);
        System.out.println("str是否存在:" + myBloomFilter.contains(str));
    }
}
5.2Guava实现

依赖:

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

代码:

package com.fandf.test.redis;

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

/**
 * Guava
 */
public class GuavaBloomFilter {

    public static void main(String[] args) {
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01);
        bloomFilter.put("好好学技术");
        System.out.println(bloomFilter.mightContain("不好好学技术"));
        System.out.println(bloomFilter.mightContain("好好学技术"));
    }
}
5.3hutool实现

依赖:

<dependency>
    <groupId>cn.hutool</groupId>
    <artifactId>hutool-all</artifactId>
    <version>5.8.3</version>
</dependency>

代码:

package com.fandf.test.redis;

import cn.hutool.bloomfilter.BitMapBloomFilter;
import cn.hutool.bloomfilter.BloomFilterUtil;

/**
 * hutool
 */
public class HutoolBloomFilter {
    public static void main(String[] args) {
        BitMapBloomFilter bloomFilter = BloomFilterUtil.createBitMap(1000);
        bloomFilter.add("好好学技术");
        System.out.println(bloomFilter.contains("不好好学技术"));
        System.out.println(bloomFilter.contains("好好学技术"));
    }
}
5.4Redisson实现

依赖:

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.20.0</version>
</dependency>

代码:

package com.fandf.test.redis;

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

/**
 * Redisson 实现布隆过滤器
 */
public class RedissonBloomFilter {

    public static void main(String[] args) {
        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");
        //构造Redisson
        RedissonClient redisson = Redisson.create(config);

        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("name");
        //初始化布隆过滤器:预计元素为100000000L,误差率为1%
        bloomFilter.tryInit(100000000L,0.01);
        bloomFilter.add("好好学技术");

        System.out.println(bloomFilter.contains("不好好学技术"));
        System.out.println(bloomFilter.contains("好好学技术"));
    }
}
文章来源:https://blog.csdn.net/o0way0o/article/details/135589867
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。