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 ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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.
Source Files