bloomfilter

README

GoLang Bloom Filter

Simple bloom filter implementation for the GoLang programming language

Installing

go get github.com/scottjr632/go-bloom-filter

Importing

import "github.com/scottjr632/go-bloom-filter"

Creating a new optimal filter

estimatedNumberOfItems, maxFailureRate := 3000, 0.01
bf := bloomfilter.NewFromEstimate(estimatedNumberOfItems, maxFailureRate)

Creating a new filter

sizeOfFilter, numHashFns := 128, 3
bf := bloomfilter.New(sizeOfFilter, numHashFns)

Handling values

Adding a value to the filter

valueToAdd := 'https://maliciousurl.xyz'
bf.Add(valueToAdd)

Checking if a value has been set

valueToCheck := 'https://maliciousurl.xyz'
bf.Check(valueToCheck) // -> true

bf.Check('value that has not been set') // -> false

Documentation

Overview

Package bloomfilter provides a simple bloom filter implementation for the GoLang programming language. This package includes the ability to create a new bloom filter from an estimated optimal size and optimal number of hash functions for the specified estimated max number of items to be set in the bloom filter as well as the maximum tolerable failure rate

Index

• type BloomFilter
  • func New(m, k int64) BloomFilter
  • func NewFromEstimate(expectedNumberOfItems int64, maxFPRate float64) BloomFilter

Types

type BloomFilter

type BloomFilter interface {
	// Add adds a value to the bloom filter
	Add(string)
	// Check checks to see if a value has been added to the bloom filter.
	// Check returns true if it thinks the value has been added and false
	// if it thinks the value has not been added.
	Check(string) bool
}

BloomFilter is a probabilistic data structure that will always return false if the value is not present but will sometimes return true if the value has not been set. BloomFilter is space-efficient, however, items cannot be deleted.

func New

func New(m, k int64) BloomFilter

New returns a new instance of BloomFilter NewBloomFilter accepts m and k as arguments where m is the size of the bloom filter and k is the number of hashing functions.

func NewFromEstimate

func NewFromEstimate(expectedNumberOfItems int64, maxFPRate float64) BloomFilter

NewFromEstimate returns a new instance of BloomFilter from an estimate of the required size of the bloom filter as well as an estimate of the optimal hash functions for the estimated number of items in the bloom filter NewBloomFilterFromEstimate takes in expectedNumberOfItems and maxFPRate as arguments where expectedNumberOfItems is the max number of items expected to be set in the bloom filter and maxFPRate is the max rate of failure tolerable for the filter