bloom

README

Bloom Filter using double hashing.

func doubleFNV(b []byte) (uint64, uint64) {
    hx := fnv.New64()
    hx.Write(b)
    x := hx.Sum64()
    hy := fnv.New64a()
    hy.Write(b)
    y := hy.Sum64()
    return x, y
}

bf := bloom.New(1000000, 0.0001, doubleFNV)
bf.Add([]byte("hello"))
bf.Test([]byte("hello"))
bf.Test([]byte("world"))

Documentation

Overview

Package bloom implements Bloom Filter using double hashing

Index

• type ClassicFilter
  • func (f *ClassicFilter) Add(b []byte)
  • func (f *ClassicFilter) Reset()
  • func (f *ClassicFilter) Size() int
  • func (f *ClassicFilter) Test(b []byte) bool
• type Filter
  • func New(n int, p float64, h func([]byte) (uint64, uint64)) Filter

Types

type ClassicFilter

type ClassicFilter struct {
	B []byte
	K int
	H func([]byte) (uint64, uint64)
}

Classic Bloom Filter

func (*ClassicFilter) Add

func (f *ClassicFilter) Add(b []byte)

func (*ClassicFilter) Reset

func (f *ClassicFilter) Reset()

func (*ClassicFilter) Size

func (f *ClassicFilter) Size() int

func (*ClassicFilter) Test

func (f *ClassicFilter) Test(b []byte) bool

type Filter

type Filter interface {
	Add([]byte)       // add an entry to the filter
	Test([]byte) bool // test if an entry is in the filter
	Size() int        // size of the filter in bytes
	Reset()           // reset the filter to initial state
}

Filter is a generic Bloom Filter

func New

func New(n int, p float64, h func([]byte) (uint64, uint64)) Filter

New creates a classic Bloom Filter that is optimal for n entries and false positive rate of p. H is a double hash that takes an entry and returns two different hashes.