每日算法 — 使用java实现布隆过滤器：概率型位图与高效成员查询

布隆过滤器（Bloom Filter）是Burton Howard Bloom于1970年提出的一种空间效率极高的概率型数据结构，用于判断一个元素是否可能属于某个集合。它的核心特点是：可能产生假阳性（false positive，即判断元素在集合中但实际不在），但绝不会产生假阴性（false negative）。这一特性使其在海量数据去重、缓存穿透防护、URL过滤等场景中大放异彩。

核心原理与数学推导

布隆过滤器本质上是一个长度为m的位数组，配合k个独立的哈希函数。插入元素时，将该元素通过k个哈希函数映射为k个数组下标，并将对应位置置为1。查询时，同样计算k个哈希值，若所有对应位均为1，则判断元素”可能存在”；若有任意一位为0，则确定”一定不存在”。

假阳性概率的精确公式为：

$$p = \left(1 – e^{-kn/m}\right)^k$$

其中n为插入元素数量，m为位数组长度，k为哈希函数数量。当 $k = \frac{m}{n} \ln 2$ 时，假阳性概率达到最小值 $(0.6185)^{m/n}$。

Java完整实现

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;

/**
 * 布隆过滤器实现 - 概率型成员查询数据结构
 * 特点：空间极省、查询O(k)、允许可控的假阳性、无假阴性
 * @param <T> 元素类型
 */
public class BloomFilter<T> {
    /** 位数组长度，决定空间占用和精确度 */
    private final int bitSize;
    /** 哈希函数数量，决定计算开销和冲突概率 */
    private final int hashCount;
    /** 底层位数组，Java内置BitSet实现 */
    private final BitSet bitSet;
    /** 已插入元素计数 */
    private int elementCount;

    /**
     * 构造函数：根据期望元素数量和可接受假阳性概率创建布隆过滤器
     * @param expectedElements 预计插入的元素数量
     * @param falsePositiveRate 可接受的假阳性概率（如0.01表示1%）
     */
    public BloomFilter(int expectedElements, double falsePositiveRate) {
        if (expectedElements <= 0 || falsePositiveRate <= 0 || falsePositiveRate >= 1) {
            throw new IllegalArgumentException("参数非法");
        }
        // 根据公式计算最优位数组长度：m = -n * ln(p) / (ln2)^2
        this.bitSize = (int) Math.ceil(
            -expectedElements * Math.log(falsePositiveRate) / (Math.log(2) * Math.log(2))
        );
        // 计算最优哈希函数数量：k = m/n * ln2
        this.hashCount = Math.max(1, (int) Math.round(
            (double) bitSize / expectedElements * Math.log(2)
        ));
        this.bitSet = new BitSet(bitSize);
        this.elementCount = 0;
    }

    /**
     * 直接使用指定位数组大小和哈希函数数量构造
     * @param bitSize 位数组长度
     * @param hashCount 哈希函数数量
     */
    public BloomFilter(int bitSize, int hashCount) {
        this.bitSize = bitSize;
        this.hashCount = hashCount;
        this.bitSet = new BitSet(bitSize);
        this.elementCount = 0;
    }

    /**
     * 使用双重哈希技术生成第i个哈希值
     * 基于MurmurHash思想，通过线性组合两个基础哈希值模拟多个哈希函数
     * @param element 待哈希的元素
     * @param seed 哈希种子，用于生成不同哈希函数
     * @return 哈希值（已取模映射到bitSize范围内）
     */
    private int hash(Object element, int seed) {
        String str = element.toString();
        int hash1 = str.hashCode();
        int hash2 = Integer.reverseBytes(hash1) * 0x5bd1e995 + seed;
        // 线性组合：hash_i = (hash1 + i * hash2) % bitSize
        int combined = Math.abs(hash1 + seed * hash2);
        return combined % bitSize;
    }

    /**
     * 向布隆过滤器中添加元素
     * 时间复杂度：O(k)，k为哈希函数数量
     * @param element 待添加的元素
     */
    public void add(T element) {
        for (int i = 0; i < hashCount; i++) {
            int index = hash(element, i);
            bitSet.set(index);
        }
        elementCount++;
    }

    /**
     * 判断元素是否可能存在于集合中
     * 返回false表示元素一定不存在；返回true表示元素可能存在（有假阳性概率）
     * 时间复杂度：O(k)
     * @param element 待查询的元素
     * @return true表示可能存在，false表示一定不存在
     */
    public boolean mightContain(T element) {
        for (int i = 0; i < hashCount; i++) {
            int index = hash(element, i);
            if (!bitSet.get(index)) {
                // 只要有一个哈希位为0，则元素一定不存在
                return false;
            }
        }
        // 所有哈希位均为1，元素可能存在（也可能是假阳性）
        return true;
    }

    /**
     * 计算当前假阳性概率的理论值
     * 公式：p = (1 - e^(-kn/m))^k
     * @return 当前假阳性概率
     */
    public double currentFalsePositiveRate() {
        return Math.pow(1 - Math.exp(-(double) hashCount * elementCount / bitSize), hashCount);
    }

    /**
     * 获取位数组长度
     */
    public int getBitSize() {
        return bitSize;
    }

    /**
     * 获取哈希函数数量
     */
    public int getHashCount() {
        return hashCount;
    }

    /**
     * 获取已插入元素数量
     */
    public int getElementCount() {
        return elementCount;
    }

    /**
     * 主方法：演示布隆过滤器的去重与查询特性
     */
    public static void main(String[] args) {
        // 创建布隆过滤器：预计100万个元素，1%假阳性率
        BloomFilter<String> filter = new BloomFilter<>(1_000_000, 0.01);
        System.out.println("位数组大小: " + filter.getBitSize() + " bits (" +
            (filter.getBitSize() / 8 / 1024) + " KB)");
        System.out.println("哈希函数数量: " + filter.getHashCount());

        // 批量插入测试数据
        System.out.println("\n插入10000个元素...");
        for (int i = 0; i < 10000; i++) {
            filter.add("user_" + i);
        }
        System.out.println("当前假阳性概率: " + String.format("%.6f", filter.currentFalsePositiveRate()));

        // 查询已存在的元素
        int truePositives = 0;
        for (int i = 0; i < 10000; i++) {
            if (filter.mightContain("user_" + i)) {
                truePositives++;
            }
        }
        System.out.println("已存在元素查询命中: " + truePositives + "/10000");

        // 查询不存在的元素（测试假阳性率）
        int falsePositives = 0;
        for (int i = 10000; i < 20000; i++) {
            if (filter.mightContain("user_" + i)) {
                falsePositives++;
            }
        }
        System.out.println("不存在元素误报数: " + falsePositives + "/10000 (假阳性率: " +
            String.format("%.2f%%", falsePositives / 100.0) + ")");

        // 与HashSet空间占用对比
        System.out.println("\n对比HashSet假设空间: 10000个String引用约需 " +
            (10000 * 32 / 1024) + " KB + 字符串本身存储");
        System.out.println("布隆过滤器实际占用: " + (filter.getBitSize() / 8 / 1024) + " KB");
    }
}

复杂度与空间效率

当期望存储100万元素且假阳性率为1%时，布隆过滤器仅需约1.14MB空间，而HashSet存储100万个字符串至少需要数十MB。

经典应用场景

1. 缓存穿透防护：Redis前部署布隆过滤器，拦截对不存在数据的查询，避免数据库被打穿
2. 海量URL去重：网络爬虫使用布隆过滤器判断URL是否已抓取，节省磁盘IO
3. 比特币SPV节点：轻节点用布隆过滤器向全节点请求可能相关的交易，保护隐私同时减少带宽
4. 数据库查询优化：Cassandra、HBase等使用布隆过滤器判断数据是否存在于SSTable中，避免无效磁盘读取

扩展变体

计数布隆过滤器（Counting Bloom Filter）：将位数组扩展为计数器数组，支持删除操作，但空间开销增加4-8倍。布谷鸟过滤器（Cuckoo Filter）：支持删除且查询效率更高，但需要更高的空间负载因子。