DOCSEARCHbyAlgolia
Submit Docs

fastbloom

repository·main·Indexed 43 days ago

https://github.com/tomtomwombat/fastbloom

A high-performance, accurate Bloom filter implementation in Rust (v0.17.0). It features full concurrency support via AtomicBloomFilter, compatibility with any hasher, and efficient hash composition. The library provides a builder pattern for configuring bit counts and false positive rates, as well as optional Serde support for serialization.

Tokens
2.4K
Snippets
8
Records
11
Agent score
56%

What's inside fastbloom

  1. Use the BloomFilter API

    main

    The BloomFilter can be instantiated by specifying the number of bits or a target false positive rate. You can then insert items or initialize the filter with an iterator of items.

    Basic initialization with bit count

    let mut filter = BloomFilter::with_num_bits(1024).expected_items(2);
filter.insert("42");

    Initialization with target false positive rate

    let filter = BloomFilter::with_false_pos(0.001).items(["42", "🦀"].iter());
assert!(filter.contains("42"));

    Using a custom hasher

    fastbloom is compatible with any hasher. You can configure it using the .hasher() method.

    let filter = BloomFilter::with_num_bits(1024)
    .hasher(RandomState::default())
    .items(["42", "🦀"].iter());
    use fastbloom::BloomFilter;

let mut filter = BloomFilter::with_num_bits(1024).expected_items(2);
filter.insert("42");
filter.insert("🦀");

  2. Install fastbloom via Cargo

    main

    Add fastbloom to your Cargo.toml dependencies.

    Note: Due to an improved algorithm in version 0.17.x, Bloom filters are not compatible with serialization/deserialization from prior versions.

    # Cargo.toml
[dependencies]
fastbloom = "0.17.0"

  3. Configure fastbloom features

    main

    fastbloom provides several feature flags to tune performance and functionality:

    • rand (enabled by default): Uses thread_rng() for the DefaultHasher source. This is faster but requires additional dependencies. If you disable this using default-features = false, the DefaultHasher will use foldhash instead, resulting in a smaller code footprint at the expense of speed.
    • serde: Enables Serialize and Deserialize implementations for BloomFilters.
    • loom: Makes AtomicBloomFilters compatible with loom atomics for testing.

  4. Use BloomFilter for approximate membership testing

    main

    A BloomFilter is a space-efficient data structure used to check if an element is possibly in a set. It allows for false positives (reporting an item is present when it is not) but guarantees no false negatives (if an item was inserted, contains will always return true).

    Once constructed, the memory usage and number of hashes per item are fixed. You can instantiate a filter by specifying a target false positive rate or a fixed number of bits.

    use fastbloom::BloomFilter;

// Instantiate with a target false positive rate and expected items
let filter = BloomFilter::with_false_pos(0.001).expected_items(1000);

// Insert items
filter.insert("42");
filter.insert("🦀");

// Check membership
assert!(filter.contains("42"));
assert!(filter.contains("🦀"));
assert!(!filter.contains("unknown"));

  5. Use AtomicBloomFilter for thread-safe membership testing

    main

    An AtomicBloomFilter provides the same functionality as a BloomFilter but is designed for concurrent access. It uses atomic operations to allow multiple threads to insert and check items without explicit locking. Note that AtomicBloomFilter does not require the mut keyword for insert operations.

    use fastbloom::AtomicBloomFilter;

// AtomicBloomFilter can be shared across threads
let filter = AtomicBloomFilter::with_num_bits(1024).expected_items(100);
filter.insert("data");
assert!(filter.contains("data"));

  6. Configure BloomFilter using builders

    main

    Bloom filters are constructed using a builder pattern. You can configure them using several methods:

    • with_false_pos(fp: f64): Sets a target false positive rate. The bit vector size will be calculated based on this and the expected number of items.
    • with_num_bits(num_bits: usize): Sets a fixed number of bits for the underlying bit vector.
    • from_vec(bit_vec: Vec<u64>): Reconstructs a filter from an existing raw bit vector.

    Common builder methods include:

    • .expected_items(n): Sets the expected number of items to help calculate optimal parameters.
    • .hashes(n): Sets the number of hashes per item.
    • .seed(&[u8; 16]): Sets a seed for the hasher to ensure deterministic behavior.
    • .hasher(hasher): Uses a custom hasher (must implement BuildHasher).
    use fastbloom::BloomFilter;

// Example: Building a filter with specific constraints
let filter = BloomFilter::with_false_pos(0.01)
    .expected_items(5000)
    .seed(&[42; 16])
    .hashes(4);

  7. Use AtomicBloomFilter for concurrent access

    main

    For full concurrency support without lock contention, use AtomicBloomFilter. It is designed as a drop-in replacement for RwLock<OtherBloomFilter> because its methods take &self rather than &mut self, allowing multiple threads to interact with the filter simultaneously.

    use fastbloom::AtomicBloomFilter;

let filter = AtomicBloomFilter::with_num_bits(1024).expected_items(2);
filter.insert("42");
filter.insert("🦀");

  8. BloomFilter API Reference

    main

    Methods available on BloomFilter<S> where S: BuildHasher:

    MethodSignatureDescription
    containsfn contains(&self, val: &(impl Hash + ?Sized)) -> boolChecks if an element is possibly in the filter.
    contains_hashfn contains_hash(&self, hash: u64) -> boolChecks membership using a pre-computed source hash.
    insertfn insert(&mut self, val: &(impl Hash + ?Sized)) -> boolInserts an element. Returns true if it might have been previously present (potential false positive).
    insert_hashfn insert_hash(&mut self, hash: u64) -> boolInserts an element using a pre-computed source hash.
    insert_allfn insert_all<'a, T, I>(&mut self, iter: I) where T: Hash, I: IntoIterator<Item = &'a T>Inserts all items from an iterator.
    source_hashfn source_hash(&self, val: &(impl Hash + ?Sized)) -> u64Returns the initial hash of a value. Subsequent hashes are derived from this.
    num_hashesfn num_hashes(&self) -> u32Returns the number of hashes per item.
    num_bitsfn num_bits(&self) -> usizeReturns the total number of bits in the filter.
    expected_false_posfn expected_false_pos(&self, num_items: usize) -> f64Returns the expected false positive rate for a given number of items.
    unionfn union(&mut self, other: &Self)Performs a bitwise OR with another filter. Panics if hash counts differ.
    intersectfn intersect(&mut self, other: &Self)Performs a bitwise AND with another filter. Panics if hash counts differ.
    clearfn clear(&mut self)Resets all bits to zero.
    as_slicefn as_slice(&self) -> &[$bits]Returns the underlying bit slice.

  9. Use the default hasher for BloomFilter

    main

    The DefaultHasher is the recommended hasher for use with BloomFilter. It is a CloneBuildHasher wrapping a RandomDefaultHasher. It is optimized for performance because its build_hasher method is faster than standard alternatives like std::collections::hash_map::RandomState or SipHasher13, which is critical since build_hasher is called for every hash operation.

    You can initialize a DefaultHasher with a specific 16-byte seed to ensure deterministic hashing behavior.

    // Using the default (randomly seeded)
let hasher = DefaultHasher::default();

// Using a specific 16-byte seed for determinism
let seed = [0u8; 16];
let hasher = DefaultHasher::seeded(&seed);

  10. BloomFilter API Reference (Atomic)

    main

    Methods available on AtomicBloomFilter:

    MethodSignatureDescription
    containsfn contains(&self, val: &(impl Hash + ?Sized)) -> boolChecks if an element is possibly in the filter.
    contains_hashfn contains_hash(&self, hash: u64) -> boolChecks membership using a pre-computed source hash.
    insertfn insert(&self, val: &(impl Hash + ?Sized)) -> boolInserts an element (thread-safe). Returns true if it might have been previously present.
    insert_hashfn insert_hash(&self, hash: u64) -> boolInserts an element using a pre-computed source hash (thread-safe).
    num_hashesfn num_hashes(&self) -> u32Returns the number of hashes per item.
    num_bitsfn num_bits(&self) -> usizeReturns the total number of bits in the filter.

  11. Initialize RandomDefaultHasher with a seed

    main

    The RandomDefaultHasher uses SipHasher13 internally. You can create a deterministic instance by providing a 16-byte seed using the seeded method. If you use Default::default(), the hasher will be initialized with a random seed (either via the rand feature or by combining two foldhash::fast::RandomState instances).

    // Create a seeded RandomDefaultHasher
let seed = [0u8; 16];
let hasher = RandomDefaultHasher::seeded(&seed);