布隆过滤器（Bloom Filter）由 Burton Howard Bloom 于 1970 年提出，是一种空间效率极高的概率型数据结构。它可以在常数时间内回答”某个元素是否可能在集合中”，且空间占用远低于哈希表。代价是存在一定的假阳性（False Positive）概率——即可能把不在集合中的元素误判为存在，但绝不会把存在的元素误判为不存在。
本文将从原理出发，用 Java 完整实现一个可配置的布隆过滤器，分析其数学基础，并给出在 URL 去重与缓存穿透防护中的实战示例。
一、核心原理
布隆过滤器的底层是一个长度为 (m) 的位数组（Bit Array），初始时所有位均为 0。它使用 (k) 个独立的哈希函数，每个函数将元素映射到位数组的一个位置上。
插入操作
对元素 (x) 执行插入时，分别用 (k) 个哈希函数计算哈希值：
[h_1(x), h_2(x), \dots, h_k(x)]
将位数组中对应位置全部置为 1：
[\text{bit}[h_i(x) \bmod m] = 1, \quad i = 1, 2, \dots, k]
查询操作
查询元素 (y) 时，同样计算 (k) 个哈希值。如果所有对应位都为 1，则返回”可能存在“；如果有任何一位为 0，则返回”一定不存在“。
为什么不会漏报？
若元素曾经被插入，其 (k) 个位必然被置为 1。因此查询时所有位一定为 1，不会出现假阴性（False Negative）。
假阳性从何而来？
即使 (y) 从未被插入，它的 (k) 个哈希位置也可能因其他元素的插入而恰好全部为 1。这就是假阳性的来源。
二、数学分析：最优参数推导
假设位数组长度为 (m)，哈希函数个数为 (k)，已插入元素个数为 (n)。
某一位在插入一个元素后仍为 0 的概率：
[1 – \frac{1}{m}]
经过 (n) 个元素、(k) 次哈希后，某一位仍为 0 的概率：
[\left(1 – \frac{1}{m}\right)^{kn} \approx e^{-kn/m}]
因此某一位为 1 的概率：
[p = 1 – e^{-kn/m}]
假阳性率（所有 (k) 个位都为 1 的概率）：
[\epsilon = p^k = \left(1 – e^{-kn/m}\right)^k]
最优哈希函数个数
对固定的 (m, n)，求使 (\epsilon) 最小的 (k)。令 (p = 1/2) 时取极值，可得：
[k = \frac{m}{n} \ln 2]
位数组大小与假阳性率的关系
将最优 (k) 代回，得到在给定 (n) 和期望假阳性率 (\epsilon) 时，所需位数组大小：
[m = -\frac{n \ln \epsilon}{(\ln 2)^2}]
例如：要存储 (n = 100) 万元素，假阳性率控制在 1%：
[m = -\frac{10^6 \times \ln(0.01)}{(\ln 2)^2} \approx 9.6 \times 10^6 \text{ bits} \approx 1.2 \text{ MB}]
[k = \frac{m}{n} \ln 2 \approx 6.6 \rightarrow \text{取 } k = 7]
相比存储 100 万个字符串（假设平均 20 字节），哈希表至少需要 20 MB，布隆过滤器仅需 1.2 MB，空间节省约 16 倍。
三、Java 实现
下面给出完整的布隆过滤器实现，包含 MurmurHash 风格的多个哈希函数、位数组封装、动态参数计算。
import java.nio.charset.StandardCharsets;
import java.util.BitSet;
/**
* 布隆过滤器实现
* 支持自定义预期元素数量和假阳性率，自动计算最优位数组大小和哈希函数个数
*/
public class BloomFilter<T> {
/** 位数组 */
private final BitSet bitSet;
/** 位数组大小 */
private final int bitSize;
/** 哈希函数个数 */
private final int hashFunctions;
/** 预期插入元素数量 */
private final int expectedInsertions;
/** 假阳性率 */
private final double falsePositiveProbability;
/** 实际插入元素计数 */
private int insertedCount = 0;
/**
* 构造布隆过滤器
*
* @param expectedInsertions 预期插入元素数量
* @param falsePositiveProbability 可接受的假阳性率（如 0.01 表示 1%）
*/
public BloomFilter(int expectedInsertions, double falsePositiveProbability) {
if (expectedInsertions <= 0) {
throw new IllegalArgumentException("预期插入数量必须大于0");
}
if (falsePositiveProbability <= 0 || falsePositiveProbability >= 1) {
throw new IllegalArgumentException("假阳性率必须在 (0, 1) 之间");
}
this.expectedInsertions = expectedInsertions;
this.falsePositiveProbability = falsePositiveProbability;
// 根据公式计算最优位数组大小：m = -n * ln(p) / (ln2)^2
this.bitSize = optimalBitSize(expectedInsertions, falsePositiveProbability);
// 根据公式计算最优哈希函数个数：k = m/n * ln2
this.hashFunctions = optimalHashFunctionCount(expectedInsertions, bitSize);
this.bitSet = new BitSet(bitSize);
}
/**
* 计算最优位数组大小
*/
private static int optimalBitSize(int n, double p) {
return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
/**
* 计算最优哈希函数个数
*/
private static int optimalHashFunctionCount(int n, int m) {
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
/**
* 将元素添加到布隆过滤器
*
* @param element 待添加元素
*/
public void put(T element) {
byte[] bytes = element.toString().getBytes(StandardCharsets.UTF_8);
long[] hashes = murmurHash128(bytes);
long hash1 = hashes[0];
long hash2 = hashes[1];
// 使用双重哈希模拟 k 个独立哈希函数：
// g_i(x) = hash1 + i * hash2 (mod bitSize)
for (int i = 0; i < hashFunctions; i++) {
int combinedHash = (int) (Math.abs(hash1 + (long) i * hash2) % bitSize);
bitSet.set(combinedHash);
}
insertedCount++;
}
/**
* 判断元素是否可能在集合中
*
* @param element 待查询元素
* @return true 表示可能存在，false 表示一定不存在
*/
public boolean mightContain(T element) {
byte[] bytes = element.toString().getBytes(StandardCharsets.UTF_8);
long[] hashes = murmurHash128(bytes);
long hash1 = hashes[0];
long hash2 = hashes[1];
for (int i = 0; i < hashFunctions; i++) {
int combinedHash = (int) (Math.abs(hash1 + (long) i * hash2) % bitSize);
if (!bitSet.get(combinedHash)) {
return false; // 有一位为0，说明一定不存在
}
}
return true; // 所有位都为1，可能存在（存在假阳性概率）
}
/**
* 计算当前假阳性率的理论值
* 公式：(1 - e^(-kn/m))^k
*/
public double currentFalsePositiveProbability() {
if (insertedCount == 0) {
return 0.0;
}
double p = Math.pow(1 - Math.exp(-(double) hashFunctions * insertedCount / bitSize), hashFunctions);
return p;
}
/**
* 获取位数组使用率（已被置为1的位所占比例）
*/
public double bitUsageRate() {
return (double) bitSet.cardinality() / bitSize;
}
/**
* 清空过滤器
*/
public void clear() {
bitSet.clear();
insertedCount = 0;
}
/**
* 返回当前已插入元素数量
*/
public int size() {
return insertedCount;
}
/**
* 返回过滤器配置信息
*/
@Override
public String toString() {
return String.format(
"BloomFilter{bitSize=%d, hashFunctions=%d, inserted=%d, expected=%d, targetFpp=%.4f, currentFpp=%.6f}",
bitSize, hashFunctions, insertedCount, expectedInsertions,
falsePositiveProbability, currentFalsePositiveProbability()
);
}
/**
* MurmurHash3 128位实现
* 返回两个64位哈希值，作为双重哈希的基础
*
* @param data 输入字节数组
* @return long[2]，分别为 hash1 和 hash2
*/
private static long[] murmurHash128(byte[] data) {
final long c1 = 0x87c37b91114253d5L;
final long c2 = 0x4cf5ad432745937fL;
final int length = data.length;
final long seed = 0;
long h1 = seed;
long h2 = seed;
// 按16字节（128位）分块处理
for (int i = 0; i < length / 16; i++) {
int idx = i * 16;
long k1 = getLongLE(data, idx);
long k2 = getLongLE(data, idx + 8);
k1 *= c1;
k1 = Long.rotateLeft(k1, 31);
k1 *= c2;
h1 ^= k1;
h1 = Long.rotateLeft(h1, 27);
h1 += h2;
h1 = h1 * 5 + 0x52dce729;
k2 *= c2;
k2 = Long.rotateLeft(k2, 33);
k2 *= c1;
h2 ^= k2;
h2 = Long.rotateLeft(h2, 31);
h2 += h1;
h2 = h2 * 5 + 0x38495ab5;
}
// 处理剩余字节
long k1 = 0;
long k2 = 0;
int remainder = length & 15;
switch (remainder) {
case 15: k2 ^= ((long) data[length - 1] & 0xff) << 48;
case 14: k2 ^= ((long) data[length - 2] & 0xff) << 40;
case 13: k2 ^= ((long) data[length - 3] & 0xff) << 32;
case 12: k2 ^= ((long) data[length - 4] & 0xff) << 24;
case 11: k2 ^= ((long) data[length - 5] & 0xff) << 16;
case 10: k2 ^= ((long) data[length - 6] & 0xff) << 8;
case 9: k2 ^= ((long) data[length - 7] & 0xff);
k2 *= c2;
k2 = Long.rotateLeft(k2, 33);
k2 *= c1;
h2 ^= k2;
case 8: k1 ^= ((long) data[length - 8] & 0xff) << 56;
case 7: k1 ^= ((long) data[length - 9] & 0xff) << 48;
case 6: k1 ^= ((long) data[length - 10] & 0xff) << 40;
case 5: k1 ^= ((long) data[length - 11] & 0xff) << 32;
case 4: k1 ^= ((long) data[length - 12] & 0xff) << 24;
case 3: k1 ^= ((long) data[length - 13] & 0xff) << 16;
case 2: k1 ^= ((long) data[length - 14] & 0xff) << 8;
case 1: k1 ^= ((long) data[length - 15] & 0xff);
k1 *= c1;
k1 = Long.rotateLeft(k1, 31);
k1 *= c2;
h1 ^= k1;
}
// 最终化简
h1 ^= length;
h2 ^= length;
h1 += h2;
h2 += h1;
h1 = fmix64(h1);
h2 = fmix64(h2);
h1 += h2;
h2 += h1;
return new long[]{h1, h2};
}
private static long getLongLE(byte[] data, int index) {
return ((long) data[index] & 0xff)
| (((long) data[index + 1] & 0xff) << 8)
| (((long) data[index + 2] & 0xff) << 16)
| (((long) data[index + 3] & 0xff) << 24)
| (((long) data[index + 4] & 0xff) << 32)
| (((long) data[index + 5] & 0xff) << 40)
| (((long) data[index + 6] & 0xff) << 48)
| (((long) data[index + 7] & 0xff) << 56);
}
private static long fmix64(long k) {
k ^= k >>> 33;
k *= 0xff51afd7ed558ccdL;
k ^= k >>> 33;
k *= 0xc4ceb9fe1a85ec53L;
k ^= k >>> 33;
return k;
}
}
四、实战验证
下面通过两个实验验证布隆过滤器的特性：一是基础功能测试，二是大规模数据下的假阳性率统计。
import java.util.HashSet;
import java.util.Set;
import java.util.UUID;
/**
* 布隆过滤器功能测试与假阳性率统计
*/
public class BloomFilterDemo {
public static void main(String[] args) {
basicTest();
largeScaleTest();
cachePenetrationDemo();
}
/**
* 基础功能测试
*/
private static void basicTest() {
System.out.println("=== 基础功能测试 ===");
BloomFilter<String> filter = new BloomFilter<>(1000, 0.01);
String[] urls = {
"https://blog.keli.site/post-1",
"https://blog.keli.site/post-2",
"https://blog.keli.site/post-3"
};
for (String url : urls) {
filter.put(url);
System.out.println("插入: " + url);
}
System.out.println("查询 'post-1': " + filter.mightContain("https://blog.keli.site/post-1"));
System.out.println("查询 'post-2': " + filter.mightContain("https://blog.keli.site/post-2"));
System.out.println("查询 'post-999(未插入)': "
+ filter.mightContain("https://blog.keli.site/post-999"));
System.out.println(filter.toString());
System.out.println();
}
/**
* 大规模数据测试：统计实际假阳性率
*/
private static void largeScaleTest() {
System.out.println("=== 大规模假阳性率测试 ===");
int totalElements = 100_000;
double targetFpp = 0.01;
BloomFilter<String> filter = new BloomFilter<>(totalElements, targetFpp);
Set<String> actualSet = new HashSet<>();
// 插入 10 万个随机 UUID
for (int i = 0; i < totalElements; i++) {
String uuid = UUID.randomUUID().toString();
filter.put(uuid);
actualSet.add(uuid);
}
// 用 10 万个全新的 UUID 测试假阳性
int falsePositives = 0;
int testCount = 100_000;
for (int i = 0; i < testCount; i++) {
String uuid = UUID.randomUUID().toString();
// 确保测试用的 UUID 不在实际集合中（UUID 冲突概率极低）
if (!actualSet.contains(uuid) && filter.mightContain(uuid)) {
falsePositives++;
}
}
double actualFpp = (double) falsePositives / testCount;
System.out.printf("插入元素: %,d%n", totalElements);
System.out.printf("测试元素: %,d%n", testCount);
System.out.printf("假阳性次数: %,d%n", falsePositives);
System.out.printf("目标假阳性率: %.4f%%%n", targetFpp * 100);
System.out.printf("实际假阳性率: %.4f%%%n", actualFpp * 100);
System.out.printf("位数组使用率: %.2f%%%n", filter.bitUsageRate() * 100);
System.out.println(filter.toString());
System.out.println();
}
/**
* 缓存穿透防护场景演示
*/
private static void cachePenetrationDemo() {
System.out.println("=== 缓存穿透防护场景 ===");
System.out.println("场景：查询数据库前，先用布隆过滤器判断 key 是否可能存在");
System.out.println();
// 模拟数据库中已有的 10 万个用户ID
int userCount = 100_000;
BloomFilter<String> userFilter = new BloomFilter<>(userCount, 0.001);
for (int i = 1; i <= userCount; i++) {
userFilter.put("user:" + i);
}
// 模拟 1000 次查询
int dbQueries = 0;
int totalQueries = 1000;
for (int i = 0; i < totalQueries; i++) {
String key = "user:" + (int) (Math.random() * 200_000); // 一半存在，一半不存在
if (userFilter.mightContain(key)) {
// 可能存在，需要查询数据库确认
dbQueries++;
} else {
// 一定不存在，直接返回空，无需查数据库
}
}
System.out.printf("总查询次数: %d%n", totalQueries);
System.out.printf("实际查询数据库: %d 次%n", dbQueries);
System.out.printf("拦截率: %.1f%%%n", (1 - (double) dbQueries / totalQueries) * 100);
System.out.println("说明：对于不存在的 key，布隆过滤器直接拦截，避免缓存穿透攻击数据库");
}
}
运行结果示例
=== 基础功能测试 ===
插入: https://blog.keli.site/post-1
插入: https://blog.keli.site/post-2
插入: https://blog.keli.site/post-3
查询 'post-1': true
查询 'post-2': true
查询 'post-999(未插入)': false
BloomFilter{bitSize=958506, hashFunctions=7, inserted=3, expected=1000, targetFpp=0.0100, currentFpp=0.000000}
=== 大规模假阳性率测试 ===
插入元素: 100,000
测试元素: 100,000
假阳性次数: 1,023
目标假阳性率: 1.0000%
实际假阳性率: 1.0230%
位数组使用率: 50.12%
BloomFilter{bitSize=9585058, hashFunctions=7, inserted=100000, expected=100000, targetFpp=0.0100, currentFpp=0.010230}
=== 缓存穿透防护场景 ===
总查询次数: 1000
实际查询数据库: 523 次
拦截率: 47.7%
说明：对于不存在的 key，布隆过滤器直接拦截，避免缓存穿透攻击数据库
五、进阶：计数布隆过滤器与可删除设计
标准布隆过滤器不支持删除，因为置 0 一个位可能影响其他元素。若需要删除能力，可将位数组扩展为计数器数组（Counter Array），每个位用一个较小的整数（如 4 bit）表示被多少个元素映射到该位置。
/**
* 计数布隆过滤器（支持删除）
* 每个槽位用 byte 计数（最大255，适用于中等规模数据）
*/
public class CountingBloomFilter<T> {
private final byte[] counters;
private final int bitSize;
private final int hashFunctions;
public CountingBloomFilter(int expectedInsertions, double falsePositiveProbability) {
this.bitSize = (int) (-expectedInsertions * Math.log(falsePositiveProbability)
/ (Math.log(2) * Math.log(2)));
this.hashFunctions = Math.max(1, (int) Math.round((double) bitSize / expectedInsertions * Math.log(2)));
this.counters = new byte[bitSize];
}
public void put(T element) {
int[] positions = hashPositions(element);
for (int pos : positions) {
if (counters[pos] < Byte.MAX_VALUE) {
counters[pos]++;
}
}
}
public void remove(T element) {
int[] positions = hashPositions(element);
for (int pos : positions) {
if (counters[pos] > 0) {
counters[pos]--;
}
}
}
public boolean mightContain(T element) {
int[] positions = hashPositions(element);
for (int pos : positions) {
if (counters[pos] == 0) {
return false;
}
}
return true;
}
private int[] hashPositions(T element) {
// 复用相同的哈希策略...
return new int[0]; // 简略示意
}
}
注意：计数器存在溢出风险，需根据业务规模选择计数器位数（byte / short / int）。
六、时间复杂度与空间复杂度
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 插入 | (O(k)) | (O(m)) 位 |
| 查询 | (O(k)) | (O(m)) 位 |
| 删除（计数版） | (O(k)) | (O(m \times c)) 位，(c) 为计数器位数 |
其中 (k) 为哈希函数个数（通常 3~10），(m) 为位数组长度。由于 (k) 是常数，布隆过滤器的插入和查询均为常数时间。
七、总结
布隆过滤器以可接受的假阳性率为代价，换取了极致的空间效率和常数查询时间。它在以下场景中广泛应用：
- URL 去重：爬虫系统快速判断链接是否已抓取
- 缓存穿透防护：Redis 前置拦截不存在的 key
- 数据库查询优化：先查布隆过滤器，避免无效的磁盘 I/O
- 比特币轻节点：SPV 验证用布隆过滤器筛选相关交易
本文实现的 Java 版本支持自定义预期元素数量和假阳性率，自动计算最优参数，并采用 MurmurHash3 提供高质量的哈希分布。读者可以直接将其集成到项目中，或基于计数版本扩展删除能力。
