布隆过滤器(go)：一个可能犯错但从不撒谎的内存大师

开场白：认识这位「内存魔法师」

想象一下，你是一个图书管理员，面对一个超级大图书馆，每天有成千上万的读者来问你：「《Go语言高级编程》这本书在不在？」。如果每次都要亲自跑到书架上找，你肯定会累得直不起腰。这时候，你需要一个聪明的助手——布隆过滤器。它虽然偶尔会「记错」（说有其实没有），但绝对不会「漏记」（说没有但其实有）。今天，我们就来揭开这位内存大师的神秘面纱！

布隆过滤器的基本原理：简单中的智慧

布隆过滤器本质上是一个位数组（bit array）和一系列哈希函数的组合。它的工作原理可以用一句话概括：来一个元素，多个哈希函数在数组上做标记；查一个元素，看所有标记位置是否都已被标记。

核心特点：

  • 可能误判，绝不会漏判：它说「有」可能是假的，但说「没有」一定是真的
  • 空间效率极高：用位数组存储，比传统数据结构节省大量内存
  • 查询速度快：O(k)的时间复杂度，k是哈希函数数量
  • 不存储原始数据：只能判断是否存在，不能获取或删除元素

数学基础

布隆过滤器有两个关键参数：

  • m：位数组大小（bit数）
  • k：哈希函数个数
  • n：预期插入元素数量
  • p：误判率

最优参数计算公式：

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

Go语言实现的布隆过滤器：源码解析

让我们来看看如何用Go语言实现一个兼容Google Guava的布隆过滤器。

1. 核心数据结构

// GuavaBloomFilter 兼容 Google Guava 的布隆过滤器
type GuavaBloomFilter struct {
    numBits          uint64 // 位数组总 bit 数
    numHashFunctions uint32 // 哈希函数个数 k
    bitArray         []byte // 位数组，按字节存储（与 Guava 一致）
}

这个结构体非常简洁，包含了布隆过滤器的三个核心组件：位数组大小、哈希函数个数和位数组本身。

2. 创建布隆过滤器

// NewWithParams 创建一个新的布隆过滤器
func NewWithParams(numItems uint, fpp float64) (*GuavaBloomFilter, error) {
    if numItems == 0 {
        return nil, errors.New("numItems must be > 0")
    }
    if fpp <= 0 || fpp >= 1 {
        return nil, errors.New("fpp must be in (0, 1)")
    }

    // 计算最优位数组大小 m
    m := math.Ceil(-float64(numItems) * math.Log(fpp) / (math.Ln2 * math.Ln2))
    if m <= 0 {
        m = 1
    }
    numBits := uint64(m)

    // 计算最优哈希函数个数 k
    k := math.Ceil(float64(numBits) / float64(numItems) * math.Ln2)
    numHashFunctions := uint32(k)
    if numHashFunctions < 1 {
        numHashFunctions = 1
    }
    if numHashFunctions > 255 {
        numHashFunctions = 255
    }

    byteLen := (numBits + 7) / 8
    bitArray := make([]byte, byteLen)

    return &GuavaBloomFilter{
        numBits:          numBits,
        numHashFunctions: numHashFunctions,
        bitArray:         bitArray,
    }, nil
}

这里实现了我们之前提到的数学公式，根据预期元素数量和误判率，计算出最优的位数组大小和哈希函数个数。

3. 插入元素

// Put 插入字节数组
func (b *GuavaBloomFilter) Put(data []byte) {
    if b.numBits == 0 {
        return
    }
    h1, h2 := murmur3.Sum128(data) // ✅ 正确获取两个 uint64

    for i := uint32(0); i < b.numHashFunctions; i++ {
        // 使用 uint64 运算避免负数
        combinedHash := h1 + uint64(i)*h2
        bitIndex := combinedHash % b.numBits

        byteIndex := bitIndex / 8
        bitOffset := bitIndex % 8
        b.bitArray[byteIndex] |= (1 << bitOffset)
    }
}

这个实现有两个亮点：

  1. 使用Murmur3哈希算法的128位输出，通过巧妙计算生成多个哈希值
  2. 位操作高效设置对应位置的bit值

4. 查询元素

// MightContain 判断是否存在
func (b *GuavaBloomFilter) MightContain(data []byte) bool {
    if b.numBits == 0 {
        return false
    }
    h1, h2 := murmur3.Sum128(data)

    for i := uint32(0); i < b.numHashFunctions; i++ {
        combinedHash := h1 + uint64(i)*h2
        bitIndex := combinedHash % b.numBits

        byteIndex := bitIndex / 8
        bitOffset := bitIndex % 8
        if b.bitArray[byteIndex]&(1<<bitOffset) == 0 {
            return false
        }
    }
    return true
}

查询逻辑很直观：只要有一个bit位没有被设置，就说明元素一定不存在；如果所有bit位都被设置，只能说元素可能存在。

性能测试结果：慢但值得的权衡

让我们看看测试结果：

BenchmarkBloomFilter_Insert-16          11654931               247.8 ns/op            16 B/op          1 allocs/op
BenchmarkHashMap_Insert-16               9406378               248.1 ns/op             0 B/op          0 allocs/op
BenchmarkBloomFilter_Lookup-16          17670654                69.81 ns/op           16 B/op          1 allocs/op
BenchmarkHashMap_Lookup-16              29366994                40.84 ns/op            0 B/op          0 allocs/op

布隆过滤器 vs 哈希表：性能对比分析

从测试结果看：

  • 插入速度：布隆过滤器和哈希表几乎相当（247.8 ns vs 248.1 ns）
  • 查询速度：布隆过滤器比哈希表慢约42%（69.81 ns vs 40.84 ns）
  • 内存分配：布隆过滤器每次操作分配16字节，哈希表没有额外分配

为什么慢但仍有价值？

  1. 空间效率的巨大优势：

    • 布隆过滤器用bit存储，而哈希表存储完整的键值对
    • 对于100万个元素，误判率0.1%，布隆过滤器只需要约1.4MB，而哈希表可能需要几十MB

  2. 「布隆过滤器+数据库」的黄金组合：

    • 对于不存在的元素，布隆过滤器可以在毫秒级拒绝查询
    • 这可以将数据库查询量减少90%以上，大大减轻数据库压力

  3. 预过滤的价值：

    • 布隆过滤器的"慢"是相对于哈希表的单次操作而言
    • 但在实际应用中，它可以避免更昂贵的操作（如磁盘IO、网络请求）

  4. 大数据量场景的性价比：

    • 数据量越大，布隆过滤器的内存优势越明显
    • 百万级元素的布隆过滤器可能只占用几MB内存

实际应用场景：布隆过滤器的高光时刻

1. 缓存穿透防御

缓存穿透是指查询一个根本不存在的数据，导致请求直接打到数据库。布隆过滤器可以完美解决：

func GetUserByID(id string) (User, error) {
    // 先查布隆过滤器，判断ID是否可能存在
    if !bloomFilter.MightContainString(id) {
        return nil, errors.New("用户不存在") // 直接返回，保护数据库
    }
    
    // 再查缓存
    user, found := cache.Get(id)
    if found {
        return user, nil
    }
    
    // 最后查数据库
    user, err := db.GetUser(id)
    // ...
}

2. 爬虫URL去重

互联网爬虫需要记录已爬取的URL，避免重复爬取：

  • 用哈希表存储：10亿URL需要几百GB内存
  • 用布隆过滤器：同样数据量可能只需要几GB

3. 分布式系统中的成员判断

在分布式系统中，判断一个元素是否属于某个集合是常见需求：

  • Redis中的布隆过滤器插件
  • HBase中用于快速判断数据是否可能在某个Region
  • Cassandra中用于减少不必要的磁盘查找

4. 垃圾邮件过滤

判断一个邮件地址是否在黑名单中，布隆过滤器可以高效处理百万级黑名单。

结语：选择合适的工具

布隆过滤器就像一把瑞士军刀，虽然不是万能的，但在特定场景下能发挥巨大价值。它用一点误判率的代价，换取了极高的空间效率和不错的时间效率。

记住布隆过滤器的黄金法则：它说「没有」的时候，你可以完全相信；它说「有」的时候，你需要进一步确认。

下次当你面临大数据量的存在性检查问题时，不妨考虑一下这位「可能犯错但从不撒谎的内存大师」！

所有源码

// bloom.go
package main

import (
    "encoding/binary"
    "errors"
    "io"
    "math"

    "github.com/spaolacci/murmur3"
)

// GuavaBloomFilter 兼容 Google Guava 的布隆过滤器
type GuavaBloomFilter struct {
    numBits          uint64 // 位数组总 bit 数
    numHashFunctions uint32 // 哈希函数个数 k
    bitArray         []byte // 位数组，按字节存储（与 Guava 一致）
}

// NewWithParams 创建一个新的布隆过滤器
func NewWithParams(numItems uint, fpp float64) (*GuavaBloomFilter, error) {
    if numItems == 0 {
        return nil, errors.New("numItems must be > 0")
    }
    if fpp <= 0 || fpp >= 1 {
        return nil, errors.New("fpp must be in (0, 1)")
    }

    // 计算最优位数组大小 m
    m := math.Ceil(-float64(numItems) * math.Log(fpp) / (math.Ln2 * math.Ln2))
    if m <= 0 {
        m = 1
    }
    numBits := uint64(m)

    // 计算最优哈希函数个数 k
    k := math.Ceil(float64(numBits) / float64(numItems) * math.Ln2)
    numHashFunctions := uint32(k)
    if numHashFunctions < 1 {
        numHashFunctions = 1
    }
    if numHashFunctions > 255 {
        numHashFunctions = 255
    }

    byteLen := (numBits + 7) / 8
    bitArray := make([]byte, byteLen)

    return &GuavaBloomFilter{
        numBits:          numBits,
        numHashFunctions: numHashFunctions,
        bitArray:         bitArray,
    }, nil
}

// NewGuavaBloomFilterFromReader 从 io.Reader 读取 Guava 布隆过滤器
func NewGuavaBloomFilterFromReader(r io.Reader) (*GuavaBloomFilter, error) {
    var version int32
    if err := binary.Read(r, binary.BigEndian, &version); err != nil {
        return nil, err
    }
    if version != 1 {
        return nil, errors.New("unsupported bloom filter version: only version 1 is supported")
    }

    var numBits int64
    if err := binary.Read(r, binary.BigEndian, &numBits); err != nil {
        return nil, err
    }
    if numBits <= 0 || numBits > 1<<40 { // 防止过大分配
        return nil, errors.New("invalid numBits")
    }

    var numHashFunctions int32
    if err := binary.Read(r, binary.BigEndian, &numHashFunctions); err != nil {
        return nil, err
    }
    if numHashFunctions <= 0 || numHashFunctions > 255 {
        return nil, errors.New("invalid numHashFunctions")
    }

    byteLen := (numBits + 7) / 8
    bitArray := make([]byte, byteLen)
    if _, err := io.ReadFull(r, bitArray); err != nil {
        return nil, err
    }

    return &GuavaBloomFilter{
        numBits:          uint64(numBits),
        numHashFunctions: uint32(numHashFunctions),
        bitArray:         bitArray,
    }, nil
}

// Put 插入字节数组
func (b *GuavaBloomFilter) Put(data []byte) {
    if b.numBits == 0 {
        return
    }
    h1, h2 := murmur3.Sum128(data) 

    for i := uint32(0); i < b.numHashFunctions; i++ {
        // 使用 uint64 运算避免负数
        combinedHash := h1 + uint64(i)*h2
        bitIndex := combinedHash % b.numBits

        byteIndex := bitIndex / 8
        bitOffset := bitIndex % 8
        b.bitArray[byteIndex] |= (1 << bitOffset)
    }
}

// PutString 插入字符串
func (b *GuavaBloomFilter) PutString(s string) {
    b.Put([]byte(s)) // 分配不可避免，但清晰
}

// MightContain 判断是否存在
func (b *GuavaBloomFilter) MightContain(data []byte) bool {
    if b.numBits == 0 {
        return false
    }
    h1, h2 := murmur3.Sum128(data)

    for i := uint32(0); i < b.numHashFunctions; i++ {
        combinedHash := h1 + uint64(i)*h2
        bitIndex := combinedHash % b.numBits

        byteIndex := bitIndex / 8
        bitOffset := bitIndex % 8
        if b.bitArray[byteIndex]&(1<<bitOffset) == 0 {
            return false
        }
    }
    return true
}

// MightContainString 判断字符串是否存在
func (b *GuavaBloomFilter) MightContainString(s string) bool {
    return b.MightContain([]byte(s))
}

// WriteTo 序列化到 io.Writer（Guava 兼容）
func (b *GuavaBloomFilter) WriteTo(w io.Writer) error {
    if err := binary.Write(w, binary.BigEndian, int32(1)); err != nil {
        return err
    }
    if err := binary.Write(w, binary.BigEndian, int64(b.numBits)); err != nil {
        return err
    }
    if err := binary.Write(w, binary.BigEndian, int32(b.numHashFunctions)); err != nil {
        return err
    }
    _, err := w.Write(b.bitArray)
    return err
}


package main

func main() {
    // 创建新布隆：10万条，误判率0.1%
    bloom, err := NewWithParams(100_000, 0.001)
    if err != nil {
        panic(err)
    }

    // 插入数据
    bloom.PutString("13800138000")
    bloom.PutString("13912345678")

    // 验证
    println("13800138000 in bloom?", bloom.MightContainString("13800138000"))
    println("13900000000 in bloom?", bloom.MightContainString("13900000000"))

    // 序列化为 Guava 兼容文件
    // file, _ := os.Create("from_go.bloom")
    // defer file.Close()
    // bloom.WriteTo(file)

    // println("Wrote Guava-compatible bloom filter to from_go.bloom")
}


// bloom_test.go
package main

import (
    "bytes"
    "math/rand"
    "testing"
)

// 生成随机字符串用于测试
func randomStrings(n int, length int) []string {
    rand.Seed(42) // 固定种子，保证可重复
    strs := make([]string, n)
    for i := 0; i < n; i++ {
        b := make([]byte, length)
        for j := 0; j < length; j++ {
            b[j] = byte(97 + rand.Intn(26)) // a-z
        }
        strs[i] = string(b)
    }
    return strs
}

// ========================================
// 单元测试
// ========================================

func TestNewWithParams(t *testing.T) {
    bloom, err := NewWithParams(1000, 0.01)
    if err != nil {
        t.Fatalf("NewWithParams failed: %v", err)
    }
    if bloom.numBits == 0 {
        t.Error("numBits should be > 0")
    }
    if bloom.numHashFunctions == 0 {
        t.Error("numHashFunctions should be > 0")
    }
    if len(bloom.bitArray) == 0 {
        t.Error("bitArray should not be empty")
    }
}

func TestPutAndMightContain(t *testing.T) {
    bloom, _ := NewWithParams(100, 0.001)

    key := "hello"
    bloom.PutString(key)

    if !bloom.MightContainString(key) {
        t.Errorf("Expected %s to be in bloom", key)
    }

    if bloom.MightContainString("nonexistent") {
        t.Error("False positive on empty key (unexpected at this scale, but possible; still, test known negative)")
    }
}

func TestSerializationRoundTrip(t *testing.T) {
    // 创建并插入数据
    bloom1, _ := NewWithParams(1000, 0.01)
    keys := []string{"apple", "banana", "cherry", "date"}
    for _, k := range keys {
        bloom1.PutString(k)
    }

    // 序列化到 buffer
    var buf bytes.Buffer
    err := bloom1.WriteTo(&buf)
    if err != nil {
        t.Fatalf("WriteTo failed: %v", err)
    }

    // 从 buffer 反序列化
    bloom2, err := NewGuavaBloomFilterFromReader(&buf)
    if err != nil {
        t.Fatalf("ReadFrom failed: %v", err)
    }

    // 验证参数一致
    if bloom1.numBits != bloom2.numBits ||
        bloom1.numHashFunctions != bloom2.numHashFunctions {
        t.Error("Parameters mismatch after round-trip")
    }

    // 验证内容一致
    for _, k := range keys {
        if !bloom2.MightContainString(k) {
            t.Errorf("Key %s missing after deserialization", k)
        }
    }
}

func TestEdgeCases(t *testing.T) {
    // 空字符串
    bloom, _ := NewWithParams(10, 0.1)
    bloom.PutString("")
    if !bloom.MightContainString("") {
        t.Error("Empty string not found")
    }

    // 超长字符串
    long := make([]byte, 10000)
    for i := range long {
        long[i] = byte(i % 256)
    }
    bloom.Put(long)
    if !bloom.MightContain(long) {
        t.Error("Long byte array not found")
    }
}

// ========================================
// 性能与内存对比测试
// ========================================

// BenchmarkBloomFilter_Insert 查询布隆插入性能
func BenchmarkBloomFilter_Insert(b *testing.B) {
    bloom, _ := NewWithParams(uint(b.N), 0.01)
    keys := randomStrings(b.N, 10)

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        bloom.PutString(keys[i])
    }
}

// BenchmarkHashMap_Insert 对比 Go map 插入性能
func BenchmarkHashMap_Insert(b *testing.B) {
    m := make(map[string]struct{}, b.N)
    keys := randomStrings(b.N, 10)

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        m[keys[i]] = struct{}{}
    }
}

// BenchmarkBloomFilter_Lookup 布隆查询性能
func BenchmarkBloomFilter_Lookup(b *testing.B) {
    bloom, _ := NewWithParams(100000, 0.01)
    keys := randomStrings(100000, 10)
    for _, k := range keys {
        bloom.PutString(k)
    }
    queryKeys := randomStrings(b.N, 10)

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        bloom.MightContainString(queryKeys[i%len(queryKeys)])
    }
}

// BenchmarkHashMap_Lookup map 查询性能
func BenchmarkHashMap_Lookup(b *testing.B) {
    m := make(map[string]struct{})
    keys := randomStrings(100000, 10)
    for _, k := range keys {
        m[k] = struct{}{}
    }
    queryKeys := randomStrings(b.N, 10)

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _, _ = m[queryKeys[i%len(queryKeys)]]
    }
}

往期部分文章列表

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容