bloomfilter

README

bloomfilter

Documentation

Overview

Package bloomfilter is a thread-safe probabilisic filter. With default configuration it can store up to one million elements. All negative results to queries are meant to be 100% accurate, while false positives should happen less than once every three million queries.

Index

• Variables
• func Nhashings(s string, n int) []int
• type Bits
• type BloomFilter
  • func New() *BloomFilter
  • func (f *BloomFilter) Add(s string)
  • func (f *BloomFilter) Exists(s string) bool

Examples

• BloomFilter.Add
• BloomFilter.Exists

Variables

var Elements = 1000000 // n

Elements is the MAX number of elements to store in the filter.

var NumOfHashes = 5 // k

NumOfHashes is the number of hash functions to use.

Functions

func Nhashings

func Nhashings(s string, n int) []int

Nhashings creates in parallel the list of nums to insert in the filter based on n trivial different hashing functions.

Types

type Bits

type Bits struct {
	sync.Mutex
	// contains filtered or unexported fields
}

Bits is the list of numbers to insert in the bloom filter.

type BloomFilter

type BloomFilter struct {
	M map[int]struct{}
	sync.Mutex
}

BloomFilter is the thread-safe golang version of a bloom filter.

func New

func New() *BloomFilter

New creates a new *BloomFilter istance.

func (*BloomFilter) Add

func (f *BloomFilter) Add(s string)

Add adds an element to a *BloomFilter.

Example

package main

import (
	"fmt"

	"github.com/axamon/bloomfilter"
)

func main() {

	f := bloomfilter.New()

	fmt.Println(f.Exists("pluto"))

	f.Add("pluto")
	fmt.Println(f.Exists("pluto"))
}

Output:

false
true

func (*BloomFilter) Exists

func (f *BloomFilter) Exists(s string) bool

Exists returns true false with 100% certainty if element is NOT in the filter, returns true with LESS than 100% certainty if element seems to be present.

Example

package main

import (
	"fmt"
	"sync"

	randomdata "github.com/Pallinder/go-randomdata"
	"github.com/axamon/bloomfilter"
)

func main() {

	f := bloomfilter.New()

	n := 10000
	var wg sync.WaitGroup

	wg.Add(n)
	for i := 0; i < n; i++ {
		go func() {
			defer wg.Done()
			f.Add(randomdata.FirstName(randomdata.Male))
			f.Add(randomdata.FirstName(randomdata.Female))
		}()
	}
	wg.Wait()

	f.Add("pluto")
	f.Add("pippo")

	fmt.Println(f.Exists("pippo"))
	fmt.Println(f.Exists("pluto"))
	fmt.Println(f.Exists("minnie"))
	fmt.Println(f.Exists("paperino"))
}

Output:

true
true
false
false