bloom

Documentation

Overview

Package bloom implements a Bloom filter data structure.

Index

• type Filter
  • func New(b, k int) *Filter
  • func (f *Filter) Insert(item []byte)
  • func (f *Filter) MarshalBinary() ([]byte, error)
  • func (f *Filter) MaybeContains(item []byte) bool
  • func (f *Filter) UnmarshalBinary(data []byte) error

Types

type Filter

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

Filter is a Bloom filter, which represents a set of items and provides a probabilistic test for membership. Filter satisfies the encoding.BinaryMarshaler and BinaryUnmarshaler interfaces. The zero value represents an empty filter of size 0 that uses 0 hash values.

func New

func New(b, k int) *Filter

New returns a Filter of size b bytes that uses k hash values. It panics if b is not a power of 2 in the range [1, 8192] or k is not in the range [1, 16].

func (*Filter) Insert

func (f *Filter) Insert(item []byte)

Insert inserts item into f's set.

func (*Filter) MarshalBinary

func (f *Filter) MarshalBinary() ([]byte, error)

MarshalBinary marshals f into a binary form. It satisfies the encoding.BinaryMarshaler interface.

func (*Filter) MaybeContains

func (f *Filter) MaybeContains(item []byte) bool

MaybeContains reports whether item is probably in f's set. If MaybeContains returns true, a false positive is possible, but if MaybeContains returns false, item is definitely not in the set.

func (*Filter) UnmarshalBinary

func (f *Filter) UnmarshalBinary(data []byte) error

UnmarshalBinary unmarshals a binary representation of a Filter and stores the representation in f. If the size of the unmarshaled Filter in bytes is not a power of 2 in the range [1, 8192] or the unmarshaled number of hash values is not in the range [1, 16], UnmarshalBinary returns an error without modifying the contents of f. Otherwise, it overwrites any existing data in f and returns nil. UnmarshalBinary satisfies the encoding.BinaryUnmarshaler interface.