bloom

Documentation

Overview

Package bloom provides a space-efficient probabilistic set-membership filter. MayContain returns false only when an element is definitely absent; it may return true for elements never added (false positives). No false negatives are possible.

The filter uses the enhanced double-hashing scheme from Kirsch & Mitzenmacher (2006): two base FNV hashes produce k independent bit positions per element without needing k separate hash functions.

Index

• type Filter
  • func New(n uint, p float64) *Filter
  • func (f *Filter) Add(data []byte)
  • func (f *Filter) K() uint
  • func (f *Filter) M() uint64
  • func (f *Filter) MayContain(data []byte) bool

Types

type Filter

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

Filter is a Bloom filter backed by a compact bit array.

func New

func New(n uint, p float64) *Filter

New returns a Filter sized for n expected elements at false-positive probability p. p must be in (0,1); n must be > 0.

func (*Filter) Add

func (f *Filter) Add(data []byte)

Add inserts data into the filter.

func (*Filter) K

func (f *Filter) K() uint

K returns the number of hash functions used.

func (*Filter) M

func (f *Filter) M() uint64

M returns the total number of bits in the filter.

func (*Filter) MayContain

func (f *Filter) MayContain(data []byte) bool

MayContain reports whether data might be in the set. Returns false only when data is definitely absent.