Bloom Filters

A basic / generic and/or concurrent Bloom filter implementation in Go.

Installation

go get github.com/daanv2/go-bloom-filters

Features

• Standard Bloom filter — basic, high-performance implementation
• Concurrent Bloom filter — safe for concurrent reads and writes using a spinlock
• Generic wrapper — use any type with a custom serializer via GenericBloomFilter[T]
• Configurable hash functions — ships with FNV, CRC-64, SHA, and MD5; bring your own with WithHashFunctions
• Functional options — clean builder pattern with WithSize, WithDefaultHashFunctions, etc.

Quick Start

package main

import (
	"fmt"

	bloomfilters "github.com/daanv2/go-bloom-filters"
)

func main() {
	bf, err := bloomfilters.NewBloomFilter(
		bloomfilters.WithSize(1024),
		bloomfilters.WithDefaultHashFunctions(),
	)
	if err != nil {
		panic(err)
	}

	bf.Add([]byte("hello"))
	bf.Add([]byte("world"))

	fmt.Println(bf.Test([]byte("hello"))) // true
	fmt.Println(bf.Test([]byte("world"))) // true
	fmt.Println(bf.Test([]byte("foo")))   // false (probably)
}

Concurrent Bloom Filter

bf, err := bloomfilters.NewConcurrentBloomFilter(
	bloomfilters.WithSize(1024),
	bloomfilters.WithDefaultHashFunctions(),
)
if err != nil {
	panic(err)
}

// Safe to call Add / Test from multiple goroutines
bf.Add([]byte("hello"))
fmt.Println(bf.Test([]byte("hello"))) // true

Generic Bloom Filter

Wrap any IBloomFilter to work with a custom type:

bf, _ := bloomfilters.NewBloomFilter(
	bloomfilters.WithSize(1024),
	bloomfilters.WithDefaultHashFunctions(),
)

sbf := bloomfilters.NewGenericBloomFilter(bf, func(s string) []byte {
	return []byte(s)
})

sbf.Add("hello")
fmt.Println(sbf.Test("hello")) // true

Bloom Settings

The pkg/bloomsettings package provides helper functions for tuning your filter:

• OptimalHashFunctions(m, n) — returns the optimal number of hash functions for m bits and n expected elements
• FalsePositiveRate(m, n, k) — calculates the expected false-positive rate for m bits, n elements, and k hash functions

import "github.com/daanv2/go-bloom-filters/pkg/bloomsettings"

k := bloomsettings.OptimalHashFunctions(1024, 100)   // optimal k
fp := bloomsettings.FalsePositiveRate(1024, 100, k)   // expected false-positive rate