bloomfilter

README

This is a basic Go implementation of a Bloom filter. I built it to test the
idea from Kirsch and Mitzenmacher [1] that you can use two hash functions to
simulate an arbitrary number of additional hash functions without losing
functionality in a Bloom filter. Cool result: they're right!

It is very short code, see tests and comments for more details.

```
set := bloomfilter.NewBloomFilter(1000000, 8192) // elements, false positive rate
set.Add([]byte("Hello, world!"))
set.Check([]byte("Hello, world!")) // => true
set.Check([]byte("String Not-appearing-in-this-set")) // => false
```

[1] http://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf

Documentation

Index

• type BloomFilter
  • func NewBloomFilter(capacity, probability int) *BloomFilter
  • func (set *BloomFilter) Add(input []byte)
  • func (set *BloomFilter) Check(input []byte) bool

Types

type BloomFilter

type BloomFilter struct {
	Capacity          int   // n
	FalsePositiveRate int   // p
	NumHashes         int   // k
	BitSize           int64 // m
	// contains filtered or unexported fields
}

func NewBloomFilter

func NewBloomFilter(capacity, probability int) *BloomFilter

Returns a new Bloom filter. Parameters are the expected number of elements in the set and the desired false positive probability. Optimal size and number of hashes are calculated based on these numbers.

p = false positive rate of the form 1/p, powers of two preferred optimal number of hashes k = (m/n)ln(2)

func (*BloomFilter) Add

func (set *BloomFilter) Add(input []byte)

Adds a piece of arbitrary data to the set

func (*BloomFilter) Check

func (set *BloomFilter) Check(input []byte) bool

Checks the set for a piece of arbitrary data