bloom

package module
v0.0.0-...-4ab62f5 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: May 28, 2012 License: MIT Imports: 7 Imported by: 0

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) Add

func (f *CountingFilter) Add(data []byte)

Adds data to 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) Reset

func (f *CountingFilter) Reset()

Resets the filter.

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) Add

func (f *CountingFilter64) Add(data []byte)

Adds data to 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) Reset

func (f *CountingFilter64) Reset()

Resets the filter.

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.

func New

func New(n int, p float64) *Filter

Create a bloom filter with an expected n number of items, and an acceptable false positive rate of p, e.g. 0.01.

func (*Filter) Add

func (f *Filter) Add(data []byte)

Add data to the filter.

func (*Filter) Reset

func (f *Filter) Reset()

Resets the filter.

func (*Filter) Test

func (f *Filter) Test(data []byte) bool

Check 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 be falsely negative.

type Filter64

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

A standard 64-bit bloom filter using the 64-bit FNV-1a hash function.

func New64

func New64(n int64, p float64) *Filter64

Create a bloom filter with an expected n number of items, and an acceptable false positive rate of p, e.g. 0.01 for 1%.

func (*Filter64) Add

func (f *Filter64) Add(data []byte)

Add data to the filter.

func (*Filter64) Reset

func (f *Filter64) Reset()

Resets the filter.

func (*Filter64) Test

func (f *Filter64) Test(data []byte) bool

Check 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 be falsely negative.

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) Reset

func (f *LayeredFilter) Reset()

Resets the filter.

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) Reset

func (f *LayeredFilter64) Reset()

Resets the filter.

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL