本文目录导读：
我来为你提供一个完整的Java布隆过滤器案例,包括手动实现和使用Google Guava库两种方式。
手动实现布隆过滤器
基本实现
import java.util.BitSet;
import java.util.Random;
/**
* 手动实现的布隆过滤器
*/
public class SimpleBloomFilter {
// 位数组大小
private final int bitSize;
// 哈希函数数量
private final int hashFunctionCount;
// 位数组
private final BitSet bitSet;
// 随机数种子
private final Random random = new Random();
/**
* 构造函数
* @param expectedElements 预期元素数量
* @param falsePositiveRate 误判率（0-1之间）
*/
public SimpleBloomFilter(int expectedElements, double falsePositiveRate) {
// 计算最优位数组大小: m = -(n * ln(p)) / (ln(2)^2)
this.bitSize = (int) Math.ceil(-(expectedElements * Math.log(falsePositiveRate))
/ (Math.pow(Math.log(2), 2)));
// 计算最优哈希函数数量: k = m/n * ln(2)
this.hashFunctionCount = (int) Math.ceil((bitSize / (double) expectedElements)
* Math.log(2));
this.bitSet = new BitSet(bitSize);
System.out.printf("位数组大小: %d, 哈希函数数量: %d%n", bitSize, hashFunctionCount);
}
/**
* 计算哈希值（使用简单哈希函数）
*/
private int[] hash(String value) {
int[] hashes = new int[hashFunctionCount];
for (int i = 0; i < hashFunctionCount; i++) {
int seed = i * 31 + 17;
int hash = value.hashCode() + seed * seed;
hash = Math.abs(hash * 2654435761L % Integer.MAX_VALUE);
hashes[i] = hash % bitSize;
}
return hashes;
}
/**
* 添加元素
*/
public void add(String value) {
int[] hashes = hash(value);
for (int hash : hashes) {
bitSet.set(hash, true);
}
System.out.println("添加元素: " + value);
}
/**
* 检查元素是否存在（可能存在误判）
*/
public boolean contains(String value) {
int[] hashes = hash(value);
for (int hash : hashes) {
if (!bitSet.get(hash)) {
return false; // 一定不存在
}
}
return true; // 可能存在
}
/**
* 获取当前占用率
*/
public double getOccupancy() {
return (double) bitSet.cardinality() / bitSize;
}
}
改进版本（支持删除操作）
import java.util.BitSet;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;
/**
* 可计数的布隆过滤器（支持删除操作）
*/
public class CountingBloomFilter {
private final int bitSize;
private final int hashFunctionCount;
private final int[] counter; // 使用计数器替代BitSet
private final Random random = new Random();
public CountingBloomFilter(int expectedElements, double falsePositiveRate) {
this.bitSize = (int) Math.ceil(-(expectedElements * Math.log(falsePositiveRate))
/ (Math.pow(Math.log(2), 2)));
this.hashFunctionCount = (int) Math.ceil((bitSize / (double) expectedElements)
* Math.log(2));
this.counter = new int[bitSize];
}
private int[] hash(String value) {
int[] hashes = new int[hashFunctionCount];
for (int i = 0; i < hashFunctionCount; i++) {
int seed = i * 37 + 11;
int hash = Math.abs((value.hashCode() ^ (seed * 2654435761L)) % bitSize);
hashes[i] = hash;
}
return hashes;
}
public void add(String value) {
int[] hashes = hash(value);
for (int hash : hashes) {
counter[hash]++;
}
}
public void remove(String value) {
if (!contains(value)) {
throw new IllegalArgumentException("元素不存在");
}
int[] hashes = hash(value);
for (int hash : hashes) {
if (counter[hash] > 0) {
counter[hash]--;
}
}
}
public boolean contains(String value) {
int[] hashes = hash(value);
for (int hash : hashes) {
if (counter[hash] == 0) {
return false;
}
}
return true;
}
}
使用Guava库实现（生产环境推荐）
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.Charset;
import java.util.Random;
/**
* 基于Guava的布隆过滤器
*/
public class GuavaBloomFilterExample {
public static void main(String[] args) {
// 创建布隆过滤器
// 参数1: 预期插入的元素数量
// 参数2: 误判率（越小越精确，但占用空间越大）
BloomFilter<String> bloomFilter = BloomFilter.create(
Funnels.stringFunnel(Charset.defaultCharset()),
10000, // 预期元素数量
0.01 // 误判率 1%
);
// 添加元素
System.out.println("=== 添加元素 ===");
for (int i = 0; i < 5000; i++) {
bloomFilter.put("user_" + i);
}
System.out.println("已添加5000个元素");
// 检查元素
System.out.println("\n=== 检查已存在的元素 ===");
int truePositive = 0;
int totalChecks = 1000;
for (int i = 0; i < totalChecks; i++) {
if (bloomFilter.mightContain("user_" + i)) {
truePositive++;
}
}
System.out.printf("已存在元素检测到: %d/%d (%.2f%%)%n",
truePositive, totalChecks, (truePositive * 100.0 / totalChecks));
// 检查不存在的元素（误判测试）
System.out.println("\n=== 检查不存在的元素（误判测试） ===");
int falsePositive = 0;
int nonExistentChecks = 5000;
for (int i = 5000; i < 10000; i++) {
if (bloomFilter.mightContain("user_" + i)) {
falsePositive++;
}
}
double falsePositiveRate = (falsePositive * 100.0 / nonExistentChecks);
System.out.printf("误判率: %.2f%% (期望值: 1%%)%n", falsePositiveRate);
// 性能测试
System.out.println("\n=== 性能测试 ===");
Random random = new Random();
long startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
bloomFilter.mightContain("random_key_" + random.nextInt(20000));
}
long endTime = System.nanoTime();
long duration = (endTime - startTime) / 1_000_000; // 毫秒
System.out.printf("10000次查询耗时: %d ms%n", duration);
}
}
完整应用示例
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.Charset;
import java.util.ArrayList;
import java.util.List;
import java.util.UUID;
/**
* 布隆过滤器在缓存穿透场景的应用
*/
public class CachePenetrationSolution {
// 模拟数据库
private static class Database {
private final List<String> data = new ArrayList<>();
public Database() {
// 模拟数据库中的用户
for (int i = 0; i < 10000; i++) {
data.add("user_" + i);
}
}
public String query(String userId) {
// 模拟数据库查询延迟
try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
return data.contains(userId) ? userId : null;
}
}
// 缓存服务
private static class CacheService {
private final BloomFilter<String> bloomFilter;
private final Database database;
private int cacheHitCount = 0;
private int cacheMissCount = 0;
public CacheService() {
// 创建布隆过滤器：预期10000个元素，误判率0.1%
bloomFilter = BloomFilter.create(
Funnels.stringFunnel(Charset.defaultCharset()),
10000,
0.001
);
database = new Database();
// 预热布隆过滤器
for (int i = 0; i < 10000; i++) {
bloomFilter.put("user_" + i);
}
}
/**
* 查询用户（带布隆过滤器优化）
*/
public String getUser(String userId) {
// 先检查布隆过滤器
if (!bloomFilter.mightContain(userId)) {
cacheMissCount++;
return null; // 一定不存在，直接返回
}
// 可能存在，查询数据库
String result = database.query(userId);
if (result != null) {
cacheHitCount++;
} else {
cacheMissCount++;
}
return result;
}
/**
* 添加新用户
*/
public void addUser(String userId) {
bloomFilter.put(userId);
System.out.println("添加新用户到布隆过滤器: " + userId);
}
public void printStats() {
System.out.printf("缓存命中: %d, 未命中: %d, 命中率: %.2f%%%n",
cacheHitCount, cacheMissCount,
(cacheHitCount * 100.0 / (cacheHitCount + cacheMissCount)));
}
}
public static void main(String[] args) {
CacheService cacheService = new CacheService();
System.out.println("=== 测试已存在的用户 ===");
long startTime = System.nanoTime();
for (int i = 0; i < 100; i++) {
String userId = "user_" + (i * 10); // 已存在的用户
String result = cacheService.getUser(userId);
System.out.printf("查询 %s: %s%n", userId,
result != null ? "找到" : "未找到");
}
System.out.println("\n=== 测试不存在的用户（恶意请求） ===");
startTime = System.nanoTime();
int maliciousRequests = 0;
for (int i = 0; i < 100; i++) {
String userId = "nonexistent_user_" + UUID.randomUUID();
String result = cacheService.getUser(userId);
if (result == null) {
maliciousRequests++;
}
}
System.out.println("恶意请求（不存在的用户）直接拦截: " + maliciousRequests + "/100");
cacheService.printStats();
}
}
高级功能示例
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.Charset;
import java.util.HashMap;
import java.util.Map;
/**
* 布隆过滤器+LRU缓存结合
*/
public class BloomFilterWithLRU extends LinkedHashMap<String, String> {
private final int maxSize;
private final BloomFilter<String> bloomFilter;
public BloomFilterWithLRU(int maxSize, double falsePositiveRate) {
super(maxSize, 0.75f, true);
this.maxSize = maxSize;
this.bloomFilter = BloomFilter.create(
Funnels.stringFunnel(Charset.defaultCharset()),
maxSize,
falsePositiveRate
);
}
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
if (size() > maxSize) {
bloomFilter.put(eldest.getKey());
return true;
}
return false;
}
@Override
public String put(String key, String value) {
bloomFilter.put(key);
return super.put(key, value);
}
@Override
public String get(Object key) {
String value = super.get(key);
if (value == null && bloomFilter.mightContain((String) key)) {
// 可能是缓存淘汰了，需要从数据库加载
// 这里模拟数据库加载
value = loadFromDatabase((String) key);
if (value != null) {
put((String) key, value);
}
}
return value;
}
private String loadFromDatabase(String key) {
// 模拟数据库查询
if (key.startsWith("user_")) {
return "数据库数据 for " + key;
}
return null;
}
public static void main(String[] args) {
BloomFilterWithLRU cache = new BloomFilterWithLRU(100, 0.01);
// 添加缓存
for (int i = 0; i < 150; i++) {
cache.put("user_" + i, "用户数据" + i);
}
// 查询缓存
System.out.println("缓存大小: " + cache.size());
System.out.println("查询 user_0: " + cache.get("user_0"));
System.out.println("查询 user_145: " + cache.get("user_145"));
System.out.println("查询 user_200 （不存在）: " + cache.get("user_200"));
}
}
注意事项和使用建议
/**
* 布隆过滤器使用的注意事项
*/
public class BloomFilterTips {
public static void main(String[] args) {
// 1. 合理设置参数
int expectedElements = 1000000; // 预期插入数量
double falsePositiveRate = 0.01; // 可接受的误判率
BloomFilter<String> filter = BloomFilter.create(
Funnels.stringFunnel(Charset.defaultCharset()),
expectedElements,
falsePositiveRate
);
// 2. 添加元素
filter.put("test");
// 3. 检查元素（不能删除元素，除非使用CountingBloomFilter）
boolean exists = filter.mightContain("test");
// 4. 返回false一定是不存在，返回true只是可能存在
// 5. 误判率测试
System.out.println("误判率设置: " + falsePositiveRate);
System.out.println("实际误判率会略低于期望值");
// 6. 内存占用估算
double bits = -(double) expectedElements * Math.log(falsePositiveRate)
/ (Math.pow(Math.log(2), 2));
System.out.printf("预计内存占用: %.2f MB%n", bits / 8 / 1024 / 1024);
}
}
这些示例涵盖了：
- 手动实现：理解布隆过滤器原理
- Guava实现：生产环境推荐方案
- 缓存穿透场景：最典型的应用场景
- 缓存结合：与LRU缓存配合使用
- 注意事项：使用最佳实践
布隆过滤器特别适合以下场景：
- 缓存穿透防护
- 爬虫URL去重
- 垃圾邮件过滤
- 推荐系统去重
- 数据库查询优化
