Skip to main content

bloom.go

bloom.go - Overview​

This file implements Bloom filters for efficient set membership testing. It provides functions to create Bloom filters, check if a key may be present in a filter, and calculate the optimal bits per key for a desired false positive rate.

Detailed Documentation​

type Filter​

type Filter []byte
  • Purpose: Represents a Bloom filter as a byte slice.

func (f Filter) MayContainKey(k []byte) bool​

func (f Filter) MayContainKey(k []byte) bool
  • Purpose: Checks if the filter f may contain the key k by hashing the key and calling MayContain.
  • Parameters:
    • k ([]byte): The key to check for.
  • Returns: bool: True if the filter may contain the key, false otherwise. False positives are possible.

func (f Filter) MayContain(h uint32) bool​

func (f Filter) MayContain(h uint32) bool
  • Purpose: Checks if the filter f may contain the given hash h.
  • Parameters:
    • h (uint32): The hash value to check for.
  • Returns: bool: True if the filter may contain the hash, false otherwise. False positives are possible.

func NewFilter(keys []uint32, bitsPerKey int) Filter​

func NewFilter(keys []uint32, bitsPerKey int) Filter
  • Purpose: Creates a new Bloom filter that encodes a set of uint32 keys.
  • Parameters:
    • keys ([]uint32): The set of hash values to encode in the filter.
    • bitsPerKey (int): The number of bits to use per key, approximately. A good value is 10, which yields a filter with ~1% false positive rate.
  • Returns: Filter: A new Bloom filter containing the encoded keys.

func BloomBitsPerKey(numEntries int, fp float64) int​

func BloomBitsPerKey(numEntries int, fp float64) int
  • Purpose: Calculates the bits per key required for a Bloom filter based on the desired false positive rate.
  • Parameters:
    • numEntries (int): The number of entries that will be inserted into the Bloom filter.
    • fp (float64): The desired false positive rate (e.g., 0.01 for 1%).
  • Returns: int: The number of bits per key required to achieve the desired false positive rate.

func appendFilter(buf []byte, keys []uint32, bitsPerKey int) []byte​

func appendFilter(buf []byte, keys []uint32, bitsPerKey int) []byte
  • Purpose: Appends a Bloom filter encoding the provided keys to an existing buffer.
  • Parameters:
    • buf ([]byte): The buffer to append the filter to.
    • keys ([]uint32): The keys (as uint32 hash values) to encode in the filter.
    • bitsPerKey (int): The number of bits to use per key.
  • Returns: []byte: The updated buffer with the Bloom filter appended.

func extend(b []byte, n int) (overall, trailer []byte)​

func extend(b []byte, n int) (overall, trailer []byte)
  • Purpose: Extends the byte slice b by n zero bytes.
  • Parameters:
    • b ([]byte): The original byte slice.
    • n (int): The number of zero bytes to append.
  • Returns:
    • overall ([]byte): The extended byte slice.
    • trailer ([]byte): A slice of the n trailing zero bytes.

func Hash(b []byte) uint32​

func Hash(b []byte) uint32
  • Purpose: Implements a hashing algorithm similar to the Murmur hash.
  • Parameters:
    • b ([]byte): The byte slice to hash.
  • Returns: uint32: The resulting hash value.

Getting Started Relevance​