bloom2

Bloom2 is a fast, sparse, 2-level bloom filter implementation for Rust that consumes about 2% of the memory of a standard bloom filter when empty. It grows its backing memory proportionally to filter load by splitting the bitmap into blocks and tracking populated blocks with a second-level block map, lazily allocating storage only where entries actually land.

Despite the sparse layout, it preserves the same false-positive probabilities and O(1) lookup and amortised O(1) insert performance as a conventional bloom filter, all implemented in safe Rust with no unsafe code and 32-bit/64-bit safety.

What You Get

• A 2-level sparse bloom filter with the same false-positive guarantees as a standard filter
• A CompressedBitmap that lazily allocates blocks as entries are inserted
• O(1) lookups and amortised O(1) inserts
• 32-bit and 64-bit safe implementation with no unsafe code
• Optional serde serialization support behind a feature flag
• Roughly 2% memory footprint when empty versus a standard bloom filter

Common Use Cases

• Tracking membership of large key sets while minimizing memory usage
• Deduplicating streams where a small false-positive rate is acceptable
• Pre-filtering expensive lookups (cache/database) with a cheap probabilistic check
• Sparse set representation where filter load stays well below capacity

Under The Hood

Architecture - The crate centers on a two-level CompressedBitmap in the bitmap module: a block map records which fixed-size usize blocks are populated, and the underlying blocks are allocated lazily only when written. bloom.rs layers the bloom filter semantics (hashing to bit positions) on top, filter_size.rs derives sizing from desired capacity and false-positive rate, and lib.rs exposes the public API. Tech Stack - Rust edition 2018 with zero required dependencies; optional serde and bytes features add serialization. Code Quality - The project ships a tests directory and benches, advertises no unsafe code, and documents its memory model carefully in the README diagrams. API Design - The filter presents a small, focused surface (construct with a target size, insert, and check membership), keeping the common path simple while the sparse allocation stays entirely internal.