3. 布隆过滤器深度解析：数据结构、哈希函数、误判率计算、Guava实现与Redisson实现

3.1 布隆过滤器的核心数据结构

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否可能存在于一个集合中。其核心思想是：用多个哈希函数将一个元素映射到一个位数组（Bit Array）中的多个位置，并将这些位置置为1。

下图展示了布隆过滤器的基本结构：一个长度为 m 的位数组，配合 k 个独立的哈希函数。

3.2 哈希函数的选择与要求

布隆过滤器的性能高度依赖于哈希函数的质量。一个优秀的哈希函数应满足以下条件：

3.3 误判率计算与参数推导

误判率（False Positive Rate, FPR）是布隆过滤器最关键的指标。给定位数组长度 m、哈希函数个数 k、已插入元素个数 n，误判率 p 的近似公式为：

p ≈ (1 - e^(-k * n / m))^k

在实际应用中，我们通常根据预期的误判率 p 和元素数量 n 来反推最优参数：

下图展示了误判率与位数组长度、哈希函数个数之间的关系：

3.4 Guava 实现详解

Google Guava 库提供了成熟的 BloomFilter 实现，是 Java 生态中最常用的布隆过滤器方案。

3.4.1 核心 API

// 创建布隆过滤器：预期插入 10000 个元素，期望误判率 1%
BloomFilter<String> bloomFilter = BloomFilter.create(
    Funnels.stringFunnel(Charset.defaultCharset()),
    10000,
    0.01
);

// 插入元素
bloomFilter.put("user:1001");

// 判断元素是否存在
boolean mightContain = bloomFilter.mightContain("user:1001"); // true
boolean notExist = bloomFilter.mightContain("user:9999");    // 大概率 false

3.4.2 参数自动推导

Guava 的 BloomFilter.create() 方法内部会自动计算最优参数：

// Guava 源码中的参数计算逻辑（简化版）
long numBits = optimalNumOfBits(expectedInsertions, fpp);
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);

// 实际实现
static long optimalNumOfBits(long n, double p) {
    return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}

static int optimalNumOfHashFunctions(long n, long m) {
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}

3.5 Redisson 实现详解

Redisson 是基于 Redis 的分布式布隆过滤器实现，适合分布式系统场景。

3.5.1 核心 API

// 获取 Redisson 客户端
Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
RedissonClient redisson = Redisson.create(config);

// 创建布隆过滤器：名称 "myBloom"，预期插入 10000 个元素，期望误判率 1%
RBloomFilter<String> bloomFilter = redisson.getBloomFilter("myBloom");
bloomFilter.tryInit(10000, 0.01);

// 插入元素
bloomFilter.add("user:1001");

// 判断元素是否存在
boolean mightContain = bloomFilter.contains("user:1001"); // true
boolean notExist = bloomFilter.contains("user:9999");    // 大概率 false

// 关闭客户端
redisson.shutdown();

3.5.2 Guava vs Redisson 对比

3.6 布隆过滤器在缓存穿透治理中的应用

布隆过滤器是解决缓存穿透问题的核心手段之一。其典型部署架构如下：