Struct BloomFilter 

pub struct BloomFilter<H: Hasher = Sha256> { /* private fields */ }

A Bloom Filter.

This implementation uses the Kirsch-Mitzenmacher optimization to derive k hash functions from two hash values, which are in turn derived from a single hash digest. This provides efficient hashing for BloomFilter::insert and BloomFilter::contains operations.

Hasher Selection

The H type parameter specifies the hash function to use. It defaults to Sha256. The hasher’s digest must be at least 16 bytes (128 bits) long, this is enforced at compile time.

When choosing a hasher, consider:

• Security: If the bloom filter accepts untrusted input, use a cryptographically secure hash function to prevent attackers from crafting inputs that cause excessive collisions (degrading the filter to always return true).

• Determinism: If the bloom filter must produce consistent results across runs or machines (e.g. for serialization or consensus-critical applications), avoid keyed or randomized hash functions. Both Sha256 and Blake3 are deterministic.

• Performance: Hash function performance varies with the size of items inserted and queried. Sha256 is faster for smaller items (up to ~2KB), while Blake3 is faster for larger items (4KB+).

Implementations

impl<H: Hasher> BloomFilter<H>

pub fn new(hashers: NonZeroU8, bits: NonZeroUsize) -> Self

Creates a new BloomFilter with hashers hash functions and bits bits.

The number of bits will be rounded up to the next power of 2. If that would overflow, the maximum power of 2 for the platform (2^63 on 64-bit) is used.

pub fn with_rate(expected_items: NonZeroUsize, fp_rate: BigRational) -> Self

Creates a new BloomFilter with optimal parameters for the expected number of items and desired false positive rate.

Uses exact rational arithmetic for full determinism across all platforms.

Arguments

• expected_items - Number of items expected to be inserted
• fp_rate - False positive rate as a rational (e.g., BigRational::from_frac_u64(1, 100) for 1%)

Panics

Panics if fp_rate is not in (0, 1).

pub const fn hashers(&self) -> NonZeroU8

Returns the number of hashers used by the filter.

pub const fn bits(&self) -> NonZeroUsize

Returns the number of bits used by the filter.

pub fn insert(&mut self, item: &[u8])

Inserts an item into the BloomFilter.

pub fn contains(&self, item: &[u8]) -> bool

Checks if an item is possibly in the BloomFilter.

Returns true if the item is probably in the set, and false if it is definitely not.

pub fn estimated_false_positive_rate(&self) -> BigRational

Estimates the current false positive probability.

This approximates the false positive rate as f^k where f is the fill ratio (proportion of bits set to 1) and k is the number of hash functions.

Returns a BigRational for exact representation and cross-platform determinism.

pub fn estimated_count(&self) -> BigRational

Estimates the number of items that have been inserted.

Uses the formula n = -(m/k) * ln(1 - x/m) where m is the number of bits, k is the number of hash functions, and x is the number of bits set to 1.

Returns a BigRational using log2_floor for the logarithm computation.

pub fn optimal_hashers(expected_items: usize, bits: usize) -> u8

Calculates the optimal number of hash functions for a given capacity and bit count.

Uses BigRational for determinism. The result is clamped to [1, 16] since beyond ~10-12 hashes provides negligible improvement while increasing CPU cost.

pub fn optimal_bits(expected_items: usize, fp_rate: &BigRational) -> usize

Calculates the optimal number of bits for a given capacity and false positive rate.

Uses exact rational arithmetic for full determinism across all platforms. The result is rounded up to the next power of 2. If that would overflow, the maximum power of 2 for the platform (2^63 on 64-bit) is used.

Formula: m = -n * log2(p) / ln(2)

Panics

Panics if fp_rate is not in (0, 1).

Trait Implementations

impl<H: Clone + Hasher> Clone for BloomFilter<H>

fn clone(&self) -> BloomFilter<H>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<H: Debug + Hasher> Debug for BloomFilter<H>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<H: Hasher> EncodeSize for BloomFilter<H>

fn encode_size(&self) -> usize

Returns the encoded size of this value (in bytes).

impl<H: Hasher> PartialEq for BloomFilter<H>

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<H: Hasher> Read for BloomFilter<H>

type Cfg = (NonZero<u8>, NonZero<u64>)

The Cfg type parameter allows passing configuration during the read process. This is crucial for safely decoding untrusted data, for example, by providing size limits for collections or strings.

fn read_cfg( buf: &mut impl Buf, (hashers_cfg, bits_cfg): &Self::Cfg, ) -> Result<Self, CodecError>

Reads a value from the buffer using the provided configuration cfg.

impl<H: Hasher> Write for BloomFilter<H>

fn write(&self, buf: &mut impl BufMut)

Writes the binary representation of self to the provided buffer buf.

impl<H: Hasher> Eq for BloomFilter<H>