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

在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")); // trueSystem.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")); // trueSystem.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();// 检查所有位是否都为1for (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")); // trueSystem.out.println(filter.mightContain("world")); // 可能为false，也可能为误判的truefilter.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("[e-mail]");bloomFilter.add("[e-mail]");// 检查元素是否存在System.out.println(bloomFilter.contains("[e-mail]")); // trueSystem.out.println(bloomFilter.contains("[e-mail]"));  // 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"