Bloom Filter

medium · probabilistic, hashing

Bloom Filter

Implement a Bloom filter that supports membership checks with possible false positives.

A Bloom filter is a bitset plus k hash functions. To add a value, hash it k times and set those bit positions. To test membership, check that all positions are set.

API

type BloomFilter struct { /* ... */ }

func NewBloomFilter(size int, k int) *BloomFilter
func (bf *BloomFilter) Add(value string)
func (bf *BloomFilter) Contains(value string) bool

Example

bf := NewBloomFilter(128, 3)
bf.Add("apple")
Contains("apple") == true

Notes

Contains may return true for values never added (false positives).
Use the provided hash64 helper (or your own) to generate hashes.

package solution

// BloomFilter supports membership checks with possible false positives.
type BloomFilter struct {
	size int
	k    int
	bits []bool
}

// NewBloomFilter creates a Bloom filter with the given bitset size and k hashes.
func NewBloomFilter(size int, k int) *BloomFilter {
	// TODO: initialize fields
	return &BloomFilter{}
}

// Add inserts a value into the filter.
func (bf *BloomFilter) Add(value string) {
	// TODO: set k hash positions
}

// Contains returns true if the value may be present.
func (bf *BloomFilter) Contains(value string) bool {
	// TODO: check all k positions
	return false
}

// hash64 returns a 64-bit FNV-1a hash seeded with the provided value.
func hash64(s string, seed uint64) uint64 {
	const offset64 = 1469598103934665603
	const prime64 = 1099511628211

h := offset64 ^ seed
	for i := 0; i < len(s); i++ {
		h ^= uint64(s[i])
		h *= prime64
	}
	return h
}

// positions returns k bit positions for value.
func positions(value string, size int, k int) []int {
	pos := make([]int, k)
	for i := 0; i < k; i++ {
		h := hash64(value, uint64(0x9e3779b97f4a7c15*uint64(i+1)))
		pos[i] = int(h % uint64(size))
	}
	return pos
}