ibloom

Documentation

Overview

Package ibloom implements a bloom filter on integer (uint32) sets.

Index

• func Estimate(n, fpr float64) (m int, k int)
• type Config
• type Filter
  • func FromConfig(cfg *Config) (Filter, error)
  • func NewFnv32(mbytes, k int) Filter

Functions

func Estimate

func Estimate(n, fpr float64) (m int, k int)

Estimate gives estimates of the size in bits (m) and the number of hash functions (k) which can represent sets of size 'n' with false positive rate 'fpr'. See Wikipedia for Bloom filters.

Estimate rounds m up to be byte-aligned.

Types

type Config

type Config struct {
	Name string
	M, K int
}

type Filter

type Filter interface {
	K() int
	M() int
	Config() *Config
	Ones(v uint32, fn func(int) bool) bool
	PutOnes(dst []uint32, v uint32)
	Add(d []byte, v uint32)
	Has(d []byte, v uint32) bool
	Set() []byte
}

func FromConfig

func FromConfig(cfg *Config) (Filter, error)

func NewFnv32

func NewFnv32(mbytes, k int) Filter

NewFnv32 creates an ibloom filter with mbytes bytes of data and k hash functions. The k hash functions are fnv hash based and cost just a multiply and xor on top of the cost of hashing the input value to achieve k variations.