bloom

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) FullRatio() float64
  • func (b *Buckets) Get(bucket uint) uint32
  • func (b *Buckets) MaxBucketValue() uint8
  • func (b *Buckets) Reset() *Buckets
  • func (b *Buckets) Set(bucket uint, value uint8) *Buckets
• type Filter
  • func New(n uint, fpRate float64) *Filter
  • func (b *Filter) Add(data []byte)
  • func (b *Filter) Test(data []byte) (exist bool)
  • func (b *Filter) TestAndAdd(data []byte) bool

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

func (b *Buckets) FullRatio() float64

func (*Buckets) Get

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

Get returns the value in the specified bucket.

func (*Buckets) MaxBucketValue

func (b *Buckets) MaxBucketValue() uint8

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

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.

type Filter

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

Filter implements a classic thread-safe Bloom filter. A Bloom filter has a non-zero probability of false positives and a zero probability of false negatives.

func New

func New(n uint, fpRate float64) *Filter

New creates a new Bloom filter optimized to store n items with a specified target false-positive rate.

func (*Filter) Add

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

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

func (*Filter) Test

func (b *Filter) Test(data []byte) (exist bool)

func (*Filter) TestAndAdd

func (b *Filter) 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.