Ween's Blog

/home

/posts

/categories

布隆过滤器算法实现

  ·   1 min read

实现原理 #

布隆过滤器由一个位数组（bit array）和多个哈希函数（hash functions）组成。其工作原理如下：

  1. 初始化：
    • 创建一个长度为 m 的位数组，将所有位初始化为 0。
    • 选择 k 个独立的哈希函数，每个哈希函数将输入映射到 [0, m-1] 范围内的一个位置。
  2. 插入元素：
    • 对于要插入的元素，通过 k 个哈希函数分别计算出 k 个哈希值。
    • 将位数组中这 k 个位置的值设置为 1。
  3. 查询元素：
    • 对于要查询的元素，通过 k 个哈希函数分别计算出 k 个哈希值。
    • 检查位数组中这 k 个位置的值，如果所有位置的值都为 1，则认为该元素可能在集合中；如果有任何一个位置的值为 0，则认为该元素不在集合中。

image-2025228218354.png

代码实现 # 
package bloomfilter

import (
	"hash/fnv"
	"math"
)

type BloomFilter struct {
	bitset []bool //比特数组
	m      int    //比特数组长度
	k      int    //哈希函数数量
}

func NewBloomFilter(n int, p float64) *BloomFilter {
	m := int(math.Ceil(float64(-n) * math.Log(p) / math.Pow(math.Log(2), 2)))
	k := int(math.Ceil(math.Log(2) * float64(m) / float64(n)))
	return &BloomFilter{
		bitset: make([]bool, m),
		m:      m,
		k:      k,
	}
}

// 哈希函数
func (bf *BloomFilter) hash(data []byte, seed uint32) int {
	h := fnv.New32a()
	h.Write(data)
	hash := h.Sum32()
	return int((hash + seed) % uint32(bf.m))
}

// 添加元素
func (bf *BloomFilter) Add(item string) {
	for i := 0; i < bf.k; i++ {
		pos := bf.hash([]byte(item), uint32(i))
		bf.bitset[pos] = true
	}
}

// 查找元素
func (bf *BloomFilter) Contains(item string) bool {
	for i := 0; i < bf.k; i++ {
		pos := bf.hash([]byte(item), uint32(i))
		if !bf.bitset[pos] {
			return false
		}
	}
	return true
}
←
区块链相关定义和概念
实现redis客户端一致性哈希分片
→
back to top