bloomfilter

README

bloomfilter

A simple implementation of a Bloom Filter data structure.

Test

go test
go test -bench=.

Documentation

Overview

Package bloomfilter is a simple implementation of a Bloom filter. It uses the hashing algorithms FNV-1a and murmur3.

Example

package main

import (
	"fmt"
	"math"

	"github.com/mkraft/bloomfilter"
)

func main() {
	bf := bloomfilter.NewBloomFilter(math.MaxUint16)

	bf.Add([]byte("John"))
	bf.Add([]byte("Paul"))
	bf.Add([]byte("George"))
	bf.Add([]byte("Ringo"))

	switch bf.IsMember([]byte("Yoko")) {
	case bloomfilter.MaybeMember:
		panic("Yoko is not a member!")
	case bloomfilter.NotMember:
		fmt.Println("That is correct.")
	}

}

Output:

That is correct.

Index

• type BloomFilter
  • func NewBloomFilter(size uint64) *BloomFilter
  • func (bf *BloomFilter) Add(element []byte)
  • func (bf *BloomFilter) IsMember(element []byte) MembershipStatus
• type MembershipStatus

Examples

• Package

Types

type BloomFilter

type BloomFilter struct {
	BitVector []bool
	// contains filtered or unexported fields
}

BloomFilter holds the state of the Bloom filter instance.

func NewBloomFilter

func NewBloomFilter(size uint64) *BloomFilter

NewBloomFilter creates a new instance of a BloomFilter with the given size.

func (*BloomFilter) Add

func (bf *BloomFilter) Add(element []byte)

Add adds an element to the set.

func (*BloomFilter) IsMember

func (bf *BloomFilter) IsMember(element []byte) MembershipStatus

IsMember tests for the membership of an element in the set and returns a MembershipStatus.

type MembershipStatus

type MembershipStatus int

MembershipStatus contains the constants used to represent the two possible membership states either NotMember or MaybeMember.

const (
	// NotMember means the element is definitely not a mamber of the set.
	NotMember MembershipStatus = iota
	// MaybeMember means the element may be a member of the set.
	MaybeMember
)