gobf

README

gobf - bloom filters in golang

Creating a basic bloom filter

If you want to create an in-memory bloom filter with the standard FNV hash function, call the function NewDefault:

hashes := uint32(5)
size := uint64(1000)

b, err := gobf.NewDefault(hashes, size)

Here, hashes refers to the number of hash functions to use and size refers to the size of the bit array.

Inserting into a bloom filter

Use the Insert method to insert a key into a bloom filter:

err := b.Insert([]byte("my key"))

Checking for the presence of a key

Similarly, use the Present method to check if the bloom filter contains a key:

present, err := b.Present([]byte("my key"))

Deleting a key

Use the Delete method:

err := b.Delete([]byte("my key"))

Note: since this isn't a counting filter, a delete may affect other keys.

Configurable bloom filters

The general constructor takes in these arguments:

func New(db gobf.Db, hash hash.Hash64, hashes uint32, seed uint64, size uint64) (*BloomFilter, error)

The argument hash enables the developer to use a different hash function as long as it implements the hash.Hash64 interface from the standard library.

If you want to use a different data store, provide a struct instance that implements the gobf.Db interface:

type Db interface {
     Init(uint64) error
     GetBit(uint64) (bool, error)
     SetBit(uint64, bool) error
}

Copyright

Copyright (c) 2014 David Huie. See LICENSE.txt for further details.

Documentation

Index

• type BloomFilter
  • func New(db Db, hash hash.Hash64, hashes uint32, seed uint64, size uint64) (*BloomFilter, error)
  • func NewDefault(hashes uint32, size uint64) (*BloomFilter, error)
  • func (bf *BloomFilter) Delete(key []byte) error
  • func (bf *BloomFilter) Insert(key []byte) error
  • func (bf *BloomFilter) Present(key []byte) (bool, error)
• type Db

Types

type BloomFilter

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

func New

func New(db Db, hash hash.Hash64, hashes uint32, seed uint64, size uint64) (*BloomFilter, error)

Returns a completely customizable bloom filter

func NewDefault

func NewDefault(hashes uint32, size uint64) (*BloomFilter, error)

Returns an in-memory bloom filter that builds on the FNV hash

func (*BloomFilter) Delete

func (bf *BloomFilter) Delete(key []byte) error

Deletes a key from the bloom filter

func (*BloomFilter) Insert

func (bf *BloomFilter) Insert(key []byte) error

Inserts a key into the bloom filter

func (*BloomFilter) Present

func (bf *BloomFilter) Present(key []byte) (bool, error)

Returns true if the key is present in the bloom filter

type Db

type Db interface {
	// Initializes the data store to contain the capacity specified by
	// the input uint
	Init(uint64) error

	GetBit(uint64) (bool, error)
	SetBit(uint64, bool) error
}