内网监控系统之 Go 语言布隆过滤器算法深度剖析

package main
import (
    "fmt"
    "hash/fnv"
)
// BloomFilter 定义布隆过滤器结构体
type BloomFilter struct {
    bits   []bool // 二进制向量
    k      int    // 哈希函数的数量
    n      int    // 元素的数量
    m      int    // 二进制向量的长度
}
// NewBloomFilter 创建一个新的布隆过滤器
func NewBloomFilter(m, k int) *BloomFilter {
    return &BloomFilter{
        bits: make([]bool, m),
        k:    k,
        m:    m,
    }
}
// Add 向布隆过滤器中添加元素
func (bf *BloomFilter) Add(item []byte) {
    for i := 0; i < bf.k; i++ {
        hash := fnv.New32a()
        hash.Write([]byte(fmt.Sprintf("%d", i)))
        hash.Write(item)
        index := int(hash.Sum32()) % bf.m
        bf.bits[index] = true
    }
    bf.n++
}
// Contains 判断元素是否可能存在于布隆过滤器中
func (bf *BloomFilter) Contains(item []byte) bool {
    for i := 0; i < bf.k; i++ {
        hash := fnv.New32a()
        hash.Write([]byte(fmt.Sprintf("%d", i)))
        hash.Write(item)
        index := int(hash.Sum32()) % bf.m
        if!bf.bits[index] {
            return false
        }
    }
    return true
}
func main() {
    // 创建一个布隆过滤器，二进制向量长度为 1000，哈希函数数量为 3
    bf := NewBloomFilter(1000, 3)
    // 添加元素
    bf.Add([]byte("https://www.vipshare.com"))
    bf.Add([]byte("example.com"))
    // 判断元素是否存在
    fmt.Println(bf.Contains([]byte("https://www.vipshare.com"))) // 输出: true
    fmt.Println(bf.Contains([]byte("unknown.com")))               // 输出: false
}