bloom

package
v1.11.3-rc.0 Latest Latest
Warning

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

Go to latest
Published: Apr 29, 2024 License: BSD-3-Clause Imports: 10 Imported by: 4

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 added in v1.10.18

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

func Contains added in v1.10.18

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

func EstimateCount added in v1.10.18

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 added in v1.10.18

func Hash(key, salt []byte) uint64

func OptimalEntries added in v1.10.18

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 added in v1.10.18

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 added in v1.10.18

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 added in v1.10.18

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 added in v1.10.18

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

func (*Filter) Count added in v1.10.18

func (f *Filter) Count() int

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

func (*Filter) Marshal added in v1.10.18

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

type Metrics added in v1.11.1

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 added in v1.11.1

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

func (*Metrics) Reset added in v1.11.1

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

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

type ReadFilter added in v1.10.18

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

func Parse added in v1.10.18

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

Parse bytes into a read-only bloom filter.

func (*ReadFilter) Contains added in v1.10.18

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

func (*ReadFilter) Marshal added in v1.10.18

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

Jump to

Keyboard shortcuts

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