bloom

Documentation

Overview

package bloom implements bloom filters.

Bloom filters are probabilistic data structures that can be used to test whether an element is a member of a set.

The operations on bloom filters are the following:

1. Insert(x): insert x into the set.

2. Contains(x): check if x is in the set.

Index

• Constants
• type Filter
  • func New(expectedSize int, falsePositiveRate float64, tp HasherType) Filter
• type HasherType

Constants

const (
	// RecommendedFalsePositiveRate is the recommended false positive rate
	// to use with bloom filters - 1%.
	RecommendedFalsePositiveRate float64 = 0.01
)

Types

type Filter

type Filter interface {
	// Insert inserts the given item into the bloom filter.
	// The item must be hashable.
	Insert(item []byte) error
	// Contains checks whether the provided item is in the bloom filter.
	// The item must be hashable.
	Contains(item []byte) bool
}

func New

func New(expectedSize int, falsePositiveRate float64, tp HasherType) Filter

New creates a new bloom filter, given the expected size of the set backed by the filter, and a false positive rate interpreted as a percentage out of 100 (i.e 1 = 1%).

type HasherType

type HasherType int

const (
	HasherTypeKeccak256 HasherType = iota
	HasherTypeMurmur32
)