bloom

Documentation

Overview

Package bloom provides a simple bloom filter implementation.

Index

• type Filter
  • func New(bits int, k int) *Filter
  • func NewOptimal(n int, p float64) *Filter
  • func (f *Filter) Add(v []byte) bool
  • func (f *Filter) AddFilter(other *Filter)
  • func (f *Filter) Decode(r io.ByteReader) error
  • func (f *Filter) Encode(w io.Writer) error
  • func (f *Filter) Has(v []byte) bool
  • func (f *Filter) NBits() int
  • func (f *Filter) NElements() int
  • func (f *Filter) NHash() int
  • func (f *Filter) Seed() uint32
  • func (f *Filter) SetSeed(seed uint32)

Types

type Filter

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

Filter is a single bloom filter.

func New

func New(bits int, k int) *Filter

New creates a new bloom filter with the given parameters. Number of bits is rounded up to the nearest multiple of 8.

See NewOptimal for an alternative way to decide on the parameters.

func NewOptimal

func NewOptimal(n int, p float64) *Filter

NewOptimal creates a new bloom filter, with parameters optimal for the expected number of elements (n) and the required false-positive rate (p).

The calculation is taken from: https://en.wikipedia.org/wiki/Bloom_filter#Optimal_number_of_hash_functions

func (*Filter) Add

func (f *Filter) Add(v []byte) bool

Add adds v to the filter, and returns the value of Has(v) before adding. After calling Add, Has(v) will always be true. Makes k calls to hash.

func (*Filter) AddFilter

func (f *Filter) AddFilter(other *Filter)

AddFilter merges other into f. After merging, f is equivalent to have been added all the elements of other.

func (*Filter) Decode

func (f *Filter) Decode(r io.ByteReader) error

Decode reads an encoded filter from the stream and sets this filter's state to match it. Destroys the previously existing state of this filter.

func (*Filter) Encode

func (f *Filter) Encode(w io.Writer) error

Encode writes this filter to the stream. Can be reproduced later with Decode.

func (*Filter) Has

func (f *Filter) Has(v []byte) bool

Has checks if all k hash values of v were encountered. Makes at most k hash calculations.

func (*Filter) NBits

func (f *Filter) NBits() int

NBits returns the number of bits this filter uses.

func (*Filter) NElements

func (f *Filter) NElements() int

NElements returns an approximation of the number of elements added to the filter.

func (*Filter) NHash

func (f *Filter) NHash() int

NHash returns the number of hash functions this filter uses.

func (*Filter) Seed

func (f *Filter) Seed() uint32

Seed returns the hash seed of this filter. A new filter starts with a random seed.

func (*Filter) SetSeed

func (f *Filter) SetSeed(seed uint32)

SetSeed sets the hash seed of this filter. The filter must be empty.