bf

README

Bloom Filter

Bloom Filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970.

This implement is experimental to written Golang to prove the basic concept of Bloom Filter.

Install

go get github.com/kkdai/bloomfilter

Usage

    //Create a couting bloom filter expect size 100, false detect rate 0.01
	cbf := NewCountingBloomFilter(100, 0.01)
	
	//Add item into cbf
	cbf.Add([]byte("foo"))
	cbf.Add([]byte("john"))
	cbf.Add([]byte("tom"))

	//test 
	fmt.Println("Test cbf:", cbf.Test([]byte("tom"))) //return "true"

    //Remvoe item from cbf
	cbf.Remove([]byte("john"))
	
	//test again
	fmt.Println("Test cbf:", cbf.Test([]byte("john"))) //return "false"

Inspired

• https://github.com/pmylund/go-bloom
• https://github.com/willf/bloom

Project52

It is one of my project 52.

License

This package is licensed under MIT license. See LICENSE for details.

Documentation

Index

• func CreateBloomFilter(setA []int, hashFns [](func(index int) int), m int) []int
• func MembershipTest(element int, filterSet []int, hashFns [](func(index int) int)) bool
• type CBF
  • func NewCountingBloomFilter(totalNumber uint32, falseDetectRate float64) *CBF
  • func (b *CBF) Add(element []byte)
  • func (b *CBF) Remove(element []byte)
  • func (b *CBF) Test(element []byte) bool

Examples

• CBF

Functions

func CreateBloomFilter

func CreateBloomFilter(setA []int, hashFns [](func(index int) int), m int) []int

CreateBloomFilter the basic function to create bloom filter.

func MembershipTest

func MembershipTest(element int, filterSet []int, hashFns [](func(index int) int)) bool

MembershipTest the basic test function from a bloom filter list.

Types

type CBF

type CBF struct {
	// contains filtered or unexported fields
}

CBF :Counting Bloom Filter

Example

m := 5
h1 := func(input int) int {
	return (input % m) + 1
}

var hashList [](func(index int) int)
hashList = append(hashList, h1)

var inputList = []int{100, 121, 456, 121, 987}
fmt.Println("Bloom Filter:", CreateBloomFilter(inputList, hashList, m))

func NewCountingBloomFilter

func NewCountingBloomFilter(totalNumber uint32, falseDetectRate float64) *CBF

NewCountingBloomFilter : Create a counting bloom filter with assigned expect element count and false detect rate.

func (*CBF) Add

func (b *CBF) Add(element []byte)

Add :add element into this cbf structure.

func (*CBF) Remove

func (b *CBF) Remove(element []byte)

Remove :will remove item from this structure.

func (*CBF) Test

func (b *CBF) Test(element []byte) bool

Test :test element if exist in cbf structure.