bloomflt

package module
v0.0.0-...-3b93d31 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Mar 11, 2018 License: MIT Imports: 5 Imported by: 0

README

bloomflt

GoDoc Build Status Coverage Status Go Report Card

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".

What is a 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.

How to use?

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)
    }
}

Documentation

Overview

Package bloomflt is implementation of bloom filter with no 3rd party dependencies.

Example
// We expect the set to contains up to 100 elements with acceptable false-positive rate of 0.01%
b := 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)
}
Output:

The set now has 'value1'.
The set now has ID 123.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func CalcOptimalMK

func CalcOptimalMK(n int, falsePositiveRate float64) (int, int)

CalcOptimalMK calculates optimal values of m and k for the specified number of elements in the set (n), and given acceptable false-positive rate (value from 0.0 to 1.0).

Types

type BloomFilter

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

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.

This implementation uses the big.Int type as bitset storage and FNV-1a (Fowler–Noll–Vo) and CRC32 from the builtin hash package as the base hash functions. Additional hash functions are simulated with "Double Hashing Scheme" by Kirsch and Mitzenmacher as explained in "Less Hashing, Same Performance: Building a Better Bloom Filter".

func New

func New(n int, falsePositiveRate float64) *BloomFilter

New creates a new bloom filter with optimal values of m and k for the given given acceptable false-positive rate (value from 0.0 to 1.0).

func NewMK

func NewMK(m int, k int) *BloomFilter

NewMK creates a new bloom filter with bucket size equal to m and number of hash functions equal to k.

func (*BloomFilter) AddBytes

func (b *BloomFilter) AddBytes(value []byte)

AddBytes inserts a bytes value to the set

func (*BloomFilter) AddString

func (b *BloomFilter) AddString(value string)

AddString inserts a string value to the set

func (*BloomFilter) AddUInt32

func (b *BloomFilter) AddUInt32(value uint32)

AddUInt32 inserts an int value to the set

func (*BloomFilter) AddUInt64

func (b *BloomFilter) AddUInt64(value uint64)

AddUInt64 inserts an int value to the set

func (*BloomFilter) ContainsBytes

func (b *BloomFilter) ContainsBytes(value []byte) bool

ContainsBytes tests if the set contains the given bytes value

func (*BloomFilter) ContainsString

func (b *BloomFilter) ContainsString(value string) bool

ContainsString tests if the set contains the given string value

func (*BloomFilter) ContainsUInt32

func (b *BloomFilter) ContainsUInt32(value uint32) bool

ContainsUInt32 tests if the set contains the given int value

func (*BloomFilter) ContainsUInt64

func (b *BloomFilter) ContainsUInt64(value uint64) bool

ContainsUInt64 tests if the set contains the given int value

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL