概述

布隆过滤器（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模块为分布式环境提供了开箱即用的布隆过滤器实现。

贡献者

withesse

更新日志

2026/3/14 13:09

查看所有更新日志

• 9f6c2-feat: organize wiki content and refresh site setup于 2026/3/14

编辑此页