bloomfilter

README

bloomfilter

a bloomfilter implement with roaring bitmap.

Usage:

package main

import (
	"fmt"

	"github.com/safeie/bloomfilter"
)

func main() {
	cfg := bloomfilter.Config{
		N:        1000000,                    // capacity
		P:        0.00001,                    // false probability
		HashName: bloomfilter.HASHER_OPTIMAL, // hash functions
	}
	bf := bloomfilter.New(cfg, bloomfilter.NewRoaring(cfg))
	bf.Add([]byte("www.google.com"))
	bf.Add([]byte("twitter.com"))
	bf.Add([]byte("github.com"))

	fmt.Println(bf.Check([]byte("twitter.com")))
	fmt.Println(bf.Check([]byte("facebook.com")))
}

Documentation

Overview

Package bloomfilter contains a bloomfilter implement with roaring bitmap.

Index

• Constants
• Variables
• func K(m, n uint64) uint64
• func M(n uint64, p float64) uint64
• func New(cfg Config, bm Bitmaper) *bloomfilter
• func NewBitSet(cfg Config) *bitSet
• func NewRoaring(cfg Config) *roaring
• type Bitmaper
• type Config
• type Hash
  • func DefaultHashFactory(k uint64) []Hash
  • func HashWrapper(h hash.Hash) Hash
  • func OptimalHashFactory(k uint64) []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())
)

Functions

func K

func K(m, n uint64) uint64

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

func M

func M(n uint64, p float64) uint64

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

func New

func New(cfg Config, bm Bitmaper) *bloomfilter

New creates a new bloomfilter from a given config

func NewBitSet

func NewBitSet(cfg Config) *bitSet

NewBitSet constructor for bitSet with an array of m bits

func NewRoaring

func NewRoaring(cfg Config) *roaring

NewRoaring constructor for Roaring

Types

type Bitmaper

type Bitmaper interface {
	Add(x uint64)
	Check(x uint64) bool
	Count() uint64
	Optimize()
}

Bitmaper bitmap interface

type Config

type Config struct {
	N        uint64  // capacity
	P        float64 // false probability
	HashName string  // hash functions
}

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

type Hash

type Hash func([]byte) []uint64

func DefaultHashFactory

func DefaultHashFactory(k uint64) []Hash

func HashWrapper

func HashWrapper(h hash.Hash) Hash

func OptimalHashFactory

func OptimalHashFactory(k uint64) []Hash

type HashFactory

type HashFactory func(uint64) []Hash