每日算法 — 使用java实现布隆过滤器：位数组与多哈希函数的空间高效判重

引言

布隆过滤器（Bloom Filter）由 Burton Howard Bloom 于1970年提出，是一种空间效率极高的概率型数据结构。它能够以极小的内存开销判断一个元素”可能存在”或”肯定不存在”于集合中，允许少量误判（false positive）但绝不会漏判（false negative）。Google Chrome 的恶意网址检测、HBase 和 Cassandra 的 SSTable 查询优化、比特币网络的交易过滤都广泛使用了布隆过滤器。

本文将用 Java 实现一个标准布隆过滤器，深入讲解位数组布局、多哈希函数设计、误判率计算与优化策略。

核心原理

布隆过滤器由以下两部分组成：

1. 位数组（Bit Array）：长度为 m 的数组，所有位初始化为 0
2. k 个独立哈希函数：每个函数将元素映射到位数组的一个位置

插入流程

对元素 x 执行 k 次哈希，得到 k 个位置索引，将这 k 个位置都置为 1。

查询流程

对元素 x 执行同样的 k 次哈希，检查这 k 个位置是否都为 1：
– 如果任意一位为 0，则 x 肯定不在集合中
– 如果全为 1，则 x 可能在集合中（存在误判可能）

误判率公式

当插入 n 个元素后，某一位仍为 0 的概率为：

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

误判率（所有 k 个位置恰好都为 1 的概率）：

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

最优哈希函数数量（使误判率最小）：

$$k = \frac{m}{n} \ln 2$$

此时最优位数组大小：

$$m = -\frac{n \ln \epsilon}{(\ln 2)^2}$$

Java 实现

基础版布隆过滤器

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

public class BloomFilter<T> {
    private final BitSet bitSet;
    private final int bitSize;      // 位数组大小 m
    private final int hashCount;    // 哈希函数数量 k
    private final int seed;         // 哈希种子，用于生成不同的哈希函数
    private int elementCount;       // 已插入元素数量

    /**
     * 创建布隆过滤器
     * @param expectedElements 预计插入元素数量 n
     * @param falsePositiveRate 期望误判率 ε（如 0.01 表示 1%）
     */
    public BloomFilter(int expectedElements, double falsePositiveRate) {
        // 根据公式计算最优位数组大小 m
        this.bitSize = (int) Math.ceil(
            -expectedElements * Math.log(falsePositiveRate) / (Math.log(2) * Math.log(2))
        );
        // 计算最优哈希函数数量 k
        this.hashCount = (int) Math.ceil(
            (double) bitSize / expectedElements * Math.log(2)
        );
        this.bitSet = new BitSet(bitSize);
        this.seed = 0x5bd1e995; // MurmurHash 常用种子
        this.elementCount = 0;

        System.out.println("布隆过滤器配置: m=" + bitSize + ", k=" + hashCount);
    }

    /**
     * MurmurHash 变体：将对象转换为多个哈希值
     * 通过不同的偏移量模拟 k 个独立哈希函数
     */
    private int[] generateHashes(T element) {
        int[] hashes = new int[hashCount];
        byte[] data = element.toString().getBytes(StandardCharsets.UTF_8);

        for (int i = 0; i < hashCount; i++) {
            hashes[i] = murmurHash(data, seed + i * 0x9e3779b9) % bitSize;
            if (hashes[i] < 0) {
                hashes[i] += bitSize;
            }
        }
        return hashes;
    }

    /**
     * 简化的 MurmurHash3 32-bit 实现
     */
    private int murmurHash(byte[] data, int seed) {
        int hash = seed;
        final int c1 = 0xcc9e2d51;
        final int c2 = 0x1b873593;
        final int r1 = 15;
        final int r2 = 13;
        final int m = 5;
        final int n = 0xe6546b64;

        int length = data.length;
        int offset = 0;

        // 每次处理 4 个字节
        while (length >= 4) {
            int k = (data[offset] & 0xff) |
                    ((data[offset + 1] & 0xff) << 8) |
                    ((data[offset + 2] & 0xff) << 16) |
                    ((data[offset + 3] & 0xff) << 24);

            k *= c1;
            k = (k << r1) | (k >>> (32 - r1));
            k *= c2;

            hash ^= k;
            hash = (hash << r2) | (hash >>> (32 - r2));
            hash = hash * m + n;

            offset += 4;
            length -= 4;
        }

        // 处理剩余字节
        int k = 0;
        switch (length) {
            case 3: k ^= (data[offset + 2] & 0xff) << 16;
            case 2: k ^= (data[offset + 1] & 0xff) << 8;
            case 1: k ^= (data[offset] & 0xff);
                k *= c1;
                k = (k << r1) | (k >>> (32 - r1));
                k *= c2;
                hash ^= k;
        }

        hash ^= data.length;
        hash ^= (hash >>> 16);
        hash *= 0x85ebca6b;
        hash ^= (hash >>> 13);
        hash *= 0xc2b2ae35;
        hash ^= (hash >>> 16);

        return hash;
    }

    /**
     * 向过滤器中添加元素
     */
    public void add(T element) {
        int[] hashes = generateHashes(element);
        for (int hash : hashes) {
            bitSet.set(hash);
        }
        elementCount++;
    }

    /**
     * 判断元素是否可能在集合中
     * @return true: 可能存在（可能误判）；false: 肯定不存在
     */
    public boolean mightContain(T element) {
        int[] hashes = generateHashes(element);
        for (int hash : hashes) {
            if (!bitSet.get(hash)) {
                return false; // 有一位为 0，肯定不存在
            }
        }
        return true; // 全为 1，可能存在
    }

    /**
     * 计算当前实际误判率的理论值
     */
    public double getCurrentFalsePositiveRate() {
        return Math.pow(1 - Math.exp(-hashCount * (double) elementCount / bitSize), hashCount);
    }

    /**
     * 获取位数组填充率
     */
    public double getFillRate() {
        return (double) bitSet.cardinality() / bitSize;
    }

    public int getBitSize() {
        return bitSize;
    }

    public int getHashCount() {
        return hashCount;
    }

    public int size() {
        return elementCount;
    }

    /**
     * 清空过滤器
     */
    public void clear() {
        bitSet.clear();
        elementCount = 0;
    }
}

计数布隆过滤器（支持删除）

标准布隆过滤器不支持删除，因为删除可能误删其他元素对应的位置。计数布隆过滤器将每一位扩展为计数器：

public class CountingBloomFilter<T> {
    private final short[] counters;  // 使用 short 作为计数器
    private final int bitSize;
    private final int hashCount;
    private final int seed;
    private int elementCount;

    public CountingBloomFilter(int expectedElements, double falsePositiveRate) {
        this.bitSize = (int) Math.ceil(
            -expectedElements * Math.log(falsePositiveRate) / (Math.log(2) * Math.log(2))
        );
        this.hashCount = (int) Math.ceil(
            (double) bitSize / expectedElements * Math.log(2)
        );
        this.counters = new short[bitSize];
        this.seed = 0x5bd1e995;
        this.elementCount = 0;
    }

    // 复用相同的哈希生成逻辑...
    private int[] generateHashes(T element) {
        int[] hashes = new int[hashCount];
        byte[] data = element.toString().getBytes(StandardCharsets.UTF_8);
        for (int i = 0; i < hashCount; i++) {
            hashes[i] = Math.abs(murmurHash(data, seed + i * 0x9e3779b9)) % bitSize;
        }
        return hashes;
    }

    private int murmurHash(byte[] data, int seed) {
        // 简化版 MurmurHash，与上文相同
        int hash = seed;
        for (int i = 0; i < data.length; i++) {
            hash ^= (data[i] & 0xff);
            hash *= 0x01000193;
        }
        return hash;
    }

    public void add(T element) {
        int[] hashes = generateHashes(element);
        for (int hash : hashes) {
            if (counters[hash] < Short.MAX_VALUE) {
                counters[hash]++;
            }
        }
        elementCount++;
    }

    public void remove(T element) {
        int[] hashes = generateHashes(element);
        for (int hash : hashes) {
            if (counters[hash] > 0) {
                counters[hash]--;
            }
        }
        elementCount--;
    }

    public boolean mightContain(T element) {
        int[] hashes = generateHashes(element);
        for (int hash : hashes) {
            if (counters[hash] <= 0) {
                return false;
            }
        }
        return true;
    }
}

性能测试与验证

import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class BloomFilterDemo {
    public static void main(String[] args) {
        int expectedElements = 100_000;
        double targetFPR = 0.01; // 1% 目标误判率

        BloomFilter<String> filter = new BloomFilter<>(expectedElements, targetFPR);
        Set<String> actualSet = new HashSet<>();
        Random random = new Random();

        System.out.println("=== 布隆过滤器测试 ===\n");

        // 插入 10 万个元素
        System.out.println("插入 " + expectedElements + " 个元素...");
        for (int i = 0; i < expectedElements; i++) {
            String element = "user-" + random.nextInt(10_000_000);
            filter.add(element);
            actualSet.add(element);
        }

        System.out.println("位数组大小: " + filter.getBitSize() + " bits = " + 
                           (filter.getBitSize() / 8 / 1024) + " KB");
        System.out.println("哈希函数数: " + filter.getHashCount());
        System.out.println("位数组填充率: " + String.format("%.2f%%", filter.getFillRate() * 100));
        System.out.println("理论误判率: " + String.format("%.4f%%", filter.getCurrentFalsePositiveRate() * 100));
        System.out.println("HashSet 占用内存估算: " + (expectedElements * 32 / 1024) + " KB+\n");

        // 测试：查询已插入的元素（应全部命中）
        int truePositives = 0;
        for (String element : actualSet) {
            if (filter.mightContain(element)) {
                truePositives++;
            }
        }
        System.out.println("已插入元素查询命中率: " + truePositives + "/" + actualSet.size());

        // 测试：查询未插入的元素（统计误判）
        int falsePositives = 0;
        int testCount = 100_000;
        for (int i = 0; i < testCount; i++) {
            String element = "test-" + random.nextInt(10_000_000) + "-new";
            if (!actualSet.contains(element) && filter.mightContain(element)) {
                falsePositives++;
            }
        }
        System.out.println("未插入元素误判数: " + falsePositives + "/" + testCount);
        System.out.println("实际误判率: " + String.format("%.4f%%", (double) falsePositives / testCount * 100));
    }
}

布隆过滤器的变体

实际应用场景

1. 数据库查询优化：HBase/Cassandra 用布隆过滤器避免读取不存在的 SSTable
2. 缓存穿透防护：Redis 前部署布隆过滤器，拦截肯定不存在的 key
3. URL 去重：爬虫系统快速判断 URL 是否已抓取
4. 比特币 SPV 节点：过滤不相关的交易，减少带宽
5. 推荐系统去重：防止重复推荐用户已看过的内容

总结

布隆过滤器以可控的误判率为代价，换取了极高的空间效率（通常比哈希表节省 90% 以上内存）。其核心设计思想——”用概率换空间”——在大数据和高并发场景下具有不可替代的价值。掌握布隆过滤器的原理与实现，是构建高性能系统的必备技能。