package main
import (
"fmt"
"github.com/go-redis/redis/v8"
"github.com/willf/bitset"
)
// 定义布隆过滤器结构体
type BloomFilter struct {
redisClient *redis.Client // Redis客户端
keyPrefix string // Redis键的前缀
bitSets []*bitset.BitSet
bitSetCount int // 位集数量
hashCount int // 哈希函数数量
}
// 初始化布隆过滤器
func NewBloomFilter(redisClient *redis.Client, keyPrefix string, size, hashCount int) *BloomFilter {
return &BloomFilter{
redisClient: redisClient,
keyPrefix: keyPrefix,
bitSetCount: size,
hashCount: hashCount,
}
}
// 添加元素到布隆过滤器
func (bf *BloomFilter) Add(key string) error {
for i := 0; i < bf.bitSetCount; i++ {
bitSetKey := fmt.Sprintf("%s:%d", bf.keyPrefix, i)
for _, hash := range bf.hashes(key) {
if err := bf.redisClient.SetBit(bf.ctx(), bitSetKey, hash, 1).Err(); err != nil {
return err
}
}
}
return nil
}
// 检查元素是否可能存在于布隆过滤器
func (bf *BloomFilter) Exists(key string) (bool, error) {
for i := 0; i < bf.bitSetCount; i++ {
bitSetKey := fmt.Sprintf("%s:%d", bf.keyPrefix, i)
var allBitsSet bool
for _, hash := range bf.hashes(key) {
bit, err := bf.redisClient.GetBit(bf.ctx(), bitSetKey, hash).Result()
if err != nil || bit == 0 {
allBitsSet = false
break
}
allBitsSet = true
}
if !allBitsSet {
return false, nil
}
}
return true, nil
}
// 哈希函数集合
func (bf *BloomFilter) hashes(key string) []uint64 {
var hashes []uint64
for i := 0; i < bf.hashCount; i++ {
hash := fnv64(key)
hashes = append(hashes, hash)
}
return hashes
}
// FNV-1a哈希函数
func fnv64(key string) uint64 {
hash := uint64(14695981039346656037)
for i := 0; i < len(key); i++ {
hash ^= uint64(key[i])
hash *= uint64(1099511628211)
}
return hash
}
func (bf *BloomFilter) ctx() *redis.Context {
return bf.redisClient.Context()
}
func main() {
// 假设已经设置了Redis客户端和其他参数
redisClient := redis.NewClient(&redis.Options{})
keyPrefix := "myBloomFilter"
size := 10
hashCount := 10
bf := NewBloomFilter(redisClient, keyPrefix, size, hashCount)
// 添加元素
bf.Add("someKey")
// 检查元素是否存在
exists, err := bf.Exists("someKey")
if err != nil {
panic(err)
}
fmt.Printf