中文
devexamples

Bloom Filter Probabilistic Membership (Go)

Implement a Go bloom filter with k hash functions for probabilistic membership testing.

GoData Integrity

Code

snippet
package main

import "hash/fnv"

type BloomFilter struct {
	bits []byte
	size int
	k    int
}

func newBloom(size, k int) *BloomFilter { return &BloomFilter{bits: make([]byte, size), size: size, k: k} }

func (bf *BloomFilter) hash(item string, seed int) int {
	h := fnv.New32a()
	h.Write([]byte{byte(seed)})
	h.Write([]byte(item))
	return int(h.Sum32()) % bf.size
}

func (bf *BloomFilter) Add(item string) { for i := 0; i < bf.k; i++ { bf.bits[bf.hash(item, i+1)] = 1 } }
func (bf *BloomFilter) Contains(item string) bool { for i := 0; i < bf.k; i++ { if bf.bits[bf.hash(item, i+1)] == 0 { return false } }; return true }

Related Examples