golang,go,博客,开源,编程

golang每日一库之bits-and-blooms/bloom

Published on with 0 views and 0 comments

github.com/bits-and-blooms/bloom 是 Go 语言中的 布隆过滤器（Bloom Filter） 实现。布隆过滤器是一种 高效的概率型数据结构，用于快速判断某个元素是否存在于一个集合中，具有 节省空间 和 高效查询 的特点，广泛应用于 去重、缓存、黑名单检测等场景。

1. 安装

使用 go get 下载安装：

go get github.com/bits-and-blooms/bloom

然后在代码中导入：

import "github.com/bits-and-blooms/bloom"

2. 布隆过滤器原理

布隆过滤器使用 多个哈希函数 将元素映射到一个 位数组（bit array） 中：

  • 插入数据：使用多个哈希函数计算索引，并将对应的位设为 1。
  • 查询数据：检查所有哈希索引位置是否都为 1，如果存在 0，则该元素一定 不在集合中，否则可能 在集合中（但可能存在误判）。
  • 误判率：布隆过滤器 不会产生假阴性（False Negative），但会有** 假阳性（False Positive）**。

3. 使用示例

3.1 创建布隆过滤器

package main

import (
	"fmt"

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

func main() {
	// 创建一个布隆过滤器，使用 1000 个 bit 位，3 个哈希函数
	filter := bloom.New(1000, 3)

	// 添加数据
	filter.Add([]byte("hello"))
	filter.Add([]byte("world"))

	// 查询数据
	fmt.Println(filter.Test([]byte("hello"))) // true
	fmt.Println(filter.Test([]byte("world"))) // true
	fmt.Println(filter.Test([]byte("golang"))) // false（一定正确）
}

代码解析：

  • bloom.New(size, hashCount)：创建一个布隆过滤器，size 是位数组大小，hashCount 是哈希函数个数。
  • filter.Add(data)：向布隆过滤器中添加数据。
  • filter.Test(data)：测试数据是否可能在过滤器中。

4. 高级用法

4.1 从二进制数据创建布隆过滤器

// 从 byte 数组加载布隆过滤器状态
data := []byte{0, 1, 0, 1} // 示例数据
filter := bloom.NewWithBytes(1000, 3, data)

4.2 计算误判率

可以调整 哈希函数个数（k） 和 位数组大小（m） 来优化误判率：

n := uint(1000)  // 预期存储的元素个数
p := 0.01        // 误判率
m := bloom.EstimateParameters(n, p) // 计算最佳位数组大小
fmt.Println(m) // 输出建议的位数组大小

5. 适用场景

  1. 防止缓存穿透
    • 在 Redis/Memcached 之前使用布隆过滤器，拦截无效查询，减少数据库压力。
  2. 黑名单检测
    • 例如：垃圾邮件过滤、恶意 IP 检测、爬虫屏蔽。
  3. 去重
    • 例如：检测 URL 是否已被访问，防止重复抓取。
  4. 搜索引擎
    • 记录已索引的网页，避免重复爬取。

6. 其他布隆过滤器实现

库线程安全泛型支持误判率调整备注
bits-and-blooms/bloom❌❌✅高性能但不支持并发
willf/bloom✅❌✅线程安全，适用于并发环境

7. 总结

  • github.com/bits-and-blooms/bloom 是 Go 语言中 轻量级、高性能 的布隆过滤器实现。
  • 适用于 去重、缓存防穿透、黑名单检测 等场景。
  • 不适用于需要删除元素的情况（标准布隆过滤器不支持删除）。
  • 适用于 单线程环境，如果需要 线程安全，可以考虑 willf/bloom。
标题：golang每日一库之bits-and-blooms/bloom
作者：mooncakeee
地址：http://blog.dd95828.com/articles/2025/03/08/1741445343478.html
联系：scotttu@163.com
↑ ↓