bloom

Documentation

Index

• type BitPackingStorage
  • func NewBitPackingStorage[T common.Hashable](size uint64, seeds []uint32) *BitPackingStorage[T]
  • func (b *BitPackingStorage[T]) CheckBit(key T) bool
  • func (b *BitPackingStorage[T]) SetBit(key T) error
• type BloomFilter
  • func NewBloomFilter[T common.Hashable]() *BloomFilter[T]
  • func (bf *BloomFilter[T]) WithAutoConfigure(elements uint64, requestedErrorRate float64) (*BloomFilter[T], error)
  • func (bf *BloomFilter[T]) WithHashFunctions(num int, hashFunc func(T, uint32) (uint64, error)) *BloomFilter[T]
  • func (bf *BloomFilter[T]) WithStorage(storage Storage[T]) (*BloomFilter[T], error)
• type ConventionalStorage
  • func NewConventionalStorage[T common.Hashable](size uint64, seeds []uint32) *ConventionalStorage[T]
  • func (c *ConventionalStorage[T]) CheckBit(key T) bool
  • func (c *ConventionalStorage[T]) SetBit(key T) error
• type Storage

Types

type BitPackingStorage

type BitPackingStorage[T common.Hashable] struct {
	// contains filtered or unexported fields
}

BitPackingStorage uses a slice of uint64 for efficient bit storage

func NewBitPackingStorage

func NewBitPackingStorage[T common.Hashable](size uint64, seeds []uint32) *BitPackingStorage[T]

NewBitPackingStorage creates a new BitPackingStorage with the given number of bits

Size here indicates the number of bits, and not the number of keys we wish to store.

func (*BitPackingStorage[T]) CheckBit

func (b *BitPackingStorage[T]) CheckBit(key T) bool

CheckBit checks if all bits corresponding to the given key are set to true. It iterates through the seeds and calculates the bit index using the calculateBitIndex method. If there is an error or the bit at the calculated index is not set, it returns false. Otherwise, it returns true.

func (*BitPackingStorage[T]) SetBit

func (b *BitPackingStorage[T]) SetBit(key T) error

SetBit sets the bit at the calculated index for a given key by iterating through each seed in the BitPackingStorage. It uses the calculateBitIndex method to determine the index and then sets the bit at that index using bitwise operations. If there is an error during the index calculation, the error is returned.

type BloomFilter

type BloomFilter[T common.Hashable] struct {
	Storage Storage[T]
	// contains filtered or unexported fields
}

BloomFilter holds the bit storage and hash functions

func NewBloomFilter

func NewBloomFilter[T common.Hashable]() *BloomFilter[T]

NewBloomFilter creates a new BloomFilter, initially with no storage

func (*BloomFilter[T]) WithAutoConfigure

func (bf *BloomFilter[T]) WithAutoConfigure(elements uint64, requestedErrorRate float64) (*BloomFilter[T], error)

WithAutoConfigure may be used in lieu of WithHashFunctions and WithStorage. It does this by calculating the best parameters for the Bloom Filter, based upon the formulas:

“m = -n * ln(p) / (ln(2)^2)“, where m is the number of bits, n is the required number of elements to be stored, and p is the requested error-rate, and

“k = (m / n) * ln(2)“, where k is the number of key hashes to use

It picks the most memory efficient Storage option (which will almost always be BitPackingStorage unless an tiny number of elements are expected to be stored in the Bloom Filter

Finally, it selects Murmur3 as the hash function to be used

func (*BloomFilter[T]) WithHashFunctions

func (bf *BloomFilter[T]) WithHashFunctions(num int, hashFunc func(T, uint32) (uint64, error)) *BloomFilter[T]

WithHashFunctions sets the number of hash functions to use and initializes the seeds

func (*BloomFilter[T]) WithStorage

func (bf *BloomFilter[T]) WithStorage(storage Storage[T]) (*BloomFilter[T], error)

WithStorage sets the storage mechanism for the BloomFilter

type ConventionalStorage

type ConventionalStorage[T common.Hashable] struct {
	// contains filtered or unexported fields
}

ConventionalStorage uses a slice of bool

func NewConventionalStorage

func NewConventionalStorage[T common.Hashable](size uint64, seeds []uint32) *ConventionalStorage[T]

NewConventionalStorage creates a new ConventionalStorage with the specified size

Size here indicates the number of bits - or here, being ConventionalStorage) - the number of cells in the slice, and not the number of keys we wish to store.

func (*ConventionalStorage[T]) CheckBit

func (c *ConventionalStorage[T]) CheckBit(key T) bool

CheckBit checks if all bits corresponding to the given key are set to true. It iterates through the seeds and calculates the bit index using the calculateBitIndex method. If there is an error or the bit at the calculated index is not set, it returns false. Otherwise, it returns true.

func (*ConventionalStorage[T]) SetBit

func (c *ConventionalStorage[T]) SetBit(key T) error

SetBit sets the bit at the calculated index for a given key by iterating through each seed in the ConventionalStorage. It uses the calculateBitIndex method to determine the index and then sets the bit at that index using bitwise operations. If there is an error during the index calculation, the error is returned.

type Storage

type Storage[T common.Hashable] interface {
	SetBit(key T) error
	CheckBit(key T) bool
}

Storage defines the interface for bit storage operations