当前位置： 首页 > article >正文

【redis】布隆过滤器的Java实现

article 2025/3/13 4:54:17

在Java中，要实现布隆过滤器（Bloom Filter）的方式有很多种，除了上一节中通过jedis包调用安装了布隆过滤器的redis外，还有以下几种常见的实现方式：

  • 手写布隆过滤器

  • 基于guava包实现

  • 通过redis的bitmaps实现

  • 基于redisson包实现

手写布隆过滤器

手写一个布隆过滤器的源代码：

package com.morris.redis.demo.bloomfilter;

import java.util.BitSet;

/**
 * 手写一个布隆过滤器
 */
public class MyBloomFilter {
    // 位数组的大小
    private static final int DEFAULT_SIZE = 2 << 24;
    // 哈希函数种子
    private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};
    // 位数组
    private final BitSet bits = new BitSet(DEFAULT_SIZE);
    // 哈希函数数组
    private final SimpleHash[] func = new SimpleHash[seeds.length];

    // 初始化哈希函数
    public MyBloomFilter() {
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    // 添加元素
    public void add(String value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    // 判断元素是否存在（可能误判）
    public boolean contains(String value) {
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
            if (!ret) return false;
        }
        return true;
    }

    // 静态内部类，实现简单的哈希函数
    private static class SimpleHash {
        private final int cap;
        private final int seed;

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

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

}

手写一个布隆过滤器的使用：

package com.morris.redis.demo.bloomfilter;

/**
 * 手写一个布隆过滤器的使用
 */
public class MyBloomFilterDemo {

    public static void main(String[] args) {

        MyBloomFilter filter = new MyBloomFilter();
        filter.add("hello");

        System.out.println(filter.contains("hello")); // true
        System.out.println(filter.contains("world")); // 可能为false，也可能为误判的true
    }
}

基于guava包实现

先添加maven依赖：

<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>33.3.1-jre</version>
</dependency>

guava包中布隆过滤器的使用源码如下：

package com.morris.redis.demo.bloomfilter;

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

import java.nio.charset.Charset;

/**
 * guava包中布隆过滤器的使用
 */
public class GuavaBloomFilterDemo {
    
    public static void main(String[] args) {
        // 创建布隆过滤器对象
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), 10000, 0.001);

        bloomFilter.put("10080");
        bloomFilter.put("10081");
        bloomFilter.put("10082");
        bloomFilter.put("10083");
        bloomFilter.put("10084");
        bloomFilter.put("10085");
        bloomFilter.put("10086");

        System.out.println(bloomFilter.mightContain("10086")); // true
        System.out.println(bloomFilter.mightContain("10089")); // false
    }
}

通过redis的bitmaps实现

使用redis的bitmaps实现布隆过滤器源码如下：

package com.morris.redis.demo.bloomfilter;

import com.google.common.hash.HashCode;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.Pipeline;
import redis.clients.jedis.Response;

import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;

/**
 * 使用redis的bitmaps实现布隆过滤器
 */
public class RedisBloomFilter {
    private final Jedis jedis;
    private final String redisKey;
    private final int bitArraySize;
    private final int hashCount;
    private final int[] hashSeeds;

    /**
     * 构造布隆过滤器
     *
     * @param redisHost         Redis主机地址
     * @param redisPort         Redis端口
     * @param redisKey          存储位数组的Redis键
     * @param expectedElements  预期元素数量
     * @param falsePositiveRate 可接受的误判率（0.0到1.0之间）
     */
    public RedisBloomFilter(String redisHost, int redisPort, String redisKey,
                            int expectedElements, double falsePositiveRate) {
        this.jedis = new Jedis(redisHost, redisPort);
        this.redisKey = redisKey;
        this.bitArraySize = calculateOptimalSize(expectedElements, falsePositiveRate);
        this.hashCount = calculateOptimalHashCount(bitArraySize, expectedElements);
        this.hashSeeds = generateHashSeeds(hashCount);
    }

    // 计算最优位数组大小
    private int calculateOptimalSize(int n, double p) {
        return (int) Math.ceil(-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }

    // 计算最优哈希函数数量
    private int calculateOptimalHashCount(int m, int n) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }

    // 生成哈希种子（简单实现，实际可能需要更复杂的种子）
    private int[] generateHashSeeds(int count) {
        int[] seeds = new int[count];
        for (int i = 0; i < count; i++) {
            seeds[i] = 31 * (i + 1); // 使用质数生成种子
        }
        return seeds;
    }

    /**
     * 添加元素到布隆过滤器
     *
     * @param element 要添加的元素
     */
    public void add(String element) {
        byte[] bytes = element.getBytes(StandardCharsets.UTF_8);
        try (Pipeline pipeline = jedis.pipelined()) {
            for (int seed : hashSeeds) {
                long hash = murmurHash(bytes, seed);
                long bitOffset = (hash & Long.MAX_VALUE) % bitArraySize;
                pipeline.setbit(redisKey, bitOffset, true);
            }
            pipeline.sync();
        }
    }

    /**
     * 检查元素是否存在
     *
     * @param element 要检查的元素
     * @return true表示可能存在，false表示一定不存在
     */
    public boolean mightContain(String element) {
        byte[] bytes = element.getBytes(StandardCharsets.UTF_8);
        List<Long> offsets = new ArrayList<>(hashSeeds.length);

        // 计算所有位偏移量
        for (int seed : hashSeeds) {
            long hash = murmurHash(bytes, seed);
            long bitOffset = (hash & Long.MAX_VALUE) % bitArraySize;
            offsets.add(bitOffset);
        }

        // 使用管道批量查询
        try (Pipeline pipeline = jedis.pipelined()) {
            List<Response<Boolean>> responses = new ArrayList<>();
            for (Long offset : offsets) {
                responses.add(pipeline.getbit(redisKey, offset));
            }
            pipeline.sync();

            // 检查所有位是否都为1
            for (Response<Boolean> response : responses) {
                if (!response.get()) {
                    return false;
                }
            }
            return true;
        }
    }

    // 使用MurmurHash3算法计算哈希值
    private long murmurHash(byte[] data, int seed) {
        HashFunction hashFunction = Hashing.murmur3_128(seed);
        HashCode hashCode = hashFunction.hashBytes(data);
        return hashCode.asLong();
    }

    /**
     * 关闭Redis连接
     */
    public void close() {
        jedis.close();
    }

}

使用redis的bitmaps实现布隆过滤器的使用：

package com.morris.redis.demo.bloomfilter;


/**
 * 使用redis的bitmaps实现布隆过滤器 的使用
 */
public class RedisBloomFilterDemo {

    public static void main(String[] args) {
        // 示例用法
        RedisBloomFilter filter = new RedisBloomFilter("localhost", 6379, "myBloomFilter", 1000000, 0.01);

        filter.add("hello");

        System.out.println(filter.mightContain("hello")); // true
        System.out.println(filter.mightContain("world")); // 可能为false，也可能为误判的true
        
        filter.close();
    }
}

基于redisson包实现

先添加maven依赖：

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

Redisson包中布隆过滤器的使用：

package com.morris.redis.demo.bloomfilter;

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

/**
 * redisson包中布隆过滤器的使用
 */
public class RedissonBloomFilterDemo {
    
    public static void main(String[] args) {
        // 配置Redisson客户端
        Config config = new Config();
        config.useSingleServer()
              .setAddress("redis://127.0.0.1:6379");
        
        // 创建Redisson客户端实例
        RedissonClient redisson = Redisson.create(config);
        
        // 获取或创建布隆过滤器
        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("userEmails");
        
        // 初始化布隆过滤器（重要！）
        // expectedInsertions: 预期插入数量
        // falseProbability: 误判率（0.0-1.0）
        bloomFilter.tryInit(1000000L, 0.01);
        
        // 添加元素
        bloomFilter.add("user1@example.com");
        bloomFilter.add("user2@example.com");
        
        // 检查元素是否存在
        System.out.println(bloomFilter.contains("user1@example.com")); // true
        System.out.println(bloomFilter.contains("unknown@test.com"));  // false
        
        // 关闭客户端
        redisson.shutdown();
    }
}

布隆过滤器的配置会在redis中生成一个key：

127.0.0.1:6379> hgetall {userEmails}:config
1) "size"
2) "9585058"
3) "hashIterations"
4) "7"
5) "expectedInsertions"
6) "1000000"
7) "falseProbability"
8) "0.01"

http://www.kler.cn/a/582297.html

相关文章：

  • leetcode日记（93）从中序与后序遍历序列构造二叉树
  • C 语言数据结构（三）：栈和队列
  • 【3D视觉学习笔记1】针孔相机模型与坐标系变换
  • Linux进程管理15 - CFS调度器2 - 数据结构关系
  • c#25/3/11 周二
  • WHAT - 前端性能监控和错误追踪（Sentry 篇）
  • 【A2DP】蓝牙A2DP协议剖析：从架构到规范
  • 2025-03-11 学习记录--C/C++-PTA 习题11-5 指定位置输出字符串
  • 详细介绍c++中的文件处理
  • nginx 代理 redis
  • git子仓库管理的两种方式
  • 从零开发Chrome广告拦截插件：开发、打包到发布全攻略
  • C++ 标准库：string 类、vector/List 容器与文件操作深度剖析
  • Android JNI二维码生成与优化方案
  • C语言_数据结构总结3:带头结点的单链表
  • deepseek R1提供的3d迷宫设计方案
  • 爬虫中一些有用的用法
  • PHP框架加载不上.env文件中的变量
  • Mysql 的 Query Cache为什么被废弃
  • Linux losetup循环设备