布隆过滤器：用极小空间高效判断“可能存在”-牧云

在大数据和高并发系统中，我们常常需要快速判断一个元素是否存在于某个集合中。比如：用户请求的 ID 是否在数据库中？爬虫是否已经抓取过这个 URL？如果每次都去查数据库或磁盘，性能开销巨大。

这时候，布隆过滤器（Bloom Filter） 就派上用场了——它是一种空间效率极高、基于概率的数据结构，能以极小的内存代价，快速告诉你：这个元素肯定不存在，或者可能存在。

核心思想：用位数组 + 多个哈希函数

布隆过滤器内部维护一个位数组（bit array） 和 k 个独立的哈希函数。

插入元素时：对元素分别用 k 个哈希函数计算出 k 个位置，将位数组中这些位置设为 1。
查询元素时：同样计算 k 个位置，只要有一个位置是 0，就说明该元素一定没被插入过；如果全是 1，则可能存在（注意：只是“可能”！）。

✅ 关键特性：

不会漏判：说“不存在”，就绝对不存在。
可能误判：说“存在”，其实可能没插入过（False Positive）。

举个例子 🌰

假设我们有一个长度为 16 的位数组，使用 2 个哈希函数：

插入 "apple"：

hash1("apple") % 16 = 3
hash2("apple") % 16 = 11
设置 bit[3] = 1, bit[11] = 1

查询 "banana"：

hash1("banana") % 16 = 3 → bit[3] = 1 ✅
hash2("banana") % 16 = 7 → bit[7] = 0 ❌
→ 肯定不存在

查询 "orange"（从未插入）：

恰好 hash1("orange")=3, hash2("orange")=11
两个位置都是 1 → 返回“可能存在” → 这就是误判

Java 实现示例

Java 中可以借助 java.util.BitSet 来实现布隆过滤器。下面是一个简化版：

import java.util.BitSet;
import java.util.Objects;

public class BloomFilter {
    private final BitSet bitSet;
    private final int numHashFunctions;
    private final int bitSize;

    public BloomFilter(int expectedInsertions, double fpp) {
        // 计算最优位数组大小 m ≈ -n * ln(p) / (ln2)^2
        this.bitSize = (int) Math.ceil(-expectedInsertions * Math.log(fpp) / (Math.log(2) * Math.log(2)));
        // 最优哈希函数个数 k ≈ (m/n) * ln2
        this.numHashFunctions = (int) Math.ceil(Math.log(2) * bitSize / expectedInsertions);
        this.bitSet = new BitSet(bitSize);
    }

    public void add(String item) {
        Objects.requireNonNull(item);
        long hash64 = hash(item);
        for (int i = 0; i < numHashFunctions; i++) {
            int index = (int) ((hash64 + i * hash64) % bitSize);
            if (index < 0) index += bitSize;
            bitSet.set(index);
        }
    }

    public boolean mightContain(String item) {
        Objects.requireNonNull(item);
        long hash64 = hash(item);
        for (int i = 0; i < numHashFunctions; i++) {
            int index = (int) ((hash64 + i * hash64) % bitSize);
            if (index < 0) index += bitSize;
            if (!bitSet.get(index)) {
                return false; // 肯定不存在
            }
        }
        return true; // 可能存在
    }

    // 简单的 64 位哈希（实际项目建议用 MurmurHash 或 Guava 的 Hashing）
    private long hash(String key) {
        long h = 0;
        for (char c : key.toCharArray()) {
            h = h * 31 + c;
        }
        return h;
    }
}

💡 生产环境建议：直接使用 Google Guava 库中的 BloomFilter，它经过充分测试且性能优异：

BloomFilter<String> filter = BloomFilter.create(
    Funnels.stringFunnel(Charset.defaultCharset()),
    10_000,      // 预期插入数量
    0.01         // 期望误判率（1%）
);
filter.put("apple");
boolean maybeExists = filter.mightContain("banana");

典型应用场景

防止缓存穿透：在 Redis 前加布隆过滤器，拦截无效 ID 请求。
爬虫 URL 去重：避免重复抓取网页。
数据库查询优化：先查布隆过滤器，减少无谓的磁盘 I/O。
垃圾邮件过滤：快速判断发件人是否在黑名单中。

注意事项

❌ 不能删除元素（标准布隆过滤器）。如需删除，可考虑计数布隆过滤器（Counting Bloom Filter）。
⚠️ 误判率可控但不为零：通过调整位数组大小和哈希函数数量来平衡空间与精度。
✅ 永远不会漏掉真实存在的元素：这是它可靠的关键。

总结

布隆过滤器不是万能的，但在“允许少量误判、但绝不容忍漏判”的场景下，它是性价比极高的选择。用几 KB 内存，就能管理百万级数据的存在性判断——这正是其魅力所在。

记住一句话：
“布隆过滤器说没有，那就真的没有；说有，那可能是有。”

合理使用它，你的系统会更轻、更快、更稳。

目录CONTENT

布隆过滤器：用极小空间高效判断“可能存在”