README
¶
bloom
A set of bloom filter implementations, forked from zentures due to inactivity.
Package bloom currently supports:
- Optimized bloom filters (hash-partitioned arrays)
- Scalable Bloom Filters
Additional information regarding benchmarks is here.
For examples, take a look at the *_test.go files in each of the directories.
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Filter ¶
type Filter struct {
// contains filtered or unexported fields
}
Filter is the standard implementation used by this package. It is a variant implementation of the standard bloom filter that reduces the risk of false-positives by assigning a bit array to each hash function.
Reference #2: Scalable Bloom Filters (http://gsd.di.uminho.pt/members/cbm/ps/dpdf)
The name Partitioned Bloom Filter is my choice as there was no name assigned to f variant.
func New ¶
New initializes a new partitioned bloom filter. n is the number of items f bloom filter predicted to hold.
func (*Filter) EstimatedFillRatio ¶
type Option ¶
type Option func(*params)
func WithErrorRate ¶
WithErrorRate sets the desired error rate for the bloom filter. Smaller values of e imply a larger number of hash values used to set and test bits (the K parameter).
If e <= 0, defaults to .001.
func WithFillRatio ¶
WithFillRation specifies the maximum porportion of bits that may be set to 1 in the filter. This influences how large the filter must be in order to guarantee the specified error rate. Note that this fill ratio is not strictly enforced. Overloading a filter happens silently, causing the error rate (false positives) to increase.
If p <= 0, defaults to 0.5
type ScalableFilter ¶
type ScalableFilter struct {
// contains filtered or unexported fields
}
ScalableFilter is an implementation of the Scalable Bloom Filter that "addresses the problem of having to choose an a priori maximum size for the set, and allows an arbitrary growth of the set being presented." Reference #2: Scalable Bloom Filters (http://gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf)
func NewScalable ¶
func NewScalable(n uint, opt ...Option) *ScalableFilter
New initializes a new partitioned bloom filter. n is the number of items sbf bloom filter predicted to hold.
func (*ScalableFilter) Add ¶
func (sbf *ScalableFilter) Add(item []byte)
func (*ScalableFilter) Check ¶
func (sbf *ScalableFilter) Check(item []byte) bool
func (*ScalableFilter) Count ¶
func (sbf *ScalableFilter) Count() uint
func (*ScalableFilter) EstimatedFillRatio ¶
func (sbf *ScalableFilter) EstimatedFillRatio() float64
func (*ScalableFilter) FillRatio ¶
func (sbf *ScalableFilter) FillRatio() float64
func (*ScalableFilter) Reset ¶
func (sbf *ScalableFilter) Reset()
Source Files