bloom

Documentation

Overview

Package bloom implements Bloom filters.

Index

• func BinaryMarshalLength(numElements int, falsePositiveRate float64) int64
• func Optimal(numElements int, falsePositiveRate float64) (sizeBits int, numHashes uint32)
• type Filter
  • func New(sizeBits int, numHashes uint32, prefix uint32) *Filter
  • func UnmarshalBinary(data []byte) (*Filter, error)
  • func UnmarshalJSON(data []byte) (*Filter, error)
  • func (f *Filter) Len() int
  • func (f *Filter) MarshalBinary() ([]byte, error)
  • func (f *Filter) MarshalJSON() ([]byte, error)
  • func (f *Filter) NumHashes() uint32
  • func (f *Filter) Set(x []byte)
  • func (f *Filter) Test(x []byte) bool

Functions

func BinaryMarshalLength

func BinaryMarshalLength(numElements int, falsePositiveRate float64) int64

BinaryMarshalLength returns the length of a binary marshaled filter ( in bytes ) using the optimal configuration for the given number of elements with the desired false positive rate.

func Optimal

func Optimal(numElements int, falsePositiveRate float64) (sizeBits int, numHashes uint32)

Optimal computes optimal Bloom filter parameters. These parameters are optimal for small bloom filters as described in section 4.1 of this paper:

https://web.stanford.edu/~ashishg/papers/inverted.pdf

Types

type Filter

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

Filter represents the state of the Bloom filter

func New

func New(sizeBits int, numHashes uint32, prefix uint32) *Filter

New creates a new Bloom filter

func UnmarshalBinary

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

UnmarshalBinary restores the state of the filter from raw data

func UnmarshalJSON

func UnmarshalJSON(data []byte) (*Filter, error)

UnmarshalJSON defines how this filter should be decoded from JSON

func (*Filter) Len

func (f *Filter) Len() int

Len returns the size of the filter in bytes

func (*Filter) MarshalBinary

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

MarshalBinary defines how this filter should be encoded to binary

func (*Filter) MarshalJSON

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

MarshalJSON defines how this filter should be encoded to JSON

func (*Filter) NumHashes

func (f *Filter) NumHashes() uint32

NumHashes returns the number of hash functions used in the filter

func (*Filter) Set

func (f *Filter) Set(x []byte)

Set marks x as present in the filter

func (*Filter) Test

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

Test checks whether x is present in the filter