## bloom filter for go/golang

package implements a fast bloom filter with a []bool as 'bit'-set and JSONMarshal/JSONUnmarshal to store/reload the filter after casting it to []uint8. 


This bloom filter was developed to strengthen a website-log database and was tested and optimized for this log-entry mask: "2014/%02i/%02i %02i:%02i:%02i /info.html". 
Nonetheless bloom should work with any other form of entries. 

provides 32bit and 64bit boolsets for smaller or larger entry volumes. 

32bit - bloom: hash function is Berkeley DB smdb hash (slightly modified to optimize for smaller bitsets len<=4096). smdb <---

64bit - bloom: hash function is go's generic FNV64a hash 


go get

+ change to folder ../bloom 
+ create wordlist in file "words.txt" (you might use `python`)
+ run go test within the folder

go test

If you've installed the GOCONVEY TDD-framework you can run the tests automatically.

### usage

after installation add

import (

at your header. In the program use

// create a bloom filter for 65536 items and 1 % wrong-positive ratio 
bf := bloom.New(float64(1<<16), float64(0.01))

// create a bloom filter with 650000 for 65536 items and 7 locs per hash
bf = bloom.New(float64(650000), float64(7))

// add one item

// check if item is in the filter
isIn := bf.Has([]byte("butter"))
isNotIn := bf.Has([]byte("Butter"))

// convert to JSON ([]byte) 
// (the bitset (type []bool) is casted to []uint8 for compression)
Json := bf.JSONMarshal()

// restore a bloom filter from storage 
bf = JSONUnmarshal(Json)

to work with the bloom filter.

### why 'fast'? 

It's about 3 times faster than William Fitzgeralds real bitset bloom filter . 
This comes at the cost of 8times greater memory usage for the 'bit'-set which is basically a []bool slice (even if it could be stored in smaller []uint8 JSON-Object). 
You might get a bitset (instead of []bool) Bloom filter with a smaller memory footprint at (Note: bbloom uses the unsafe package)
	Bloom filter (filter size 524288, 7 hashlocs) 'Add' 65536 items (100 repetitions): 5656535 ns (86 ns/op) 'Has' 65536 items (100 repetitions): 5806509 ns (88 ns/op) 'Add' 65536 items (100 repetitions): 4481291 ns (68 ns/op) 'Has' 65536 items (100 repetitions): 4728276 ns (72 ns/op) 'Add' 65536 items (100 repetitions): 23620537 ns (360 ns/op) 'Test' 65536 items (100 repetitions): 22160548 ns (338 ns/op) 'Add' 65536 items (100 repetitions): 22613773 ns (345 ns/op) 'Check' 65536 items (100 repetitions): 18995579 ns (289 ns/op) 'Add' 65536 items (100 repetitions): 128564605 ns (1961 ns/op) 'Contains' 65536 items (100 repetitions): 127572465 ns (1946 ns/op)

(on MBPro15 OSX10.8.5 i7 4Core 2.4Ghz)

With 32bit bloom filters (bloom32) using smdb, bloom32 does hashing with only 2 bit shifts, one xor and one substraction per byte. smdb is about as fast as fnv64a but gives less collisions with the dataset (see mask above). bloom.New(float64(10 * 1<<16),float64(7)) populated with 1<<16 random items from the dataset (see above) and tested against the rest results in less than 0.05% collisions.

Test imports 1 package(s) ΒΆ