bloom

README

bloom

A simple bloom filter written in Go.

A Bloom filter is a probabilistic data structure for set membership that trades accuracy for space. When queried for membership of a key a Bloom filter returns false if the key is definitely not in the set else it returns true which mean the key might be in the set.

This implementation of a Bloom filter uses a combination of the murmur3 and fnv1 hashing to calculate which bits to set.

API

Create new Bloom filter

A new BloomFilter is created using the NewBloomFilter function, parameterized by:

• maxSize - the maximum number of elements expected in the set.
• maxTolerance - the expected accuracy (a sensible default is 0.01).
• seed - the seed to use for the murmer hash function.

A error is returned if maxSize is set to 0 or the number of bits is needed in the backing bit set is larger than a uint32.

bloom, err = NewBloomFilter(1000, 0.01, 42)

Insert

Insert a new key into the bloom filter using Insert.

bloom.Insert([2,3,23,200])

Contains

Check if the key is contained in the set using Contains.

bloom.Contains([23,89,205,148])

Tests

The tests can be invoked with go test

License

MIT © Oliver Daff

Documentation

Overview

Package bloom is an implementation of Bloom filter.

Index

• type BloomFilter
  • func NewBloomFilter(maxSize uint32, maxTolerance float64, seed uint32) (*BloomFilter, error)
  • func (bf *BloomFilter) Contains(key []byte) bool
  • func (bf *BloomFilter) FalsePositiveProbability() float64
  • func (bf *BloomFilter) Insert(key []byte)

Types

type BloomFilter

type BloomFilter struct {
	// contains filtered or unexported fields
}

BloomFilter is a datastructure to tell if a element is present in a set. The BloomFilter trades accuracy for space. The contains method returns false if the element is definitely not present but true if the element might be in the set.

func NewBloomFilter

func NewBloomFilter(maxSize uint32, maxTolerance float64, seed uint32) (*BloomFilter, error)

NewBloomFilter allocates a new BloomFilter parameterised by the arguments.

maxSize - the maximum number of elements the filter is expected to hold (must be > 0)
maxTolerance - the expected accuracy (a sensible default is 0.01)
seed - the seed to use for hashFunctions.

func (*BloomFilter) Contains

func (bf *BloomFilter) Contains(key []byte) bool

Contains returns false if the key is definitely not contained in the set else returns true if the key might be in the set.

func (*BloomFilter) FalsePositiveProbability

func (bf *BloomFilter) FalsePositiveProbability() float64

FalsePositiveProbability returns the probability of a false positive being returned by BloomFilter.

func (*BloomFilter) Insert

func (bf *BloomFilter) Insert(key []byte)

Insert adds the key to the set in the BloomFilter.