Documentation ¶
Index ¶
- Variables
- func Add(f *Filter, key, salt []byte)
- func Contains(c Checker, key, salt []byte) bool
- func EstimateCount(numHashes, numEntries int, falsePositiveProbability float64) int
- func Hash(key, salt []byte) uint64
- func OptimalEntries(count int, falsePositiveProbability float64) int
- func OptimalHashes(numEntries, count int) int
- func OptimalParameters(count int, falsePositiveProbability float64) (int, int)
- type Checker
- type Filter
- type Metrics
- type ReadFilter
Constants ¶
This section is empty.
Variables ¶
var ( EmptyFilter = &ReadFilter{ hashSeeds: make([]uint64, minHashes), entries: make([]byte, minEntries), } FullFilter = &ReadFilter{ hashSeeds: make([]uint64, minHashes), entries: make([]byte, minEntries), } )
Functions ¶
func EstimateCount ¶ added in v1.10.18
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 OptimalEntries ¶ added in v1.10.18
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].
func OptimalHashes ¶ added in v1.10.18
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].
func OptimalParameters ¶ added in v1.10.18
OptimalParameters calculates the optimal [numHashes] and [numEntries] that should be allocated for a bloom filter which will contain [count] and target [falsePositiveProbability].
Types ¶
type Filter ¶
type Filter struct {
// contains filtered or unexported fields
}
func New ¶
New creates a new Filter with the specified number of hashes and bytes for entries. The returned bloom filter is safe for concurrent usage.
type Metrics ¶ added in v1.10.19
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.10.19
func NewMetrics( namespace string, registerer prometheus.Registerer, ) (*Metrics, error)
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