dibf

Documentation

Index

• func EstimateParameters(n uint, e float64) (uint64, uint64)
• type DIBF
  • func New(m, k, r uint64, hashFns []types.Hash) *DIBF
  • func NewWithEstimates(n uint, e float64, f float64, hashFns []types.Hash) *DIBF
  • func (f *DIBF) Add(item []byte)
  • func (f *DIBF) ApproximateCount() int
  • func (f *DIBF) Cap() uint64
  • func (f *DIBF) Clear()
  • func (f *DIBF) Contains(item []byte) bool
  • func (f *DIBF) CurrentFalsePositiveRate() float64
  • func (f *DIBF) Delete(item []byte)
  • func (f *DIBF) K() uint64

Functions

func EstimateParameters

func EstimateParameters(n uint, e float64) (uint64, uint64)

EstimateParameters estimates requirements for m and k.

Based on: https://en.wikipedia.org/wiki/Bloom_filter#Optimal_number_of_hash_functions

Types

type DIBF

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

DIBF represents a Deletable Bloom filter.

Based on: https://arxiv.org/pdf/1005.0352.pdf

func New

func New(m, k, r uint64, hashFns []types.Hash) *DIBF

New returns a new pointer to a Deletable Bloom filter.

m - the total number of bits in the Bloom filter.
k - the number of hash functions used.
r - the size of the bitset used to store the collsions (r <= m).

func NewWithEstimates

func NewWithEstimates(n uint, e float64, f float64, hashFns []types.Hash) *DIBF

NewWithEstimates returns a pointer to a standard Bloom filter with the given number of items and false positive rate.

func (*DIBF) Add

func (f *DIBF) Add(item []byte)

Add adds an item to the Bloom filter.

func (*DIBF) ApproximateCount

func (f *DIBF) ApproximateCount() int

ApproximateCount returns the approximate number of items in the Bloom filter.

Based on: https://en.wikipedia.org/wiki/Bloom_filter#Approximating_the_number_of_items_in_a_Bloom_filter

func (*DIBF) Cap

func (f *DIBF) Cap() uint64

Cap returns the capacity of the Bloom filter.

func (*DIBF) Clear

func (f *DIBF) Clear()

Clear clears the Bloom filter.

func (*DIBF) Contains

func (f *DIBF) Contains(item []byte) bool

Contains returns true if the item is in the Bloom filter.

func (*DIBF) CurrentFalsePositiveRate

func (f *DIBF) CurrentFalsePositiveRate() float64

CurrentFalsePositiveRate returns the current false positive rate of the Bloom filter.

Based on: https://en.wikipedia.org/wiki/Bloom_filter#Probability_of_false_positives

func (*DIBF) Delete

func (f *DIBF) Delete(item []byte)

Delete deletes an item from the Bloom filter.

func (*DIBF) K

func (f *DIBF) K() uint64

K returns the number of hash functions used.