Implementation of bloom filter in Golang with no 3rd party dependencies.
Uses the big.Int type as bitset storage and two hash functions from the builtin hash package:
Those functions are used to simulate an arbitrary number of hash functions using the "Double Hashing Scheme" as described by Kirsch and Mitzenmacher in "Less Hashing, Same Performance: Building a Better Bloom Filter".
BloomFilter is an efficient data structure, used to test whether an element is a member of a set.
Bloom filters are probabilistic, which means that false positives are tolerated, but it is guaranteed there will be no false negatives.
In other words, if the bloom filter says an element is NOT in the set, then it is guaranteed the element is not in the set.
If the bloom filter says an element IS in the set, then that means the element is probably there, but it is not guaranteed.
package main
import (
"fmt"
"github.com/quasoft/bloomflt"
)
func main() {
// We expect the set to contains up to 100 elements and accept a false-positive rate of 0.01%
b := bloomflt.New(100, 0.01)
b.AddString("value1")
if b.ContainsString("value1") {
fmt.Println("The set now has 'value1'.")
}
someID := uint64(123)
b.AddUInt64(someID)
if b.ContainsUInt64(someID) {
fmt.Printf("The set now has ID %v.", someID)
}
}