CodeWalk

手写布隆过滤器Bloom Filter实现

作者：我还是少年 · 2026-05-30 12:55

请手写一个布隆过滤器（Bloom Filter），支持add和mightContain操作。什么是布隆过滤器？它的原理是什么？为什么说布隆过滤器有假阳性（False Positive）但没有假阴性（False Negative）？如何根据预期元素数量和可接受的误判率计算位数组大小和哈希函数个数？

回答

我还是少年

原理

布隆过滤器是一个很长的二进制向量和一系列随机哈希函数，用于快速判断一个元素是否在集合中。

  • add：对元素进行k次哈希，将对应位设为1
  • mightContain：对元素进行k次哈希，检查所有位是否都为1
    • 如果有任一位为0 → 一定不在集合中
    • 如果所有位都为1 → 可能在集合中（假阳性）

参数计算公式

设：

  • n = 预期元素数量
  • p = 期望误判率（如0.01 = 1%）
  • m = 位数组长度（bit数）
  • k = 哈希函数个数
m = -n * ln(p) / (ln(2)^2)
k = (m/n) * ln(2)

例：n=100万, p=1% → m≈8MB, k≈7个哈希函数

手写实现

public class BloomFilter<T> {
    private final BitSet bits;           // 位数组
    private final int bitSize;           // 位数组长度
    private final int numHashFunctions;  // 哈希函数个数
    
    public BloomFilter(int expectedCount, double falsePositiveRate) {
        this.bitSize = (int) Math.ceil(-expectedCount * Math.log(falsePositiveRate) 
                         / (Math.log(2) * Math.log(2)));
        this.numHashFunctions = (int) Math.ceil(
            (double) bitSize / expectedCount * Math.log(2));
        this.bits = new BitSet(bitSize);
    }
    
    // 默认误判率1%
    public BloomFilter(int expectedCount) {
        this(expectedCount, 0.01);
    }
    
    public void add(T element) {
        int[] hashes = hash(element);
        for (int i = 0; i < numHashFunctions; i++) {
            bits.set(Math.abs(hashes[i] % bitSize));
        }
    }
    
    public boolean mightContain(T element) {
        int[] hashes = hash(element);
        for (int i = 0; i < numHashFunctions; i++) {
            if (!bits.get(Math.abs(hashes[i] % bitSize))) {
                return false;  // 某一位为0 → 一定不存在
            }
        }
        return true;  // 所有位为1 → 可能存在（假阳性）
    }
    
    // 使用MurmurHash算法生成多个哈希值
    private int[] hash(T element) {
        int h1 = element.hashCode();
        int h2 = h1 >>> 16;
        int[] result = new int[numHashFunctions];
        for (int i = 0; i < numHashFunctions; i++) {
            // 通过h1 + i*h2 生成k个不同的哈希值
            result[i] = h1 + i * h2;
        }
        return result;
    }
}

优缺点

特性说明
假阳性可能（位可能被其他元素设置）
假阴性不可能（如果元素已添加，其所有位必然都为1）
删除操作不支持（不能将1重置为0）
空间效率极高，比传统集合少几十倍内存

应用场景：

  • 防止缓存穿透（先查布隆过滤器，不存在则直接返回）
  • 爬虫URL去重
  • 垃圾邮件过滤