Java布隆过滤器案例

wen java案例 2026-08-10 122

本文目录导读：

Java布隆过滤器案例

手动实现布隆过滤器
使用Guava库实现（生产环境推荐）
完整应用示例
高级功能示例
注意事项和使用建议

我来为你提供一个完整的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);
    }
}

这些示例涵盖了：