giftiaのblog

布隆过滤器

· 更新于 · giftia

布隆过滤器是什么

在处理海量数据去重或判断"是否存在"时，如果使用 Map 或 Set，内存开销会随数据量线性增长。

布隆过滤器是一种概率型数据结构。它的核心权衡是：用极小的内存消耗，换取一定的"误判率"。

它的回答只有两种可能：

  1. 绝对不在集合中（100% 准确）。
  2. 可能在集合中（存在误判概率）。

原理与结构

布隆过滤器的底层是一个位数组和一组无偏哈希函数。

flowchart TB
    subgraph 添加["添加元素 x"]
        A["元素 x"] --> H1["Hash1 → 位置 3"] & H2["Hash2 → 位置 5"] & H3["Hash3 → 位置 8"]
        H1 --> B1["Bit[3] = 1"]
        H2 --> B2["Bit[5] = 1"]
        H3 --> B3["Bit[8] = 1"]
    end

    subgraph 查询["查询元素 y (y ≠ x)"]
        Q["元素 y"] --> QH1["Hash1 → 位置 1"] & QH2["Hash2 → 位置 5"] & QH3["Hash3 → 位置 8"]
        QH1 --> R1["Bit[1] = 0 ⚠️"]
        QH2 --> R2["Bit[5] = 1"]
        QH3 --> R3["Bit[8] = 1"]
        R1 --> RESULT["任一为 0 → 绝对不存在"]
    end

工作流程：

  1. 初始化：所有位（Bit）置为 0。
  2. 添加元素：
    • 将元素通过 k 个哈希函数计算，得到 k 个位置。
    • 将位数组中对应的这些位置全部置为 1。
  3. 查询元素：
    • 将待查询元素通过同样的 k 个哈希函数计算。
    • 如果所有位置都是 1：认为元素"可能存在"。
    • 如果任一位置是 0：认为元素"绝对不存在"。

应用场景

  1. 防止缓存穿透： 在访问数据库前，先通过布隆过滤器判断 Key 是否存在。 如果不存在直接返回，避免无效请求击穿缓存直达数据库。
  2. 爬虫 URL 去重： 存入数亿级 URL，快速判断某个网页是否已经爬取过，节省内存。
  3. 垃圾邮件过滤： 从数十亿个垃圾邮件地址中快速匹配。
  4. 黑名单系统： 如恶意 IP 过滤、敏感词检查。

进阶版：布隆过滤器的变体

  1. Counting Bloom Filter (可计数布隆过滤器)

    • 解决问题：不支持删除。
    • 原理：将位数组的每个 Bit 换成一个 Counter (计数器)。
    • 操作：添加时 +1，删除时 -1。虽然增加了空间占用，但支持了动态删除。

  2. Cuckoo Filter (布谷鸟过滤器)

    • 优势：支持动态删除，且在误判率较低时，查询性能优于布隆过滤器，空间利用率更高。
    • 原理：基于布谷鸟哈希算法，通过指纹（Fingerprint）存储元素特征。