go_bloom_filter

README

go-bloom-filter

BloomFilter written in Golang.

Implementations

This repository contains several bloomfilter implementations that you can use to solve different distributed computing problems. The solution starts from an optimized local implementation that adds rotation, RPC coordination, and generic rejecters. The packages are:

• bitset: Implementations of bitsets for basic sets.
• bloomfilter: Optimized implementation of the bloomfilter.
• rotable: Implementation over the BF with 3 rotating buckets.
• rpc: Implementation of an RPC layer over rotable.
• sonic:Integration of the rpc package as a rejecter for Sonic

Documentation

Overview

Package go_bloom_filter contains common data and interfaces needed to implement BloomFilters

Index

• Constants
• Variables
• func K(m, n uint) uint
• func M(n uint, p float64) uint
• type BloomFilter
• type Config
• type EmptySet
  • func (e EmptySet) Add(_ []byte)
  • func (e EmptySet) Check(_ []byte) bool
  • func (e 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())
	SHA1   = HashWrapper(sha1.New())
	CRC64  = HashWrapper(crc64.New(crc64.MakeTable(crc64.ECMA)))
	FNV64  = HashWrapper(fnv.New64())
	FNV128 = HashWrapper(fnv.New128())
)

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

Functions

func K

func K(m, n uint) uint

func M

func M(n uint, p float64) uint

Types

type BloomFilter

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

type Config

type Config struct {
	N        uint
	P        float64
	HashName string
}

type EmptySet

type EmptySet int

func (EmptySet) Add

func (e EmptySet) Add(_ []byte)

func (EmptySet) Check

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

func (EmptySet) Union

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

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