Documentation
¶
Overview ¶
Package bloom provides a space-efficient probabilistic set membership filter.
A Bloom filter answers "definitely not in set" or "possibly in set" with a tunable false-positive rate. It is useful as a pre-filter to avoid expensive exact lookups (map access, lock acquisition, disk I/O).
This implementation uses the double-hashing technique from Kirsch and Mitzenmacher (2006): two base hashes derive k bit positions via h(i) = h1 + i*h2 mod m, avoiding k independent hash functions.
Index ¶
- Variables
- type Filter
- func (f *Filter) Add(data []byte)
- func (f *Filter) AddBulk(items [][]byte)
- func (f *Filter) BitCount() uint
- func (f *Filter) EstimatedCount() uint
- func (f *Filter) FillRatio() float64
- func (f *Filter) HashCount() uint
- func (f *Filter) MarshalBinary() ([]byte, error)
- func (f *Filter) Reset()
- func (f *Filter) Test(data []byte) bool
- func (f *Filter) TestAndAdd(data []byte) bool
- func (f *Filter) TestBulk(items [][]byte) []bool
- func (f *Filter) UnmarshalBinary(data []byte) error
Constants ¶
This section is empty.
Variables ¶
var ( // ErrZeroN is returned when n (expected element count) is zero. ErrZeroN = errors.New("bloom: n must be positive") // ErrInvalidFP is returned when fp is not in the open interval (0, 1). ErrInvalidFP = errors.New("bloom: fp must be in the open interval (0, 1)") )
Functions ¶
This section is empty.
Types ¶
type Filter ¶
type Filter struct {
// contains filtered or unexported fields
}
Filter is a thread-safe Bloom filter.
func NewWithEstimates ¶
NewWithEstimates creates a Bloom filter sized for n expected elements at a false-positive rate of fp. Returns an error if n is zero or fp is not in the open interval (0, 1).
func (*Filter) EstimatedCount ¶
EstimatedCount returns an approximation of the number of elements that have been added to the filter.
func (*Filter) FillRatio ¶
FillRatio returns the fraction of bits that are set, in the range [0, 1].
func (*Filter) MarshalBinary ¶
MarshalBinary encodes the filter into a binary format. Layout: [m uint64][k uint64][count uint64][bits...].
func (*Filter) Reset ¶
func (f *Filter) Reset()
Reset clears the filter without reallocating the bit array.
func (*Filter) Test ¶
Test reports whether data is possibly in the filter. A return value of false guarantees the element was never added. A return value of true means the element might have been added (subject to the configured false-positive rate).
func (*Filter) TestAndAdd ¶
TestAndAdd tests for membership and then adds the element. It returns true if the element was possibly already present before this call.
func (*Filter) TestBulk ¶
TestBulk tests multiple elements for membership. Returns a bool slice of the same length as items, where each entry indicates possible presence.
func (*Filter) UnmarshalBinary ¶
UnmarshalBinary decodes the filter from a binary format produced by MarshalBinary.
Source Files