bloomfilter

Documentation

Overview

Package bloomfilter contains common data and interfaces needed to implement bloomfilters.

It is based on the theory explained in: http://llimllib.github.io/bloomfilter-tutorial/ In the repo, there are created the following types of bloomfilter: derived from bitset, sliding bloomfilters and rpc bloomfilter implementation.

Index

• Constants
• Variables
• func K(m, n uint) uint
• func M(n uint, p float64) uint
• type Bloomfilter
• type Config
• type EmptySet
  • func (EmptySet) Add(_ []byte)
  • func (EmptySet) Check(_ []byte) bool
  • func (EmptySet) Union(interface{}) (float64, error)
• type Hash
  • func DefaultHashFactory(k uint) []Hash
  • func HashWrapper(h hash.Hash) Hash
  • func OptimalHashFactory(k uint) []Hash
• type HashFactory

Constants

const (
	HASHER_DEFAULT = "default"
	HASHER_OPTIMAL = "optimal"
)

Variables

var (
	HashFactoryNames = map[string]HashFactory{
		HASHER_DEFAULT: DefaultHashFactory,
		HASHER_OPTIMAL: OptimalHashFactory,
	}

	ErrImpossibleToTreat = fmt.Errorf("unable to union")

	MD5    = HashWrapper(md5.New())  // skipcq: GO-S1023, GSC-G401
	SHA1   = HashWrapper(sha1.New()) // skipcq: GO-S1025, GSC-G401
	CRC64  = HashWrapper(crc64.New(crc64.MakeTable(crc64.ECMA)))
	FNV64  = HashWrapper(fnv.New64())
	FNV128 = HashWrapper(fnv.New128())
)

var EmptyConfig = Config{
	N: 2,
	P: .5,
}

EmptyConfig configuration used for first empty `previous` bloomfilter in the sliding three bloomfilters

Functions

func K

func K(m, n uint) uint

K function computes the number of hashfunctions of the bloomfilter as function of n and p

func M

func M(n uint, p float64) uint

M function computes the length of the bit array of the bloomfilter as function of n and p

Types

type Bloomfilter

type Bloomfilter interface {
	Add([]byte)
	Check([]byte) bool
	Union(interface{}) (float64, error)
}

Bloomfilter interface implemented in the different packages

type Config

type Config struct {
	N        uint    `json:"n"`
	P        float64 `json:"p"`
	HashName string  `json:"hash_name"`
}

Config for bloomfilter defining the parameters: P - desired false positive probability, N - number of elements to be stored in the filter and HashName - the name of the particular hashfunction

type EmptySet

type EmptySet int

EmptySet type is a synonym of int

func (EmptySet) Add

func (EmptySet) Add(_ []byte)

Add implementation for EmptySet

func (EmptySet) Check

func (EmptySet) Check(_ []byte) bool

Check implementation for EmptySet

func (EmptySet) Union

func (EmptySet) Union(interface{}) (float64, error)

Union implementation for EmptySet

type Hash

type Hash func([]byte) []uint

func DefaultHashFactory

func DefaultHashFactory(k uint) []Hash

func HashWrapper

func HashWrapper(h hash.Hash) Hash

func OptimalHashFactory

func OptimalHashFactory(k uint) []Hash

type HashFactory

type HashFactory func(uint) []Hash