布隆过滤器

作者： /

什么是布隆过滤器

布隆过滤器（Bloom Filter）是 Burton Howard Bloom 在 1970 年提出的概率型数据结构，用极小的空间回答一个问题：”某个元素是否可能存在于集合中”。它允许假阳性（可能把不存在的元素判为存在），但绝不假阴性（存在的元素一定判为存在）。正是”可能误判但绝不会漏判”这个特性，让它在缓存穿透防护、URL 去重、数据库查询优化等场景大放异彩。

原理

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

  • 一个长度为 m 的位数组（初始全 0）；
  • k 个不同的哈希函数。

插入：用 k 个哈希函数算出 k 个位置，把位数组中这些位置全部置 1。查询：同样算出 k 个位置，只要有一个位置是 0，元素一定不存在；全部是 1 才认为”可能存在”——因为那 k 个 1 可能是别的元素置的（这就是假阳性来源）。

特性

  • ✅ 空间效率极高（远低于哈希表）；查询/插入都是 O(k)，与元素数量无关；
  • ❌ 有误判率；无法删除元素（除非用 Counting Bloom Filter 变种）。

参数设计

三个参数决定性能：n（预期元素数）、m（位数组长度）、k（哈希函数数）。给定期望误判率 p，最优参数为：

m = -(n * ln p) / (ln 2)²
k = (m / n) * ln 2

直觉：位数组越长误判越低；哈希函数太多会导致位很快被占满，太少则碰撞加剧，存在最优值。

Go 实现：bits-and-blooms/bloom

工程上直接用 github.com/bits-and-blooms/bloom/v3 即可。它的关键设计：

  • 自行实现的 MurmurHash3 变种，一次计算产出 4 个哈希值；
  • 用 unsafe 直接操作字节切片、内联位操作，完全避免堆分配；
  • NewWithEstimates(n, fp) 自动按期望元素数和误判率算出最优 m、k。
package main

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

func main() {
    // 预计 10000 个元素，误判率 0.01%
    filter := bloom.NewWithEstimates(10000, 0.0001)

    filter.Add([]byte("hello"))
    filter.Add([]byte("world"))

    fmt.Println(filter.Test([]byte("hello")))  // true
    fmt.Println(filter.Test([]byte("python"))) // false 或极小概率 true
    fmt.Printf("capacity=%d k=%dn", filter.Cap(), filter.K())
}

核心操作一览（源码逻辑）：

// Add：把 k 个位置置位
func (f *BloomFilter) Add(data []byte) *BloomFilter {
    h := baseHashes(data)
    for i := uint(0); i < f.k; i++ {
        f.b.Set(f.location(h, i))
    }
    return f
}

// Test：k 个位置必须全为 1
func (f *BloomFilter) Test(data []byte) bool {
    h := baseHashes(data)
    for i := uint(0); i < f.k; i++ {
        if !f.b.Test(f.location(h, i)) {
            return false
        }
    }
    return true
}

另外提供 TestOrAdd（原子地”查并加”）和 Merge（合并两个参数相同的过滤器）。

典型应用

// 1. 缓存穿透防护：不存在就直接挡掉，避免打穿到 DB
func getFromCache(key string) ([]byte, error) {
    if !filter.TestString(key) {
        return nil, ErrNotExist      // 肯定不存在，不必查缓存/DB
    }
    // 继续查缓存...
}

// 2. 爬虫 URL 去重
func shouldCrawl(url string) bool {
    if filter.TestString(url) { return false }
    filter.AddString(url)
    return true
}

工程建议

  • 参数自动估算：用 EstimateParameters(n, p) 或 NewWithEstimates，别手搓公式；
  • 内存参考：100 万元素、1% 误判率约需 1.14MB 和 7 个哈希函数；
  • 定位是前置过滤：误判只会导致”多查一次”，所以布隆过滤器应作为快速判断的前置条件，命中后仍需真实校验；
  • 并发：标准实现非并发安全，需用互斥锁包装，或每 goroutine 独立过滤器最后合并；
  • 扩展：数据量巨大用分片布隆过滤器；数据会增长用 Scalable Bloom Filter；需要删除用 Counting Bloom Filter。
滚动至顶部