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]) LoadPersistence() error
  • func (bf *BloomFilter[T]) MarshalBinary() ([]byte, error)
  • func (bf *BloomFilter[T]) SavePersistence() error
  • func (bf *BloomFilter[T]) UnmarshalBinary(data []byte) error
  • func (bf *BloomFilter[T]) WithAutoConfigure(elements uint64, requestedErrorRate float64) (*BloomFilter[T], error)
  • func (bf *BloomFilter[T]) WithHashFunctions(num int, hashFunc uint8) *BloomFilter[T]
  • func (bf *BloomFilter[T]) WithPersistence(persistence Persistence[T]) *BloomFilter[T]
  • func (bf *BloomFilter[T]) WithStorage(storage Storage[T]) (*BloomFilter[T], error)
• type BloomFilterData
• 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 FilePersistence
  • func NewFilePersistence[T common.Hashable](directory, filename string) *FilePersistence[T]
  • func (fp *FilePersistence[T]) Load(bf *BloomFilter[T]) error
  • func (fp *FilePersistence[T]) Save(bf *BloomFilter[T]) error
• type Persistence
• 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]) LoadPersistence

func (bf *BloomFilter[T]) LoadPersistence() error

LoadPersistence loads the BloomFilter data using the selected persistence mechanism

func (*BloomFilter[T]) MarshalBinary

func (bf *BloomFilter[T]) MarshalBinary() ([]byte, error)

func (*BloomFilter[T]) SavePersistence

func (bf *BloomFilter[T]) SavePersistence() error

SavePersistence saves the BloomFilter data using the selected persistence mechanism

func (*BloomFilter[T]) UnmarshalBinary

func (bf *BloomFilter[T]) UnmarshalBinary(data []byte) error

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 uint8) *BloomFilter[T]

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

func (*BloomFilter[T]) WithPersistence

func (bf *BloomFilter[T]) WithPersistence(persistence Persistence[T]) *BloomFilter[T]

WithPersistence sets the persistence mechanism for the BloomFilter

func (*BloomFilter[T]) WithStorage

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

WithStorage sets the storage mechanism for the BloomFilter

type BloomFilterData

type BloomFilterData[T common.Hashable] struct {
	NumHashFunctions int
	Seeds            []uint32
	HashFunctionEnum uint8
	StorageData      []byte
	StorageType      string
	FilterType       string
}

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 FilePersistence

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

func NewFilePersistence

func NewFilePersistence[T common.Hashable](directory, filename string) *FilePersistence[T]

func (*FilePersistence[T]) Load

func (fp *FilePersistence[T]) Load(bf *BloomFilter[T]) error

func (*FilePersistence[T]) Save

func (fp *FilePersistence[T]) Save(bf *BloomFilter[T]) error

type Persistence

type Persistence[T common.Hashable] interface {
	Save(*BloomFilter[T]) error
	Load(*BloomFilter[T]) error
}

type Storage

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

Storage defines the interface for bit storage operations