布隆过滤器

💡 一句话概述

布隆过滤器是一种空间高效的概率数据结构，用于判断元素**是否可能存在**——说不存在则一定不存在，说存在则可能不存在。

---

🔑 核心概念

1. 位数组（Bit Array）：底层数据结构是一个 m 位的 bit 数组，初始全为 0。
2. 多个哈希函数：使用 k 个独立的哈希函数，每个元素映射到 k 个 bit 位。
3. 假阳性（False Positive）：不存在的元素可能被所有哈希函数命中的位恰好被其他元素置为 1，导致误判。
4. 无假阴性（No False Negative）：已插入的元素，其所有位一定为 1，判断"存在"时不会漏报。

---

📝 详细说明

工作原理

graph LR
    subgraph 插入元素x["插入元素 x"]
        X["x"] --> H1["h₁(x) = 3"]
        X --> H2["h₂(x) = 7"]
        X --> H3["h₃(x) = 11"]
        H1 --> B3["bit[3] = 1"]
        H2 --> B7["bit[7] = 1"]
        H3 --> B11["bit[11] = 1"]
    end

graph LR
    subgraph 查询y["查询元素 y — 一定不存在"]
        Y["y"] --> YH1["h₁(y) = 3 → bit[3]=1 ✓"]
        Y --> YH2["h₂(y) = 5 → bit[5]=0 ✗"]
        YH1 --> YR["结论：一定不存在"]
        YH2 --> YR
    end

    subgraph 查询z["查询元素 z — 假阳性"]
        Z["z"] --> ZH1["h₁(z)=3 → bit[3]=1 ✓"]
        Z --> ZH2["h₂(z)=7 → bit[7]=1 ✓"]
        Z --> ZH3["h₃(z)=11 → bit[11]=1 ✓"]
        ZH1 --> ZR["结论：可能存在<br/>⚠️ 实际未插入（假阳性）"]
        ZH2 --> ZR
        ZH3 --> ZR
    end

graph LR
    subgraph 位数组["位数组 (m=16)"]
        direction LR
        b0["0"] --- b1["0"] --- b2["0"] --- b3["1"] --- b4["0"] --- b5["0"] --- b6["0"] --- b7["1"]
        b7 --- b8["0"] --- b9["0"] --- b10["0"] --- b11["1"] --- b12["0"] --- b13["0"] --- b14["0"] --- b15["0"]
    end

    插入元素x -.->|h₁ h₂ h₃| b3
    插入元素x -.-> b7
    插入元素x -.-> b11

假阳性率

假阳性率由三个参数决定：位数组大小 m、哈希函数个数 k、已插入元素数 n：

\[p \approx \left(1 - e^{-kn/m}\right)^k\]

给定预期元素数 n 和可接受误判率 p，最优参数为：

参数	公式
位数组大小 m	\(m = -\frac{n \ln p}{(\ln 2)^2}\)
哈希函数个数 k	\(k = \frac{m}{n} \ln 2\)

示例：100 万元素、1% 误判率 → m ≈ 958 万 bit（约 1.14 MB）、k ≈ 7。

布隆过滤器 vs 其他结构

graph TB
    subgraph BF["布隆过滤器 — 极致省空间"]
        B1["位数组 m bit"] --> B2["k 个哈希函数"]
        B2 --> B3["插入: O(k)"]
        B2 --> B4["查询: O(k)"]
        B2 --> B5["删除: ❌"]
        B2 --> B6["假阳性: 有"]
    end

    subgraph HS["HashSet — 精确但占空间"]
        HS1["存完整元素"] --> HS2["哈希表"]
        HS2 --> HS3["插入: O(1)"]
        HS2 --> HS4["查询: O(1)"]
        HS2 --> HS5["删除: ✅"]
        HS2 --> HS6["假阳性: 无"]
    end

    subgraph CBF["Counting Bloom — 可删除"]
        C1["计数器数组 4m bit"] --> C2["k 个哈希函数"]
        C2 --> C3["插入: O(k)"]
        C2 --> C4["查询: O(k)"]
        C2 --> C5["删除: ✅"]
        C2 --> C6["假阳性: 有"]
    end

    BF -.->|"约 4x 空间差"| CBF
    HS -.->|"约 4~10x 空间差"| BF

	布隆过滤器	HashSet	Counting Bloom Filter
空间	★★★★★ 极省	★★ 需存完整元素	★★★ 约为布隆 4x
查询	O(k)	O(1) 均摊	O(k)
插入	O(k)	O(1) 均摊	O(k)
删除	❌ 不支持	✅	✅
假阳性	有	无	有

---

💻 代码示例

基础实现

package bloom

import (
    "hash/fnv"
    "math"
)

type BloomFilter struct {
    bits []uint64    // 位数组，用 uint64 切片
    k    int         // 哈希函数个数
    m    uint        // 位数组总大小
}

// New 根据预期元素数和误判率创建布隆过滤器
func New(expectedItems uint, falsePositiveRate float64) *BloomFilter {
    m := optimalM(expectedItems, falsePositiveRate)
    k := optimalK(m, expectedItems)
    // 每个 uint64 有 64 个 bit
    size := (m + 63) / 64
    return &BloomFilter{
        bits: make([]uint64, size),
        k:    k,
        m:    m,
    }
}

func optimalM(n uint, p float64) uint {
    return uint(-float64(n) * math.Log(p) / (math.Ln2 * math.Ln2))
}

func optimalK(m, n uint) int {
    return int(math.Round(float64(m) / float64(n) * math.Ln2))
}

// Add 插入元素
func (bf *BloomFilter) Add(data []byte) {
    for i := 0; i < bf.k; i++ {
        pos := bf.hash(data, i)
        idx := pos / 64
        bit := pos % 64
        bf.bits[idx] |= 1 << bit
    }
}

// Contains 判断元素是否可能存在
func (bf *BloomFilter) Contains(data []byte) bool {
    for i := 0; i < bf.k; i++ {
        pos := bf.hash(data, i)
        idx := pos / 64
        bit := pos % 64
        if bf.bits[idx]&(1<<bit) == 0 {
            return false // 一定不存在
        }
    }
    return true // 可能存在
}

// hash 使用双重哈希技巧生成第 i 个哈希值
func (bf *BloomFilter) hash(data []byte, i int) uint {
    h1 := fnv.New32a()
    h1.Write(data)
    hash1 := h1.Sum32()

    h2 := fnv.New32()
    h2.Write(data)
    hash2 := h2.Sum32()

    // h_i(x) = h1(x) + i * h2(x)
    combined := uint(hash1) + uint(i)*uint(hash2)
    return combined % bf.m
}

使用示例：缓存穿透防护

sequenceDiagram
    participant C as 客户端
    participant BF as 布隆过滤器
    participant R as Redis
    participant DB as DB

    C->>BF: 查询 user:50
    BF-->>C: 一定不存在 ✗
    C-->>C: 直接返回，不查缓存/DB

    C->>BF: 查询 user:100
    BF-->>C: 可能存在 ✓
    C->>R: GET user:100
    alt 缓存命中
        R-->>C: 返回数据 ✅
    else 缓存 miss
        C->>DB: SELECT * FROM users WHERE id=100
        DB-->>C: 返回数据
        C->>R: SET user:100 + TTL
    end

package main

import (
    "fmt"
    "strconv"

    "github.com/bits-and-blooms/bloom/v3"
)

func main() {
    // 100万用户，1% 误判率
    filter := bloom.NewWithEstimates(1_000_000, 0.01)

    // 服务启动时：从 DB 加载所有合法用户 ID
    userIDs := []int64{1, 2, 3, 100, 200, 500, 999}
    for _, id := range userIDs {
        filter.AddString(strconv.FormatInt(id, 10))
    }

    // 查询时：先过布隆过滤器
    testIDs := []int64{1, 50, 100, 888, 999}
    for _, id := range testIDs {
        key := strconv.FormatInt(id, 10)
        if !filter.TestString(key) {
            fmt.Printf("用户 %d → 一定不存在，跳过 DB 查询\n", id)
        } else {
            fmt.Printf("用户 %d → 可能存在，继续查缓存/DB\n", id)
        }
    }
}

Redis 布隆过滤器

package main

import (
    "context"
    "fmt"

    "github.com/redis/go-redis/v9"
)

func main() {
    rdb := redis.NewClient(&redis.Options{Addr: "localhost:6379"})
    ctx := context.Background()

    // 创建布隆过滤器（需 RedisBloom 模块）
    rdb.Do(ctx, "BF.RESERVE", "users:filter", 0.01, 1_000_000)

    // 添加元素
    rdb.Do(ctx, "BF.ADD", "users:filter", "user:1001")

    // 批量添加
    rdb.Do(ctx, "BF.MADD", "users:filter", "user:1002", "user:1003", "user:1004")

    // 查询
    exists, _ := rdb.Do(ctx, "BF.EXISTS", "users:filter", "user:1001").Bool()
    fmt.Println("user:1001 exists:", exists) // true

    exists, _ = rdb.Do(ctx, "BF.EXISTS", "users:filter", "user:9999").Bool()
    fmt.Println("user:9999 exists:", exists) // 可能 false
}

---

⚠️ 常见陷阱

不支持删除

布隆过滤器无法删除元素——将位置 0 可能影响其他元素的判断。需要删除场景请用 Counting Bloom Filter（每 位改为计数器）或 Cuckoo Filter。

容量超出后误判率飙升

插入元素远超预期 n 时，假阳性率急剧上升。生产环境建议预留 20~30% 冗余，或使用 Scalable Bloom Filter 自动扩容。

哈希函数必须独立均匀

哈希函数质量差会导致分布不均匀、误判率高于理论值。推荐使用双重哈希（Double Hashing）或 MurmurHash3 系列。

跨语言/跨系统序列化

布隆过滤器的位数组直接序列化后，在另一端反序列化时必须使用**完全相同的 m、k、哈希函数**，否则查询结果无意义。

---

🏋️ 练习题

练习 1：1000 万元素、0.1% 误判率需要多少内存？几个哈希函数？

代入公式：m = -n·ln(p) / (ln2)² = -10⁷·ln(0.001) / (0.693)² ≈ 143.8M bit ≈ 17.1 MB，k = (m/n)·ln2 ≈ 10。

答案

位数组 m ≈ 1.438 亿 bit ≈ 17.1 MB，哈希函数 k ≈ 10 个。 相比 HashSet 存储 1000 万个 int64（约 76 MB），空间节省约 4.4x。

练习 2：为什么说布隆过滤器「删除一个元素」很危险？

删除需要把对应的 k 个位置零，但这些位可能被其他元素共享。置零后，其他本该"存在"的元素会变成"不存在"——产生了假阴性。

答案

布隆过滤器的多个元素共享 bit 位。删除元素 A 时把其 k 个位置 0，若元素 B 恰好也映射到其中某个位，B 的判断就会从"可能存在"变为"一定不存在"，违反了"无假阴性"的核心保证。解决方案：Counting Bloom Filter（4x 空间）、Cuckoo Filter（支持删除、空间更优）。

练习 3：Scalable Bloom Filter 如何解决容量超限问题？

SBF 在当前过滤器填满后，自动创建一个新的更大的布隆过滤器（容量按指数增长，误判率按比例收紧），查询时遍历所有子过滤器。总体误判率 = 各子过滤器误判率之积，渐进趋近于 0。

答案

SBF 维护一个布隆过滤器链：每个子过滤器容量递增、误判率递减。插入时写入当前活跃的过滤器；查询时遍历所有子过滤器，任一命中即返回"可能存在"。总体误判率是各子过滤器误判率的乘积，因此即使单个小过滤器误判率较高，整体仍可控。代价是查询时间随子过滤器数量线性增长。

---

🔗 相关链接

• Bloom Filter — Wikipedia — 原理与数学推导
• go-bloom 库 — Go 布隆过滤器实现
• RedisBloom 模块 — Redis 原生布隆过滤器
• Cuckoo Filter — 支持删除的替代方案