引言
在海量数据场景下，精确去重（如HashSet）往往消耗巨大的内存空间。布隆过滤器（Bloom Filter）以极小的空间代价和可控的假阳性率，成为大规模系统中不可或缺的概率性数据结构。从Google BigTable到Redis缓存穿透防护，布隆过滤器的身影无处不在。本文将用Java从零实现一个完整的布隆过滤器，涵盖多哈希函数设计、位数组操作、假阳性率分析，以及一个支持元素删除的Counting Bloom Filter扩展。
核心原理
布隆过滤器维护一个长度为 $m$ 的位数组和 $k$ 个独立的哈希函数。插入元素时，用 $k$ 个哈希函数分别计算位置并将对应位设为1；查询时检查这 $k$ 个位置是否均为1：
– 若任一位置为0 → 元素一定不存在（无假阴性）
– 若全为1 → 元素可能存在（存在假阳性）
假阳性率近似为：
$$f \approx \left(1 – e^{-kn/m}\right)^k$$
最优哈希函数数量 $k = \frac{m}{n} \ln 2$，其中 $n$ 为期望元素数。
基础实现：标准布隆过滤器
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;
/**
* 标准布隆过滤器实现
* 使用BitSet作为底层位数组，支持MD5/SHA-256派生多哈希函数
*/
public class BloomFilter<T> {
private final BitSet bitSet;
private final int bitSize; // 位数组大小 m
private final int hashFunctions; // 哈希函数数量 k
private final int expectedElements; // 期望元素数 n
private int elementCount = 0; // 实际插入元素数
/**
* 构造布隆过滤器
* @param expectedElements 期望插入元素数量 n
* @param falsePositiveRate 可接受的假阳性率 f（如 0.01 表示1%）
*/
public BloomFilter(int expectedElements, double falsePositiveRate) {
this.expectedElements = expectedElements;
// 根据公式计算最优位数组大小：m = -n * ln(f) / (ln2)^2
this.bitSize = (int) Math.ceil(
-expectedElements * Math.log(falsePositiveRate) / (Math.log(2) * Math.log(2))
);
// 最优哈希函数数量：k = m/n * ln2
this.hashFunctions = Math.max(1, (int) Math.round(
(double) bitSize / expectedElements * Math.log(2)
));
this.bitSet = new BitSet(bitSize);
}
/**
* 直接使用指定位数组大小和哈希函数数量构造
*/
public BloomFilter(int bitSize, int hashFunctions, int expectedElements) {
this.bitSize = bitSize;
this.hashFunctions = hashFunctions;
this.expectedElements = expectedElements;
this.bitSet = new BitSet(bitSize);
}
/**
* 插入元素
* 对元素计算k个哈希位置，全部置为1
*/
public void add(T element) {
byte[] data = element.toString().getBytes(StandardCharsets.UTF_8);
int[] hashes = generateHashes(data, hashFunctions, bitSize);
for (int hash : hashes) {
bitSet.set(hash, true);
}
elementCount++;
}
/**
* 查询元素是否可能存在
* @return true表示可能存在（含假阳性），false表示一定不存在
*/
public boolean mightContain(T element) {
byte[] data = element.toString().getBytes(StandardCharsets.UTF_8);
int[] hashes = generateHashes(data, hashFunctions, bitSize);
for (int hash : hashes) {
if (!bitSet.get(hash)) {
return false; // 任一位置为0，则一定不存在
}
}
return true; // 全为1，可能存在
}
/**
* 计算当前假阳性率的理论估计
*/
public double currentFalsePositiveRate() {
return Math.pow(1 - Math.exp(-hashFunctions * (double) elementCount / bitSize), hashFunctions);
}
/**
* 使用双重哈希技术从两个基础哈希生成k个独立哈希
* 基于论文 "Less Hashing, Same Performance" (Kirsch & Mitzenmacher, 2006)
* 公式：g_i(x) = (h1(x) + i * h2(x)) % m
* @param data 元素字节数组
* @param k 需要的哈希数量
* @param mod 取模值（位数组大小）
* @return k个哈希位置
*/
public static int[] generateHashes(byte[] data, int k, int mod) {
int[] result = new int[k];
// 计算两个基础哈希值
long h1 = murmurHash64(data, 0x9747b28c); // 使用不同种子
long h2 = fnv1aHash64(data);
for (int i = 0; i < k; i++) {
// 双重哈希组合，取绝对值后取模
long combined = (h1 + (long) i * h2) & Long.MAX_VALUE; // 确保非负
result[i] = (int) (combined % mod);
}
return result;
}
/**
* MurmurHash3 64位变体 - 高性能非加密哈希
*/
public static long murmurHash64(byte[] data, long seed) {
long m = 0xc6a4a7935bd1e995L;
int r = 47;
long h = seed ^ (data.length * m);
int length8 = data.length / 8;
for (int i = 0; i < length8; i++) {
long k = 0;
for (int j = 0; j < 8; j++) {
k |= ((long) data[i * 8 + j] & 0xffL) << (8 * j);
}
k *= m;
k ^= k >>> r;
k *= m;
h ^= k;
h *= m;
}
// 处理剩余字节
int remaining = data.length % 8;
for (int i = remaining - 1; i >= 0; i--) {
h ^= ((long) data[(length8 * 8) + i] & 0xffL) << (8 * i);
}
h *= m;
h ^= h >>> r;
h *= m;
h ^= h >>> r;
return h;
}
/**
* FNV-1a 64位哈希 - 另一种高质量的简单哈希函数
*/
public static long fnv1aHash64(byte[] data) {
long hash = 0xcbf29ce484222325L; // FNV offset basis
long prime = 0x100000001b3L; // FNV prime
for (byte b : data) {
hash ^= (b & 0xff);
hash *= prime;
}
return hash;
}
public int getBitSize() { return bitSize; }
public int getHashFunctionCount() { return hashFunctions; }
public int getElementCount() { return elementCount; }
/**
* 打印过滤器统计信息
*/
public void printStats() {
int setBits = bitSet.cardinality();
System.out.printf("BloomFilter Stats:%n");
System.out.printf(" 位数组大小: %d bits (%.2f KB)%n", bitSize, bitSize / 8.0 / 1024);
System.out.printf(" 哈希函数数: %d%n", hashFunctions);
System.out.printf(" 已插入元素: %d / 期望 %d%n", elementCount, expectedElements);
System.out.printf(" 已置位数量: %d / %d (%.2f%%)%n", setBits, bitSize, 100.0 * setBits / bitSize);
System.out.printf(" 当前假阳性率: %.4f%%%n", currentFalsePositiveRate() * 100);
System.out.printf(" 每个元素占用: %.2f bits%n", (double) bitSize / elementCount);
}
}
扩展实现：Counting Bloom Filter（支持删除）
标准布隆过滤器无法删除元素（直接将位置0可能误删其他元素）。Counting Bloom Filter将每个位扩展为计数器，插入时计数+1，删除时计数-1，查询时检查是否全部>0。
/**
* Counting Bloom Filter - 支持元素删除的布隆过滤器
* 使用4位计数器（半字节）数组，每个槽位计数范围0-15
* 适合需要删除操作的场景，如缓存失效、动态集合
*/
public class CountingBloomFilter<T> {
private final byte[] counters; // 每个元素存4位计数器，所以byte数组长度为 bitSize/2 (向上取整)
private final int bitSize;
private final int hashFunctions;
private int elementCount = 0;
private static final int MAX_COUNT = 15; // 4位计数器上限
public CountingBloomFilter(int expectedElements, double falsePositiveRate) {
this.bitSize = (int) Math.ceil(
-expectedElements * Math.log(falsePositiveRate) / (Math.log(2) * Math.log(2))
);
this.hashFunctions = Math.max(1, (int) Math.round(
(double) bitSize / expectedElements * Math.log(2)
));
// 每个byte存储2个4位计数器
this.counters = new byte[(bitSize + 1) / 2];
}
/**
* 获取位置i的计数器值
*/
private int getCounter(int i) {
int byteIdx = i / 2;
if (i % 2 == 0) {
return (counters[byteIdx] & 0x0F);
} else {
return ((counters[byteIdx] & 0xF0) >>> 4);
}
}
/**
* 设置位置i的计数器值
*/
private void setCounter(int i, int value) {
int byteIdx = i / 2;
value = Math.min(value, MAX_COUNT);
if (i % 2 == 0) {
counters[byteIdx] = (byte) ((counters[byteIdx] & 0xF0) | (value & 0x0F));
} else {
counters[byteIdx] = (byte) ((counters[byteIdx] & 0x0F) | ((value & 0x0F) << 4));
}
}
/**
* 插入元素：k个位置的计数器均+1
*/
public void add(T element) {
byte[] data = element.toString().getBytes(java.nio.charset.StandardCharsets.UTF_8);
int[] hashes = BloomFilter.generateHashes(data, hashFunctions, bitSize);
for (int hash : hashes) {
int count = getCounter(hash);
setCounter(hash, Math.min(count + 1, MAX_COUNT));
}
elementCount++;
}
/**
* 删除元素：k个位置的计数器均-1（需确保元素曾插入，否则导致假阴性）
*/
public void remove(T element) {
byte[] data = element.toString().getBytes(java.nio.charset.StandardCharsets.UTF_8);
int[] hashes = BloomFilter.generateHashes(data, hashFunctions, bitSize);
for (int hash : hashes) {
int count = getCounter(hash);
if (count > 0) {
setCounter(hash, count - 1);
}
}
elementCount--;
}
/**
* 查询元素：k个位置计数器全部>0则可能存在
*/
public boolean mightContain(T element) {
byte[] data = element.toString().getBytes(java.nio.charset.StandardCharsets.UTF_8);
int[] hashes = BloomFilter.generateHashes(data, hashFunctions, bitSize);
for (int hash : hashes) {
if (getCounter(hash) == 0) {
return false;
}
}
return true;
}
public int getBitSize() { return bitSize; }
public int getHashFunctionCount() { return hashFunctions; }
}
性能测试与假阳性率验证
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
/**
* 布隆过滤器综合测试与假阳性率验证
*/
public class BloomFilterTest {
public static void main(String[] args) {
testBasicOperations();
testFalsePositiveRate();
testCountingBloomFilter();
compareWithHashSet();
}
static void testBasicOperations() {
System.out.println("===== 基础操作测试 =====");
BloomFilter<String> bf = new BloomFilter<>(10000, 0.01);
String[] added = {"apple", "banana", "cherry", "date", "elderberry"};
for (String s : added) bf.add(s);
for (String s : added) {
System.out.printf("'%s' 可能存在? %b%n", s, bf.mightContain(s));
}
System.out.printf("'grape' 可能存在? %b (应为false)%n", bf.mightContain("grape"));
bf.printStats();
}
static void testFalsePositiveRate() {
System.out.println("\n===== 假阳性率验证 =====");
int n = 100000;
double targetFPR = 0.001; // 0.1%
BloomFilter<Integer> bf = new BloomFilter<>(n, targetFPR);
Random rand = new Random(42);
Set<Integer> inserted = new HashSet<>();
// 插入n个元素（偶数）
for (int i = 0; i < n; i++) {
int val = i * 2;
bf.add(val);
inserted.add(val);
}
// 用n个未插入元素（奇数）测试假阳性
int falsePositives = 0;
for (int i = 0; i < n; i++) {
int val = i * 2 + 1;
if (bf.mightContain(val)) falsePositives++;
}
double actualFPR = (double) falsePositives / n;
System.out.printf("期望假阳性率: %.4f%%%n", targetFPR * 100);
System.out.printf("实际假阳性率: %.4f%% (%d/%d)%n", actualFPR * 100, falsePositives, n);
System.out.printf("理论估计值: %.4f%%%n", bf.currentFalsePositiveRate() * 100);
}
static void testCountingBloomFilter() {
System.out.println("\n===== Counting Bloom Filter 删除测试 =====");
CountingBloomFilter<String> cbf = new CountingBloomFilter<>(1000, 0.01);
cbf.add("alpha");
cbf.add("beta");
cbf.add("gamma");
System.out.printf("删除前 'alpha' 存在? %b%n", cbf.mightContain("alpha"));
cbf.remove("alpha");
System.out.printf("删除后 'alpha' 存在? %b%n", cbf.mightContain("alpha"));
System.out.printf("删除后 'beta' 存在? %b%n", cbf.mightContain("beta"));
}
static void compareWithHashSet() {
System.out.println("\n===== 与HashSet内存对比 =====");
int n = 1000000;
double fpr = 0.01;
BloomFilter<Integer> bf = new BloomFilter<>(n, fpr);
// HashSet<Integer> 每个元素约 32-64 字节（含对象头、指针、int包装）
// BloomFilter 每个元素约 1.44 * log2(1/fpr) 位
System.out.printf("元素数量: %d%n", n);
System.out.printf("BloomFilter 位数组: %d bits = %.2f MB%n",
bf.getBitSize(), bf.getBitSize() / 8.0 / 1024 / 1024);
System.out.printf("每个元素占用: %.2f bits%n", (double) bf.getBitSize() / n);
System.out.printf("HashSet估计占用: ~%.0f MB (假设每个元素32字节)%n", n * 32.0 / 1024 / 1024);
System.out.printf("空间节省比例: %.1f%% (BloomFilter仅占HashSet的 %.2f%%)%n",
(1 - (double) bf.getBitSize() / 8 / (n * 32)) * 100,
100.0 * (bf.getBitSize() / 8.0) / (n * 32));
}
}
参数选择速查表
| 期望元素数 $n$ | 目标假阳性率 $f$ | 位数组大小 $m$ | 哈希函数数 $k$ | 每个元素位开销 |
|---|---|---|---|---|
| 100,000 | 1% | 958,506 bits (117 KB) | 7 | 9.6 bits |
| 100,000 | 0.1% | 1,437,759 bits (175 KB) | 10 | 14.4 bits |
| 1,000,000 | 1% | 9,585,059 bits (1.14 MB) | 7 | 9.6 bits |
| 1,000,000 | 0.1% | 14,377,588 bits (1.71 MB) | 10 | 14.4 bits |
实际应用场景
- 数据库查询优化：Google BigTable/HBase用布隆过滤器避免访问不存在的磁盘块
- 缓存穿透防护：Redis前部署布隆过滤器，拦截对不存在键的请求
- URL去重：爬虫系统判断URL是否已抓取，内存占用仅为传统方案的1/20
- 比特币SPV节点：用布隆过滤器向全节点请求感兴趣交易，保护隐私
扩展方向
- Scalable Bloom Filter：支持动态扩容，在元素数超出预期时自动扩展
- Cuckoo Filter：替代方案，支持删除且查询效率更高，但空间略大
- XOR Filter：静态集合的最优空间方案，查询仅需3次内存访问
- Bloomier Filter：支持键值对存储，每个键关联一个值而非仅存在性
总结
布隆过滤器以”允许微小误差换取巨大空间节省”的设计哲学，成为海量数据系统的基石组件。核心实现仅需百余行代码，却蕴含了概率分析、多哈希设计、位运算优化等丰富的工程技巧。在需要快速存在性查询且可容忍假阳性的场景下，布隆过滤器是无可替代的最优选择。
