2025-02-26 分类：performance 作者：admin 阅读（31）
布隆过滤器（Bloom Filter）是一种高效的概率数据结构，用于判断一个元素是否属于某个集合。它可能存在误报（即判断元素存在时，实际上可能不存在），但不会漏报（即判断元素不存在时，一定不存在）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
package main import ( "fmt" "hash/fnv" "math" ) // BloomFilter 布隆过滤器结构 type BloomFilter struct { size uint // 位数组大小 hashCount uint // 哈希函数数量 bitArray []bool // 位数组 hashFuncs []hashFunc // 哈希函数列表 } // hashFunc 哈希函数类型 type hashFunc func([]byte) uint // NewBloomFilter 创建一个新的布隆过滤器 func NewBloomFilter(size uint, hashCount uint) *BloomFilter { bf := &BloomFilter{ size: size, hashCount: hashCount, bitArray: make([]bool, size), hashFuncs: make([]hashFunc, hashCount), } // 初始化哈希函数 for i := uint(0); i < hashCount; i++ { bf.hashFuncs[i] = createHashFunc(i) } return bf } // createHashFunc 创建哈希函数 func createHashFunc(seed uint) hashFunc { return func(data []byte) uint { h := fnv.New32a() h.Write(data) return uint(h.Sum32()) + seed } } // Add 添加元素到布隆过滤器 func (bf *BloomFilter) Add(item []byte) { for _, hashFunc := range bf.hashFuncs { index := hashFunc(item) % bf.size bf.bitArray[index] = true } } // Contains 检查元素是否可能存在于布隆过滤器中 func (bf *BloomFilter) Contains(item []byte) bool { for _, hashFunc := range bf.hashFuncs { index := hashFunc(item) % bf.size if !bf.bitArray[index] { return false } } return true } // OptimalHashCount 计算最优的哈希函数数量 func OptimalHashCount(size uint, expectedElements uint) uint { return uint(math.Ceil(float64(size) / float64(expectedElements) * math.Log(2))) } // OptimalSize 计算最优的位数组大小 func OptimalSize(expectedElements uint, falsePositiveRate float64) uint { return uint(math.Ceil(-float64(expectedElements) * math.Log(falsePositiveRate) / math.Pow(math.Log(2), 2))) } func main() { // 预期元素数量和误报率 expectedElements := uint(1000) falsePositiveRate := 0.01 // 计算最优的位数组大小和哈希函数数量 size := OptimalSize(expectedElements, falsePositiveRate) hashCount := OptimalHashCount(size, expectedElements) // 创建布隆过滤器 bf := NewBloomFilter(size, hashCount) // 添加元素 bf.Add([]byte("hello")) bf.Add([]byte("world")) // 检查元素是否存在 fmt.Println(bf.Contains([]byte("hello"))) // true fmt.Println(bf.Contains([]byte("world"))) // true fmt.Println(bf.Contains([]byte("foo"))) // false (可能误报) } |
true 但实际上元素不存在）。需要在程序启动时将数据加载到布隆过滤器中，可以在初始化布隆过滤器后，遍历数据并将其逐个添加到布隆过滤器中。
| 特性 | 布隆过滤器 | Go 语言 map |
|---|---|---|
| 内存占用 | 极低（位数组） | 较高（存储键值对） |
| 查询速度 | O(k)（k 是哈希函数数量） | O(1)（平均情况） |
| 误报率 | 可能存在误报 | 无误报 |
| 支持删除 | 不支持（除非使用变种） | 支持 |
| 适用场景 | 大规模数据、允许误报的场景 | 需要精确查询和存储的场景 |
map：
map 或数据库索引可能更合适。map 低很多。「三年博客，如果觉得我的文章对您有用，请帮助本站成长」
上一篇：依赖倒置原则（Dependency Inversion Principle DIP）
下一篇：git rebase 变基
分别用不同厚度的筏板定义，画图后这设置筏板变截面处理。 http://f.fwxgx.co...
评：新文章！分别用不同厚度的筏板定义，画图后这设置筏板变截面处理。 http://f.fwxgx.co...
评：新文章！新增一个框架图！ http://biji.jinli.vip/wp-content/upl...
评：新文章！嗨，这是一条评论。 要开始审核、编辑及删除评论，请访问仪表盘的“评论”页面。 评论者头像来自...
评：世界，您好！
共有 0 - 布隆过滤器（Bloom Filter）