布隆过滤器原理与应用
约 1855 字大约 6 分钟
bloom-filterdata-structure
2025-06-06
概述
布隆过滤器(Bloom Filter)是Burton Howard Bloom在1970年提出的一种空间高效的概率型数据结构,用于判断一个元素是否在集合中。它可能会产生误判(False Positive)——即判断元素存在但实际不存在,但不会漏判(False Negative)——即判断元素不存在则一定不存在。这一特性使其在缓存穿透防护、垃圾邮件检测、数据库查询优化等场景中广泛应用。
基本原理
数据结构
布隆过滤器由一个m位的位数组(Bit Array)和k个哈希函数组成。
添加操作: 将元素通过k个哈希函数分别计算,将位数组中对应的k个位置设为1。
查询操作: 将元素通过k个哈希函数计算,检查位数组中对应的k个位置:
- 如果任何一位为0 → 一定不存在
- 如果全部为1 → 可能存在(可能是其他元素设置的)
误判示例
误判率分析
数学推导
对于一个m位、k个哈希函数、已插入n个元素的布隆过滤器:
某个特定位仍为0的概率:
P(bit=0) = (1 - 1/m)^(kn) ≈ e^(-kn/m)
误判率(所有k位都为1):
FPR = (1 - e^(-kn/m))^k
最优哈希函数个数:
k_optimal = (m/n) * ln(2) ≈ 0.693 * (m/n)
此时最低误判率:
FPR_min = (1/2)^k = (0.6185)^(m/n)参数选择参考表
| 预期元素数(n) | 期望误判率 | 位数组大小(m) | 哈希函数数(k) | 内存占用 |
|---|---|---|---|---|
| 100万 | 1% | 958万位 | 7 | ~1.2MB |
| 100万 | 0.1% | 1437万位 | 10 | ~1.7MB |
| 1000万 | 1% | 9585万位 | 7 | ~11.5MB |
| 1000万 | 0.1% | 1.44亿位 | 10 | ~17MB |
| 1亿 | 1% | 9.6亿位 | 7 | ~115MB |
实现
Java实现
public class BloomFilter<T> {
private final BitSet bitSet;
private final int bitSize; // m
private final int hashCount; // k
private final int expectedInsertions; // n
public BloomFilter(int expectedInsertions, double falsePositiveRate) {
this.expectedInsertions = expectedInsertions;
// 计算最优m
this.bitSize = optimalNumOfBits(expectedInsertions, falsePositiveRate);
// 计算最优k
this.hashCount = optimalNumOfHashFunctions(expectedInsertions, bitSize);
this.bitSet = new BitSet(bitSize);
}
// 添加元素
public void add(T element) {
long hash64 = Hashing.murmur3_128().hashObject(element, funnel()).asLong();
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
// 使用双重哈希生成k个哈希值
for (int i = 0; i < hashCount; i++) {
int combinedHash = hash1 + i * hash2;
if (combinedHash < 0) combinedHash = ~combinedHash;
bitSet.set(combinedHash % bitSize);
}
}
// 查询元素
public boolean mightContain(T element) {
long hash64 = Hashing.murmur3_128().hashObject(element, funnel()).asLong();
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
for (int i = 0; i < hashCount; i++) {
int combinedHash = hash1 + i * hash2;
if (combinedHash < 0) combinedHash = ~combinedHash;
if (!bitSet.get(combinedHash % bitSize)) {
return false; // 一定不存在
}
}
return true; // 可能存在
}
static int optimalNumOfBits(int n, double p) {
return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
static int optimalNumOfHashFunctions(int n, int m) {
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
}Guava BloomFilter
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
// 创建布隆过滤器:预计插入100万元素,误判率1%
BloomFilter<String> filter = BloomFilter.create(
Funnels.stringFunnel(Charset.defaultCharset()),
1_000_000, // expected insertions
0.01 // false positive probability
);
// 添加
filter.put("user:1001");
filter.put("user:1002");
// 查询
filter.mightContain("user:1001"); // true(可能存在)
filter.mightContain("user:9999"); // false(一定不存在)或 true(误判)Counting Bloom Filter
标准布隆过滤器不支持删除操作(因为一位可能被多个元素共享)。计数布隆过滤器将每个位扩展为一个计数器:
public class CountingBloomFilter<T> {
private final int[] counters; // 使用4位计数器(0-15)
private final int size;
private final int hashCount;
public void add(T element) {
int[] indices = getHashIndices(element);
for (int idx : indices) {
if (counters[idx] < 15) { // 防止溢出
counters[idx]++;
}
}
}
public void remove(T element) {
// 先确认元素可能存在
if (!mightContain(element)) return;
int[] indices = getHashIndices(element);
for (int idx : indices) {
if (counters[idx] > 0) {
counters[idx]--;
}
}
}
public boolean mightContain(T element) {
int[] indices = getHashIndices(element);
for (int idx : indices) {
if (counters[idx] == 0) return false;
}
return true;
}
}代价: 每个位置从1位扩展为4位,内存占用增加4倍。
Cuckoo Filter
Cuckoo Filter是2014年由CMU的Bin Fan等人提出的布隆过滤器替代方案,支持删除操作且在相同误判率下通常更节省空间。
Bloom Filter vs Cuckoo Filter
| 特性 | Bloom Filter | Cuckoo Filter |
|---|---|---|
| 支持删除 | 否(Counting BF可以) | 是 |
| 空间效率 | 好 | 更好(相同FPR下) |
| 查找性能 | O(k) 次哈希 | O(1) 平均(检查2个桶) |
| 插入性能 | O(k) | O(1) 平均(可能需要踢出) |
| 误判率 < 3% | Bloom更优 | Cuckoo更优 |
| 实现复杂度 | 简单 | 中等 |
Redis Bloom Filter
Redis通过RedisBloom模块提供原生的布隆过滤器支持。
# 创建布隆过滤器(Redis命令)
BF.RESERVE user_filter 0.01 1000000
# 参数:key, error_rate, capacity
# 添加元素
BF.ADD user_filter "user:1001"
BF.MADD user_filter "user:1002" "user:1003" "user:1004"
# 查询
BF.EXISTS user_filter "user:1001" # 1 (可能存在)
BF.EXISTS user_filter "user:9999" # 0 (一定不存在)
BF.MEXISTS user_filter "user:1001" "user:9999" # 1 0// Jedis + RedisBloom
JedisPool pool = new JedisPool("localhost", 6379);
try (Jedis jedis = pool.getResource()) {
// 创建布隆过滤器
jedis.sendCommand(
Command.of("BF.RESERVE"), "user_filter", "0.01", "1000000");
// 添加
jedis.sendCommand(Command.of("BF.ADD"), "user_filter", "user:1001");
// 查询
Object result = jedis.sendCommand(
Command.of("BF.EXISTS"), "user_filter", "user:1001");
}应用场景
缓存穿透防护
其他应用
- 垃圾邮件检测:将已知垃圾邮件地址/特征加入布隆过滤器
- 网页爬虫去重:避免重复爬取已访问的URL
- 数据库查询优化:HBase/Cassandra使用布隆过滤器避免不必要的磁盘读取
- 弱密码检测:将常见弱密码加入布隆过滤器,注册时快速检查
- 推荐系统去重:避免推荐用户已浏览过的内容
总结
布隆过滤器以极低的空间成本实现了高效的集合成员检测,其"不存在一定不存在,存在可能存在"的特性在很多场景中恰好满足需求。参数选择(位数组大小m和哈希函数个数k)直接影响误判率,需要根据预期数据量和可接受的误判率进行计算。对于需要删除操作的场景,可以选择Counting Bloom Filter或Cuckoo Filter。Redis的RedisBloom模块为分布式环境提供了开箱即用的布隆过滤器实现。
贡献者
更新日志
9f6c2-feat: organize wiki content and refresh site setup于