bloom

package
v1.11.6-stella Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: May 25, 2024 License: BSD-3-Clause Imports: 10 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source
var (
	EmptyFilter = &ReadFilter{
		hashSeeds: make([]uint64, minHashes),
		entries:   make([]byte, minEntries),
	}
	FullFilter = &ReadFilter{
		hashSeeds: make([]uint64, minHashes),
		entries:   make([]byte, minEntries),
	}
)

Functions

func Add

func Add(f *Filter, key, salt []byte)

func Contains

func Contains(c Checker, key, salt []byte) bool

func EstimateCount

func EstimateCount(numHashes, numEntries int, falsePositiveProbability float64) int

EstimateCount estimates the number of additions a bloom filter with [numHashes] and [numEntries] must have to reach [falsePositiveProbability]. This is derived by inversing a lower-bound on the probability of false positives. For values where numBits >> numHashes, the predicted probability is fairly accurate.

It is guaranteed to return a value in the range [0, MaxInt].

ref: https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=903775

func Hash

func Hash(key, salt []byte) uint64

func OptimalEntries

func OptimalEntries(count int, falsePositiveProbability float64) int

OptimalEntries calculates the optimal number of entries to use when creating a new Bloom filter when targenting a size of [count] with [falsePositiveProbability] assuming that the optimal number of hashes is used.

It is guaranteed to return a value in the range [minEntries, MaxInt].

ref: https://en.wikipedia.org/wiki/Bloom_filter

func OptimalHashes

func OptimalHashes(numEntries, count int) int

OptimalHashes calculates the number of hashes which will minimize the false positive probability of a bloom filter with [numEntries] after [count] additions.

It is guaranteed to return a value in the range [minHashes, maxHashes].

ref: https://en.wikipedia.org/wiki/Bloom_filter

func OptimalParameters

func OptimalParameters(count int, falsePositiveProbability float64) (int, int)

OptimalParameters calculates the optimal [numHashes] and [numEntries] that should be allocated for a bloom filter which will contain [count] and target [falsePositiveProbability].

Types

type Checker

type Checker interface {
	Contains(hash uint64) bool
}

type Filter

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

func New

func New(numHashes, numEntries int) (*Filter, error)

New creates a new Filter with the specified number of hashes and bytes for entries. The returned bloom filter is safe for concurrent usage.

func (*Filter) Add

func (f *Filter) Add(hash uint64)

func (*Filter) Contains

func (f *Filter) Contains(hash uint64) bool

func (*Filter) Count

func (f *Filter) Count() int

Count returns the number of elements that have been added to the bloom filter.

func (*Filter) Marshal

func (f *Filter) Marshal() []byte

type Metrics

type Metrics struct {
	Count      prometheus.Gauge
	NumHashes  prometheus.Gauge
	NumEntries prometheus.Gauge
	MaxCount   prometheus.Gauge
	ResetCount prometheus.Counter
}

Metrics is a collection of commonly useful metrics when using a long-lived bloom filter.

func NewMetrics

func NewMetrics(
	namespace string,
	registerer prometheus.Registerer,
) (*Metrics, error)

func (*Metrics) Reset

func (m *Metrics) Reset(newFilter *Filter, maxCount int)

Reset the metrics to align with the provided bloom filter and max count.

type ReadFilter

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

func Parse

func Parse(bytes []byte) (*ReadFilter, error)

Parse bytes into a read-only bloom filter.

func (*ReadFilter) Contains

func (f *ReadFilter) Contains(hash uint64) bool

func (*ReadFilter) Marshal

func (f *ReadFilter) Marshal() []byte

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL