Struct BlockedBloomFilter 

pub struct BlockedBloomFilter { /* private fields */ }

Cache-line aligned blocked bloom filter for improved cache efficiency.

jj.md Task 3: Blocked Bloom Filter

This implementation groups all hash probes for a key into a single cache-line sized block, reducing cache misses from k (number of hashes) to 1.

Performance Benefits

• Cache efficiency: All probes hit the same cache line
• Reduced memory bandwidth: One cache line load vs k scattered loads
• Better TLB usage: Single page access per lookup

Trade-offs

• Slightly higher FPR than standard bloom filter at same memory usage
• Block selection uses one hash, remaining hashes probe within block

Reference

“Cache-Efficient Bloom Filters” (Putze et al., 2007)

Implementations

impl BlockedBloomFilter

pub fn new(expected_items: usize, false_positive_rate: f64) -> Self

Create a new blocked bloom filter.

Arguments

• expected_items - Number of items expected to be inserted
• false_positive_rate - Desired false positive rate (e.g., 0.01 for 1%)

pub fn for_level(expected_items: usize, level: usize) -> Self

Create a blocked bloom filter with level-adaptive FPR.

pub fn insert<T: Hash>(&mut self, item: &T)

Insert an item into the bloom filter.

pub fn contains<T: Hash>(&self, item: &T) -> bool

Check if an item might be in the set.

Returns true if item might be present (could be false positive). Returns false if item is definitely not present (100% accurate).

pub fn to_bytes(&self) -> Vec<u8>

Serialize to bytes with checksum.

pub fn from_bytes(bytes: &[u8]) -> Result<Self>

Deserialize from bytes with checksum validation.

pub fn size_bytes(&self) -> usize

Get size in bytes.

pub fn memory_usage(&self) -> usize

Get memory usage in bytes.

pub fn fill_ratio(&self) -> f64

Get fill ratio (fraction of bits set).

Trait Implementations

impl Debug for BlockedBloomFilter

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

Formats the value using the given formatter.