filter

Documentation

Index

• func OptimalK(fpRate float64) uint
• func OptimalM(n uint, fpRate float64) uint
• type Buckets
  • func NewBuckets(count uint, bucketSize uint8) *Buckets
  • func (b *Buckets) Count() uint
  • func (b *Buckets) Get(bucket uint) uint32
  • func (b *Buckets) GobDecode(data []byte) error
  • func (b *Buckets) GobEncode() ([]byte, error)
  • func (b *Buckets) Increment(bucket uint, delta int32) *Buckets
  • func (b *Buckets) MaxBucketValue() uint8
  • func (b *Buckets) ReadFrom(stream io.Reader) (int64, error)
  • func (b *Buckets) Reset() *Buckets
  • func (b *Buckets) Set(bucket uint, value uint8) *Buckets
  • func (b *Buckets) WriteTo(stream io.Writer) (int64, error)
• type CountingBloomFilter
  • func NewCountingBloomFilter(n uint, b uint8, fpRate float64) *CountingBloomFilter
  • func NewDefaultCountingBloomFilter(n uint, fpRate float64) *CountingBloomFilter
  • func (c *CountingBloomFilter) Add(data []byte) Filter
  • func (c *CountingBloomFilter) Capacity() uint
  • func (c *CountingBloomFilter) Count() uint
  • func (c *CountingBloomFilter) K() uint
  • func (c *CountingBloomFilter) Reset() *CountingBloomFilter
  • func (c *CountingBloomFilter) SetHash(h hash.Hash64)
  • func (c *CountingBloomFilter) Test(data []byte) bool
  • func (c *CountingBloomFilter) TestAndAdd(data []byte) bool
  • func (c *CountingBloomFilter) TestAndRemove(data []byte) bool
• type Filter

Functions

func OptimalK

func OptimalK(fpRate float64) uint

OptimalK calculates the optimal number of hash functions to use for a Bloom filter based on the desired rate of false positives.

func OptimalM

func OptimalM(n uint, fpRate float64) uint

OptimalM calculates the optimal Bloom filter size, m, based on the number of items and the desired rate of false positives.

Types

type Buckets

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

Buckets is a fast, space-efficient array of buckets where each bucket can store up to a configured maximum value.

func NewBuckets

func NewBuckets(count uint, bucketSize uint8) *Buckets

NewBuckets creates a new Buckets with the provided number of buckets where each bucket is the specified number of bits.

func (*Buckets) Count

func (b *Buckets) Count() uint

Count returns the number of buckets.

func (*Buckets) Get

func (b *Buckets) Get(bucket uint) uint32

Get returns the value in the specified bucket.

func (*Buckets) GobDecode

func (b *Buckets) GobDecode(data []byte) error

GobDecode implements gob.GobDecoder interface.

func (*Buckets) GobEncode

func (b *Buckets) GobEncode() ([]byte, error)

GobEncode implements gob.GobEncoder interface.

func (*Buckets) Increment

func (b *Buckets) Increment(bucket uint, delta int32) *Buckets

Increment will increment the value in the specified bucket by the provided delta. A bucket can be decremented by providing a negative delta. The value is clamped to zero and the maximum bucket value. Returns itself to allow for chaining.

func (*Buckets) MaxBucketValue

func (b *Buckets) MaxBucketValue() uint8

MaxBucketValue returns the maximum value that can be stored in a bucket.

func (*Buckets) ReadFrom

func (b *Buckets) ReadFrom(stream io.Reader) (int64, error)

ReadFrom reads a binary representation of Buckets (such as might have been written by WriteTo()) from an i/o stream. It returns the number of bytes read.

func (*Buckets) Reset

func (b *Buckets) Reset() *Buckets

Reset restores the Buckets to the original state. Returns itself to allow for chaining.

func (*Buckets) Set

func (b *Buckets) Set(bucket uint, value uint8) *Buckets

Set will set the bucket value. The value is clamped to zero and the maximum bucket value. Returns itself to allow for chaining.

func (*Buckets) WriteTo

func (b *Buckets) WriteTo(stream io.Writer) (int64, error)

WriteTo writes a binary representation of Buckets to an i/o stream. It returns the number of bytes written.

type CountingBloomFilter

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

func NewCountingBloomFilter

func NewCountingBloomFilter(n uint, b uint8, fpRate float64) *CountingBloomFilter

NewCountingBloomFilter creates a new Counting Bloom Filter optimized to store n items with a specified target false-positive rate and bucket size. If you don't know how many bits to use for buckets, use NewDefaultCountingBloomFilter for a sensible default.

func NewDefaultCountingBloomFilter

func NewDefaultCountingBloomFilter(n uint, fpRate float64) *CountingBloomFilter

NewDefaultCountingBloomFilter creates a new Counting Bloom Filter optimized to store n items with a specified target false-positive rate. Buckets are allocated four bits.

func (*CountingBloomFilter) Add

func (c *CountingBloomFilter) Add(data []byte) Filter

Add will add the data to the Bloom filter. It returns the filter to allow for chaining.

func (*CountingBloomFilter) Capacity

func (c *CountingBloomFilter) Capacity() uint

Capacity returns the Bloom filter capacity, m.

func (*CountingBloomFilter) Count

func (c *CountingBloomFilter) Count() uint

Count returns the number of items in the filter.

func (*CountingBloomFilter) K

func (c *CountingBloomFilter) K() uint

K returns the number of hash functions.

func (*CountingBloomFilter) Reset

func (c *CountingBloomFilter) Reset() *CountingBloomFilter

Reset restores the Bloom filter to its original state. It returns the filter to allow for chaining.

func (*CountingBloomFilter) SetHash

func (c *CountingBloomFilter) SetHash(h hash.Hash64)

SetHash sets the hashing function used in the filter. For the effect on false positive rates see: https://github.com/tylertreat/BoomFilters/pull/1

func (*CountingBloomFilter) Test

func (c *CountingBloomFilter) Test(data []byte) bool

Test will test for membership of the data and returns true if it is a member, false if not. This is a probabilistic test, meaning there is a non-zero probability of false positives and false negatives.

func (*CountingBloomFilter) TestAndAdd

func (c *CountingBloomFilter) TestAndAdd(data []byte) bool

TestAndAdd is equivalent to calling Test followed by Add. It returns true if the data is a member, false if not.

func (*CountingBloomFilter) TestAndRemove

func (c *CountingBloomFilter) TestAndRemove(data []byte) bool

TestAndRemove will test for membership of the data and remove it from the filter if it exists. Returns true if the data was a member, false if not.

type Filter

type Filter interface {
	// Test will test for membership of the data and returns true if it is a
	// member, false if not.
	Test([]byte) bool

	// Add will add the data to the Bloom filter. It returns the filter to
	// allow for chaining.
	Add([]byte) Filter

	// TestAndAdd is equivalent to calling Test followed by Add. It returns
	// true if the data is a member, false if not.
	TestAndAdd([]byte) bool
}

Filter is a probabilistic data structure which is used to test the membership of an element in a set.