DOCSEARCHbyAlgolia
Submit Docs

bits-and-blooms/bloom

repository·master·Indexed 25 days ago

https://github.com/bits-and-blooms/bloom

A high-performance Go implementation of Bloom filters for space-efficient set membership testing with controllable false positive rates. Features include capacity estimation via NewWithEstimates, support for byte and string keys, and optimized patterns like TestAndAdd and TestOrAdd. The library supports serialization via JSON, Gob, and binary formats, and implements io.WriterTo and io.ReaderFrom for streaming. Note that the implementation is not thread-safe for concurrent modifications.

Tokens
1.2K
Snippets
3
Records
15
Agent score
34%

What's inside bits-and-blooms/bloom

  2. Verify the False Positive Rate

    master

    You can estimate the actual false positive rate of a Bloom filter using bloom.EstimateFalsePositiveRate(m, k, n), where m is the number of bits, k is the number of hashing functions, and n is the set size.

    This function is relatively expensive because it creates a temporary Bloom filter and is intended for validation purposes only.

    // Validate computed parameters
m, k := bloom.EstimateParameters(n, fp)
ActualfpRate := bloom.EstimateFalsePositiveRate(m, k, n)

// Or validate an existing filter
f := bloom.NewWithEstimates(n, fp)
ActualfpRate := bloom.EstimateFalsePositiveRate(f.m, f.k, n)

  3. Add and test items in a Bloom filter

    master

    The implementation accepts keys as []byte.

    To add an item, use .Add([]byte). To check for membership, use .Test([]byte).

    For non-byte types like strings or integers, you must encode them into a byte slice first (e.g., using encoding/binary for numbers).

  4. Serialize and deserialize Bloom filters

    master

    Bloom filters implement the io.WriterTo and io.ReaderFrom interfaces, allowing them to be read from or written to any stream (like a file or network connection).

    Performance Tip: Wrap your streams with bufio (e.g., bufio.NewWriter or bufio.NewReader) to improve performance when performing I/O operations.

  5. Initialize a Bloom filter with capacity and false positive rate

    master

    Use bloom.NewWithEstimates(n, fp) to create a Bloom filter where n is the desired capacity (number of elements) and fp is the desired false positive rate (e.g., 0.01 for 1%).

    Note: Bloom filters are not dynamic. You must specify the capacity upfront. If the actual number of elements exceeds the specified capacity, the false-positive rate may exceed your target.

    filter := bloom.NewWithEstimates(1000000, 0.01)

  6. Handle Goroutine safety

    master

    The Bloom filter implementation is not thread-safe by default to maximize performance.

    • Unsafe: Accessing the same filter from multiple goroutines where at least one is modifying the filter.
    • Safe: Accessing the same filter from multiple goroutines if you never modify the content (read-only access).
    • How to synchronize: If you need concurrent writes/reads, use a sync.Mutex to serialize operations or use channels to manage ownership.

  7. Test membership in a Bloom filter

    master
    Use Test([]byte) or TestString(string) to check if an item is likely in the set. If the method returns false, the item is definitely not in the set. If it returns true, the item might be in the set (subject to the false positive rate).

  8. Serialize and deserialize Bloom filters

    master

    Bloom filters support several serialization formats:

    • JSON: Implements json.Marshaler and json.Unmarshaler.
    • Binary: Implements MarshalBinary and UnmarshalBinary (via WriteTo and ReadFrom).
    • Gob: Implements GobEncode and GobDecode.
    • I/O Streams: Use WriteTo(io.Writer) and ReadFrom(io.Reader) for efficient streaming to files or network connections.

  10. Estimate the false positive rate

    master
    The function EstimateFalsePositiveRate(m, k, n) provides an empirical estimation of the false positive rate for a filter with m bits, k hash functions, and n entries. Note that this is a relatively slow, empirical test and is primarily intended for validation.

  11. Use TestAndAdd and TestOrAdd patterns

    master

    The API provides optimized methods for common membership-check-and-update patterns:

    • TestAndAdd([]byte): Returns true if the item was already present, then unconditionally adds it.
    • TestOrAdd([]byte): Returns true if the item was already present; if not, it adds the item. This is more efficient if you only want to add missing items.

  12. Create a new Bloom filter

    master
    You can create a new Bloom filter using New(m, k) where m is the number of bits (capacity) and k is the number of hashing functions. Alternatively, use NewWithEstimates(n, fp) to automatically calculate optimal m and k based on the expected number of items n and a desired false positive rate fp.