package com.laozhang.bloom;

import java.util.BitSet;
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;

/**
 * 布隆过滤器完整实现
 *
 * 设计决策：
 * 1. 底层用Java BitSet（bit级别存储，内存效率高）
 * 2. 哈希函数用MD5派生（MD5分布均匀，碰撞率低）
 * 3. 构造时根据n和p自动计算最优m和k
 */
public class BloomFilter {

    private final BitSet bitSet;
    private final int bitSize;    // bit数组大小（m）
    private final int hashCount;  // 哈希函数数量（k）
    private long insertCount = 0; // 已插入元素数

    /**
     * @param expectedInsertions 预期插入的元素数量 n
     * @param fpp                期望的误判率（False Positive Probability），如0.001 = 0.1%
     */
    public BloomFilter(long expectedInsertions, double fpp) {
        this.bitSize = optimalNumOfBits(expectedInsertions, fpp);
        this.hashCount = optimalNumOfHashFunctions(expectedInsertions, bitSize);
        this.bitSet = new BitSet(bitSize);

        System.out.printf("BloomFilter初始化：n=%d, p=%.4f, m=%d bits(%.2fMB), k=%d%n",
            expectedInsertions, fpp, bitSize,
            bitSize / 8.0 / 1024 / 1024, hashCount);
    }

    /**
     * 计算最优bit数组大小
     * m = -n * ln(p) / (ln(2))^2
     */
    private static int optimalNumOfBits(long n, double p) {
        if (p == 0) p = Double.MIN_VALUE;
        return (int)(-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }

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

    /**
     * 插入元素
     * 用k个哈希函数，把k个bit位置1
     */
    public void put(String item) {
        long[] hashes = getHashes(item);
        for (int i = 0; i < hashCount; i++) {
            // 每个哈希函数的位置：用两个独立哈希线性组合（Kirsch-Mitzenmacher优化）
            // 只需2次哈希，用 hash1 + i * hash2 模拟k个独立哈希函数
            int pos = (int)((hashes[0] + i * hashes[1]) % bitSize);
            if (pos < 0) pos += bitSize; // 负数修正
            bitSet.set(pos);
        }
        insertCount++;
    }

    /**
     * 查询元素是否可能存在
     * 返回true：可能存在（有误判率p）
     * 返回false：一定不存在（100%准确）
     */
    public boolean mightContain(String item) {
        long[] hashes = getHashes(item);
        for (int i = 0; i < hashCount; i++) {
            int pos = (int)((hashes[0] + i * hashes[1]) % bitSize);
            if (pos < 0) pos += bitSize;
            if (!bitSet.get(pos)) return false; // 有一个0，一定不存在
        }
        return true; // 全是1，可能存在
    }

    /**
     * 用MD5生成两个独立的64位哈希值
     * MD5产生128位输出，前64位作为hash1，后64位作为hash2
     * 分布比Java内置hashCode更均匀
     */
    private long[] getHashes(String item) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            byte[] bytes = md.digest(item.getBytes(StandardCharsets.UTF_8));

            long hash1 = 0, hash2 = 0;
            for (int i = 0; i < 8; i++) {
                hash1 = (hash1 << 8) | (bytes[i] & 0xFF);
                hash2 = (hash2 << 8) | (bytes[i + 8] & 0xFF);
            }
            return new long[]{hash1, hash2};
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 当前实际误判率（插入insertCount个元素后）
     * 实际误判率 = (1 - e^(-k*n/m))^k
     */
    public double getCurrentFPP() {
        double exponent = -((double) hashCount * insertCount) / bitSize;
        return Math.pow(1 - Math.exp(exponent), hashCount);
    }

    public long getInsertCount() { return insertCount; }
    public int getBitSize() { return bitSize; }
    public int getHashCount() { return hashCount; }
}

3.2 实战：防缓存穿透的布隆过滤器

package com.laozhang.bloom;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

/**
 * 布隆过滤器防缓存穿透完整实现
 *
 * 场景：商品ID查询，恶意请求不断查询不存在的ID，打穿缓存直到数据库
 * 解决：启动时把所有有效商品ID加入布隆过滤器，
 *       请求进来先查过滤器，确定不存在的直接返回空，不查缓存和数据库
 *
 * 注意：新增商品时，需要同步更新布隆过滤器（否则新商品会被误判为不存在）
 */
public class CachePenetrationProtection {

    private final BloomFilter bloomFilter;
    // 模拟Redis缓存
    private final Map<Long, String> cache = new ConcurrentHashMap<>();
    // 模拟数据库
    private final Map<Long, String> database = new HashMap<>();

    public CachePenetrationProtection(int expectedProductCount) {
        // 误判率0.01%：万分之一的概率把合法商品误判为不存在（业务可接受）
        this.bloomFilter = new BloomFilter(expectedProductCount, 0.0001);
    }

    /**
     * 初始化：从数据库加载所有商品ID到布隆过滤器
     * 生产环境：可以异步加载，或者用Redis的BF.ADD命令（Redis Stack）
     */
    public void initialize(List<Long> allProductIds) {
        for (Long id : allProductIds) {
            bloomFilter.put(String.valueOf(id));
            database.put(id, "Product-" + id); // 模拟数据库数据
        }
        System.out.println("初始化完成，商品数=" + allProductIds.size() +
            "，布隆过滤器当前误判率=" + String.format("%.6f%%", bloomFilter.getCurrentFPP() * 100));
    }

    /**
     * 查询商品（带布隆过滤器防穿透）
     */
    public String getProduct(long productId) {
        String key = String.valueOf(productId);

        // 第一关：布隆过滤器检查
        // 如果布隆过滤器说"不存在"，直接返回null，不查缓存和数据库
        if (!bloomFilter.mightContain(key)) {
            System.out.println("布隆过滤器拦截：商品" + productId + "一定不存在");
            return null;
        }

        // 第二关：查缓存
        if (cache.containsKey(productId)) {
            return cache.get(productId);
        }

        // 第三关：查数据库（回源）
        String product = database.get(productId);
        if (product != null) {
            cache.put(productId, product); // 写入缓存
        }
        // 如果数据库也没有（极小概率是布隆过滤器误判导致）：
        // 可以选择缓存一个空值（缓存null，设置短过期时间）防止后续请求再次回源
        return product;
    }

    /**
     * 新增商品：同步更新布隆过滤器
     * 注意：布隆过滤器不支持删除，如果有大量商品删除，
     * 需要定期重建布隆过滤器（按业务周期重建，如每天凌晨）
     */
    public void addProduct(long productId, String productName) {
        database.put(productId, productName);
        bloomFilter.put(String.valueOf(productId)); // 加入过滤器
        // 不需要立即更新缓存（下次查询时自然回源）
    }

    public static void main(String[] args) {
        CachePenetrationProtection service = new CachePenetrationProtection(1_000_000);

        // 初始化100万个合法商品
        List<Long> validIds = new ArrayList<>();
        for (long i = 1; i <= 1_000_000; i++) validIds.add(i);
        service.initialize(validIds);

        // 测试合法商品查询
        System.out.println("查询商品1: " + service.getProduct(1));         // 正常返回
        System.out.println("查询商品1000000: " + service.getProduct(1_000_000)); // 正常返回

        // 测试非法商品（攻击者构造的不存在ID）
        long hits = 0;
        for (long id = 1_000_001; id <= 1_100_000; id++) { // 10万个不存在的ID
            if (service.getProduct(id) != null) hits++; // 布隆过滤器未拦截（误判）
        }
        System.out.printf("10万次无效请求被拦截率: %.2f%%，误判了%d次%n",
            100.0 * (100_000 - hits) / 100_000, hits);
        // 误判率约0.01%，约10次误判穿透到数据库（可接受）
    }
}

四、踩坑实录

坑1：布隆过滤器不支持删除，商品下架后仍然"存在"

报错现象：商品下架后，布隆过滤器依然认为该商品存在，请求还是会穿透到数据库（然后返回空），没有被正确拦截。

根本原因：标准布隆过滤器不支持删除操作。把一个bit清0可能影响其他共享该bit的元素，导致漏报。

具体解法：

// 方案1：定期重建布隆过滤器（最简单可靠）
// 每天凌晨从数据库重新加载所有有效ID，重建过滤器
// 适合商品下架是低频操作的场景

// 方案2：使用计数布隆过滤器（Counting Bloom Filter）
// 每个bit改为计数器，插入+1，删除-1，0才表示不存在
// 代价：内存增加4倍（4bit计数器 vs 1bit）
// 库：com.baqend:bloom-filter（Java实现，支持删除）

// 方案3：双层过滤器
// 布隆过滤器：快速过滤明确不存在的
// 缓存黑名单：记录已下架商品ID（Set，数量有限时可用）
// 查询时：先查黑名单，再查布隆过滤器

坑2：初始化时没有加载全量数据，误拦截合法请求

报错现象：布隆过滤器上线后，少量合法商品的查询返回null，用户反馈商品找不到。

根本原因：初始化时只加载了部分数据（比如分批加载，加载失败后提前返回），有一部分有效ID没有进入过滤器。

具体解法：

// 初始化必须全量加载，可以用checksum验证
public void initializeWithVerification(List<Long> expectedIds) {
    long loadedCount = 0;
    for (Long id : expectedIds) {
        bloomFilter.put(String.valueOf(id));
        loadedCount++;
    }

    // 验证加载完整性
    if (loadedCount != expectedIds.size()) {
        throw new IllegalStateException(
            "布隆过滤器初始化不完整！预期加载" + expectedIds.size() +
            "条，实际加载" + loadedCount + "条");
    }

    // 二次验证：随机抽样10%的ID，确认都在过滤器中
    java.util.Random rnd = new java.util.Random();
    long sampleCount = Math.min(1000, expectedIds.size());
    for (int i = 0; i < sampleCount; i++) {
        Long id = expectedIds.get(rnd.nextInt(expectedIds.size()));
        if (!bloomFilter.mightContain(String.valueOf(id))) {
            throw new IllegalStateException("布隆过滤器验证失败：ID " + id + " 未被正确加载");
        }
    }
}

坑3：并发写入时线程不安全，bit数组状态损坏

报错现象：高并发初始化时，布隆过滤器的误判率远高于配置值，说明部分bit没有被正确置1。

根本原因：Java BitSet不是线程安全的，并发set(pos)操作可能互相覆盖。

具体解法：

// 方案1：初始化时单线程加载（最简单）
// 方案2：用synchronized包装put操作（粗粒度锁）
// 方案3：直接用Guava的BloomFilter（内部用AtomicLongArray，线程安全）

// Guava BloomFilter使用示例（生产环境推荐）
// implementation 'com.google.guava:guava:32.1.3-jre'
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.StandardCharsets;

BloomFilter<String> guavaFilter = BloomFilter.create(
    Funnels.stringFunnel(StandardCharsets.UTF_8),
    1_000_000,  // 预期插入量
    0.001       // 误判率0.1%
);
// Guava BloomFilter是线程安全的，可以直接用于并发场景
guavaFilter.put("url1");
boolean exists = guavaFilter.mightContain("url1"); // true

五、总结与延伸

布隆过滤器的核心权衡：用极少的内存（约1.9GB存10亿URL）换取有限的误判率（可配置）。 没有False Negative（漏报），只有False Positive（误判）。适合"宁可误拦，不能漏报"的场景：爬虫去重、缓存穿透防护、垃圾邮件过滤。
参数选择公式是固定的：m = -n*ln(p)/(ln2)²，k = (m/n)*ln2。 实践中不需要手动推导，Guava的BloomFilter会根据n和p自动计算。理解公式的意义：误判率p越低，需要的bit越多，哈希函数数量越多（计算开销越大）。
布隆过滤器最大的工程挑战是"不支持删除"和"需要预加载全量数据"。 前者可以用计数布隆过滤器或定期重建解决，后者需要在系统设计层面考虑（启动预热、全量加载保障）。Redis Stack的BF模块是生产环境中更成熟的选择。