README
¶
go-bloom is a collection of bloom filters for Go, including a standard bloom
filter, a counting bloom filter, and a layered bloom filter (for counting
occurrences of the same item.) All of them use the 64-bit FNV-1 hash function
and an efficient bitset.
A bloom filter is a space-efficient probabilistic data structure that is used
to test whether an element is a member of a set. False positives are possible,
but false negatives are not; i.e. a query returns either "inside set (may be
wrong)" or "definitely not in set". Elements can be added to the set, but not
removed (though this can be addressed with a counting filter.)
== Installation
go get github.com/pmylund/go-bloom
== Documentation
go doc github.com/pmylund/go-bloom
or http://go.pkgdoc.org/github.com/pmylund/go-bloom
== Usage
import "github.com/pmylund/go-bloom"
// Normal bloom filter
// Create a bloom filter which will contain an expected 100,000 items, and which
// allows a false positive rate of 1%.
f := bloom.New(100000, 0.01)
// Add an item to the filter
f.Add([]byte("foo"))
// Check if an item has been added to the filter (if true, subject to the
// false positive chance; if false, then the item definitely has not been
// added to the filter.)
f.Test([]byte("foo"))
// Counting bloom filter
// Create a counting bloom filter which will contain an expected 100,000 items,
// and which allows a false positive rate of 1%.
f := bloom.NewCounting(100000, 0.01)
// Add an item to the counting filter
f.Add([]byte("foo"))
// Remove an item from the counting filter
f.Remove([]byte("foo"))
// Layered bloom filter
// Create a layered bloom filter which will contain an expected 100,000 items,
// and which allows a false positive rate of 1%.
f := bloom.NewLayered(100000, 0.01)
// Add an item to the layered filter
f.Add([]byte("foo"))
// Add an item to the layered filter again
f.Add([]byte("foo"))
// Find out how many times an item appears in the layered filter
count := f.Test([]byte("foo")
count == 2
To use go-bloom in multiple goroutines, use a sync.RWMutex, and surround test
calls with RLock()/RUnlock(), and set calls with Lock()/()Unlock.
go-bloom is based on bloom by Will Fitzgerald.
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CountingFilter ¶
type CountingFilter struct {
// contains filtered or unexported fields
}
A counting bloom filter using the 64-bit FNV-1a hash function. Supports removing items from the filter.
func NewCounting ¶
func NewCounting(n int, p float64) *CountingFilter
Create a counting bloom filter with an expected n number of items, and an acceptable false positive rate of p. Counting bloom filters support the removal of items from the filter.
func (*CountingFilter) Remove ¶
func (f *CountingFilter) Remove(data []byte)
Removes data from the filter. This exact data must have been previously added to the filter, or future results will be inconsistent.
func (*CountingFilter) Test ¶
func (f *CountingFilter) Test(data []byte) bool
Checks whether data was previously added to the filter. Returns true if yes, with a false positive chance near the ratio specified upon creation of the filter. The result cannot cannot be falsely negative (unless one has removed an item that wasn't actually added to the filter previously.)
type CountingFilter64 ¶
type CountingFilter64 struct {
// contains filtered or unexported fields
}
A counting bloom filter using the 64-bit FNV-1a hash function. Supports removing items from the filter.
func NewCounting64 ¶
func NewCounting64(n int64, p float64) *CountingFilter64
Create a counting bloom filter with an expected n number of items, and an acceptable false positive rate of p. Counting bloom filters support the removal of items from the filter.
func (*CountingFilter64) Remove ¶
func (f *CountingFilter64) Remove(data []byte)
Removes data from the filter. This exact data must have been previously added to the filter, or future results will be inconsistent.
func (*CountingFilter64) Test ¶
func (f *CountingFilter64) Test(data []byte) bool
Checks whether data was previously added to the filter. Returns true if yes, with a false positive chance near the ratio specified upon creation of the filter. The result cannot cannot be falsely negative (unless one has removed an item that wasn't actually added to the filter previously.)
type Filter ¶
type Filter struct {
// contains filtered or unexported fields
}
A standard bloom filter using the 64-bit FNV-1a hash function.
type Filter64 ¶
type Filter64 struct {
// contains filtered or unexported fields
}
A standard 64-bit bloom filter using the 64-bit FNV-1a hash function.
type LayeredFilter ¶
type LayeredFilter struct {
// contains filtered or unexported fields
}
A layered bloom filter using the 64-bit FNV-1a hash function.
func NewLayered ¶
func NewLayered(n int, p float64) *LayeredFilter
Create a layered bloom filter with an expected n number of items, and an acceptable false positive rate of p. Layered bloom filters can be used to keep track of a certain, arbitrary count of items, e.g. to check if some given data was added to the filter 10 times or less.
func (*LayeredFilter) Add ¶
func (f *LayeredFilter) Add(data []byte) int
Adds data to the filter. Returns the number of the layer where the data was added, e.g. 1 for the first layer.
func (*LayeredFilter) Test ¶
func (f *LayeredFilter) Test(data []byte) (int, bool)
Checks whether data was previously added to the filter. Returns the number of the last layer where the data was added, e.g. 1 for the first layer, and a boolean indicating whether the data was added to the filter at all. The check has a false positive chance near the ratio specified upon creation of the filter. The result cannot be falsely negative.
type LayeredFilter64 ¶
type LayeredFilter64 struct {
// contains filtered or unexported fields
}
A layered bloom filter using the 64-bit FNV-1a hash function.
func NewLayered64 ¶
func NewLayered64(n int64, p float64) *LayeredFilter64
Create a layered bloom filter with an expected n number of items, and an acceptable false positive rate of p. Layered bloom filters can be used to keep track of a certain, arbitrary count of items, e.g. to check if some given data was added to the filter 10 times or less.
func (*LayeredFilter64) Add ¶
func (f *LayeredFilter64) Add(data []byte) int
Adds data to the filter. Returns the number of the layer where the data was added, e.g. 1 for the first layer.
func (*LayeredFilter64) Test ¶
func (f *LayeredFilter64) Test(data []byte) (int, bool)
Checks whether data was previously added to the filter. Returns the number of the last layer where the data was added, e.g. 1 for the first layer, and a boolean indicating whether the data was added to the filter at all. The check has a false positive chance near the ratio specified upon creation of the filter. The result cannot be falsely negative.
Source Files