Struct BloomFilter 

pub struct BloomFilter<T: ?Sized> { /* private fields */ }

A space and time efficient Bloom Filter implementation.

This structure uses a Vec<u64> as a bit array for memory efficiency and implements double-hashing to simulate k hash functions with only two real hash computations.

Type Parameters

• T: The type of values to be stored. Must implement Hash.

Implementations

impl<T: ?Sized + Hash> BloomFilter<T>

pub fn new(expected_items: usize, params: impl Into<FilterParams>) -> Self

Creates a new Bloom Filter optimized for the given expected item count and configuration (either false positive rate or hash count).

Arguments

• expected_items - The expected number of items to insert (n).
• params - Either a f64 (false positive rate) or u32 (number of hashes).

Examples

use bloomlib::BloomFilter;

// Initialize with a desired false positive rate
let mut bf1: BloomFilter<str> = BloomFilter::new(1000, 0.01);

// Initialize with a specific hash count
let mut bf2: BloomFilter<str> = BloomFilter::new(1000, 7u32);

// Insert an item
bf1.insert("seen");

// Check for an item
_ = bf1.contains("seen");
_ = bf1.contains("unseen");

// Clear the filter
bf1.clear();

Panics

Panics if expected_items is 0, or if configuration parameters are invalid (e.g., rate <= 0.0, rate >= 1.0, or hashes == 0).

Examples found in repository

examples/simple.rs (line 9)

fn main() {
    // Configuration
    let expected_elements = 100_000;

    // You can initialize with a false positive rate
    let fp_rate = 0.01;
    let mut filter = BloomFilter::new(expected_elements, fp_rate);

    // OR initialize using a specific hash count (commented out example)
    // let hashes = 7u32;
    // let mut filter = BloomFilter::new(expected_elements, hashes);

    println!("Initializing Bloom Filter...");
    println!("Expected elements: {}", expected_elements);
    println!("Target False Positive Rate: {}", fp_rate);
    println!("Actual Hash Count (k): {}", filter.hash_count());

    // Insert data
    println!("Inserting values 0 to {}...", expected_elements);
    for i in 0..expected_elements {
        filter.insert(&i);
    }

    // Check true positives
    println!("Checking 10 known values...");
    let mut present_count = 0;
    for i in 0..10 {
        if filter.contains(&i) {
            present_count += 1;
        }
    }
    println!("Found {}/10 known values (Should be 10)", present_count);

    // Check false positives
    // We check numbers outside the inserted range.
    let check_range_start = expected_elements;
    let check_range_end = expected_elements + 10_000;
    println!(
        "Checking range {} to {} for false positives...",
        check_range_start, check_range_end
    );

    let mut fp_count = 0;
    for i in check_range_start..check_range_end {
        if filter.contains(&i) {
            fp_count += 1;
        }
    }

    let actual_fp_rate = fp_count as f64 / 10_000.0;
    println!("False Positives found: {}", fp_count);
    println!(
        "Actual FP Rate: {:.4} (Target: {})",
        actual_fp_rate, actual_fp_rate
    );
}

examples/benchmark.rs (line 35)

fn run_benchmark(n: usize, fp_rate: f64) {
    // --- Setup ---
    let mut bf = BloomFilter::new(n, fp_rate);
    let mut rng = Random::new(12345);

    println!("\n---------- Bloom Filter Performance Benchmark -----------\n");
    println!("Items:          {}", n);
    println!("Target FP Rate: {}", fp_rate);
    println!("Hash Count:     {}", bf.hash_count());
    println!("\n---------------------------------------------------------\n");

    // Generate data
    let mut dataset = Vec::with_capacity(n);
    for _ in 0..n {
        dataset.push(rng.next_u64());
    }

    // --- Metric 1: Memory Usage ---
    let ki = 1024.0;
    let memory_bytes = bf.memory_usage_bytes();
    let memory_mb = memory_bytes as f64 / ki / ki;
    println!("[Memory Usage]");
    println!(
        "{:<22}{:.2} MB ({} bytes)",
        "Bit Vector Size", memory_mb, memory_bytes
    );
    println!(
        "{:<22}{:.2} bits",
        "Bits per item",
        (memory_bytes * 8) as f64 / n as f64
    );

    // --- Metric 2: Insert Performance ---
    println!("\n[Insertion Performance]");
    let start_insert = Instant::now();
    for item in &dataset {
        bf.insert(item);
    }
    let duration_insert = start_insert.elapsed();
    print_timing(duration_insert, n);

    // --- Metric 3: Worst Case Lookup (Seen Items) ---
    // The worst case for Bloom Filter is when the item has been seen before.
    // The algorithm MUST compute all k hashes and check k bits.
    println!("\n[Lookup Performance - Worst Case (Seen Items)]");
    let start_worst = Instant::now();
    for item in &dataset {
        // Assign the result to a volatile variable to prevent compiler optimization
        let _ = std::hint::black_box(bf.contains(item));
    }
    let duration_worst = start_worst.elapsed();
    print_timing(duration_worst, n);

    // --- Metric 4: Average Case Lookup (Unseen Items) ---
    // In a well-tuned Bloom Filter (50% bits set), an unseen item
    // often fails on the 1st or 2nd bit check.
    println!("\n[Lookup Performance - Average Case (Unseen Items)]");

    // Generate new random items that are likely NOT in the set
    let mut unseen_dataset = Vec::with_capacity(n);
    for _ in 0..n {
        unseen_dataset.push(rng.next_u64());
    }

    let start_avg = Instant::now();
    for item in &unseen_dataset {
        let _ = std::hint::black_box(bf.contains(item));
    }
    let duration_avg = start_avg.elapsed();
    print_timing(duration_avg, n);

    // --- Metric 5: Best Case Lookup (Empty Filter) ---
    // The best case is checking against an empty filter; fails on the 1st bit.
    println!("\n[Lookup Performance - Best Case (Empty Filter)]");
    let empty_bf: BloomFilter<u64> = BloomFilter::new(n, fp_rate);

    let start_best = Instant::now();
    for item in &dataset {
        let _ = std::hint::black_box(empty_bf.contains(item));
    }
    let duration_best = start_best.elapsed();
    print_timing(duration_best, n);

    println!("\n=========================================================\n");
}

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

Inserts an item into the Bloom Filter.

Examples found in repository

examples/simple.rs (line 23)

fn main() {
    // Configuration
    let expected_elements = 100_000;

    // You can initialize with a false positive rate
    let fp_rate = 0.01;
    let mut filter = BloomFilter::new(expected_elements, fp_rate);

    // OR initialize using a specific hash count (commented out example)
    // let hashes = 7u32;
    // let mut filter = BloomFilter::new(expected_elements, hashes);

    println!("Initializing Bloom Filter...");
    println!("Expected elements: {}", expected_elements);
    println!("Target False Positive Rate: {}", fp_rate);
    println!("Actual Hash Count (k): {}", filter.hash_count());

    // Insert data
    println!("Inserting values 0 to {}...", expected_elements);
    for i in 0..expected_elements {
        filter.insert(&i);
    }

    // Check true positives
    println!("Checking 10 known values...");
    let mut present_count = 0;
    for i in 0..10 {
        if filter.contains(&i) {
            present_count += 1;
        }
    }
    println!("Found {}/10 known values (Should be 10)", present_count);

    // Check false positives
    // We check numbers outside the inserted range.
    let check_range_start = expected_elements;
    let check_range_end = expected_elements + 10_000;
    println!(
        "Checking range {} to {} for false positives...",
        check_range_start, check_range_end
    );

    let mut fp_count = 0;
    for i in check_range_start..check_range_end {
        if filter.contains(&i) {
            fp_count += 1;
        }
    }

    let actual_fp_rate = fp_count as f64 / 10_000.0;
    println!("False Positives found: {}", fp_count);
    println!(
        "Actual FP Rate: {:.4} (Target: {})",
        actual_fp_rate, actual_fp_rate
    );
}

examples/benchmark.rs (line 69)

fn run_benchmark(n: usize, fp_rate: f64) {
    // --- Setup ---
    let mut bf = BloomFilter::new(n, fp_rate);
    let mut rng = Random::new(12345);

    println!("\n---------- Bloom Filter Performance Benchmark -----------\n");
    println!("Items:          {}", n);
    println!("Target FP Rate: {}", fp_rate);
    println!("Hash Count:     {}", bf.hash_count());
    println!("\n---------------------------------------------------------\n");

    // Generate data
    let mut dataset = Vec::with_capacity(n);
    for _ in 0..n {
        dataset.push(rng.next_u64());
    }

    // --- Metric 1: Memory Usage ---
    let ki = 1024.0;
    let memory_bytes = bf.memory_usage_bytes();
    let memory_mb = memory_bytes as f64 / ki / ki;
    println!("[Memory Usage]");
    println!(
        "{:<22}{:.2} MB ({} bytes)",
        "Bit Vector Size", memory_mb, memory_bytes
    );
    println!(
        "{:<22}{:.2} bits",
        "Bits per item",
        (memory_bytes * 8) as f64 / n as f64
    );

    // --- Metric 2: Insert Performance ---
    println!("\n[Insertion Performance]");
    let start_insert = Instant::now();
    for item in &dataset {
        bf.insert(item);
    }
    let duration_insert = start_insert.elapsed();
    print_timing(duration_insert, n);

    // --- Metric 3: Worst Case Lookup (Seen Items) ---
    // The worst case for Bloom Filter is when the item has been seen before.
    // The algorithm MUST compute all k hashes and check k bits.
    println!("\n[Lookup Performance - Worst Case (Seen Items)]");
    let start_worst = Instant::now();
    for item in &dataset {
        // Assign the result to a volatile variable to prevent compiler optimization
        let _ = std::hint::black_box(bf.contains(item));
    }
    let duration_worst = start_worst.elapsed();
    print_timing(duration_worst, n);

    // --- Metric 4: Average Case Lookup (Unseen Items) ---
    // In a well-tuned Bloom Filter (50% bits set), an unseen item
    // often fails on the 1st or 2nd bit check.
    println!("\n[Lookup Performance - Average Case (Unseen Items)]");

    // Generate new random items that are likely NOT in the set
    let mut unseen_dataset = Vec::with_capacity(n);
    for _ in 0..n {
        unseen_dataset.push(rng.next_u64());
    }

    let start_avg = Instant::now();
    for item in &unseen_dataset {
        let _ = std::hint::black_box(bf.contains(item));
    }
    let duration_avg = start_avg.elapsed();
    print_timing(duration_avg, n);

    // --- Metric 5: Best Case Lookup (Empty Filter) ---
    // The best case is checking against an empty filter; fails on the 1st bit.
    println!("\n[Lookup Performance - Best Case (Empty Filter)]");
    let empty_bf: BloomFilter<u64> = BloomFilter::new(n, fp_rate);

    let start_best = Instant::now();
    for item in &dataset {
        let _ = std::hint::black_box(empty_bf.contains(item));
    }
    let duration_best = start_best.elapsed();
    print_timing(duration_best, n);

    println!("\n=========================================================\n");
}

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

Checks if an item might be in the Bloom Filter.

Returns true if the item might be present (with a probability of false positive). Returns false if the item is definitely not present.

Examples found in repository

examples/simple.rs (line 30)

fn main() {
    // Configuration
    let expected_elements = 100_000;

    // You can initialize with a false positive rate
    let fp_rate = 0.01;
    let mut filter = BloomFilter::new(expected_elements, fp_rate);

    // OR initialize using a specific hash count (commented out example)
    // let hashes = 7u32;
    // let mut filter = BloomFilter::new(expected_elements, hashes);

    println!("Initializing Bloom Filter...");
    println!("Expected elements: {}", expected_elements);
    println!("Target False Positive Rate: {}", fp_rate);
    println!("Actual Hash Count (k): {}", filter.hash_count());

    // Insert data
    println!("Inserting values 0 to {}...", expected_elements);
    for i in 0..expected_elements {
        filter.insert(&i);
    }

    // Check true positives
    println!("Checking 10 known values...");
    let mut present_count = 0;
    for i in 0..10 {
        if filter.contains(&i) {
            present_count += 1;
        }
    }
    println!("Found {}/10 known values (Should be 10)", present_count);

    // Check false positives
    // We check numbers outside the inserted range.
    let check_range_start = expected_elements;
    let check_range_end = expected_elements + 10_000;
    println!(
        "Checking range {} to {} for false positives...",
        check_range_start, check_range_end
    );

    let mut fp_count = 0;
    for i in check_range_start..check_range_end {
        if filter.contains(&i) {
            fp_count += 1;
        }
    }

    let actual_fp_rate = fp_count as f64 / 10_000.0;
    println!("False Positives found: {}", fp_count);
    println!(
        "Actual FP Rate: {:.4} (Target: {})",
        actual_fp_rate, actual_fp_rate
    );
}

examples/benchmark.rs (line 81)

fn run_benchmark(n: usize, fp_rate: f64) {
    // --- Setup ---
    let mut bf = BloomFilter::new(n, fp_rate);
    let mut rng = Random::new(12345);

    println!("\n---------- Bloom Filter Performance Benchmark -----------\n");
    println!("Items:          {}", n);
    println!("Target FP Rate: {}", fp_rate);
    println!("Hash Count:     {}", bf.hash_count());
    println!("\n---------------------------------------------------------\n");

    // Generate data
    let mut dataset = Vec::with_capacity(n);
    for _ in 0..n {
        dataset.push(rng.next_u64());
    }

    // --- Metric 1: Memory Usage ---
    let ki = 1024.0;
    let memory_bytes = bf.memory_usage_bytes();
    let memory_mb = memory_bytes as f64 / ki / ki;
    println!("[Memory Usage]");
    println!(
        "{:<22}{:.2} MB ({} bytes)",
        "Bit Vector Size", memory_mb, memory_bytes
    );
    println!(
        "{:<22}{:.2} bits",
        "Bits per item",
        (memory_bytes * 8) as f64 / n as f64
    );

    // --- Metric 2: Insert Performance ---
    println!("\n[Insertion Performance]");
    let start_insert = Instant::now();
    for item in &dataset {
        bf.insert(item);
    }
    let duration_insert = start_insert.elapsed();
    print_timing(duration_insert, n);

    // --- Metric 3: Worst Case Lookup (Seen Items) ---
    // The worst case for Bloom Filter is when the item has been seen before.
    // The algorithm MUST compute all k hashes and check k bits.
    println!("\n[Lookup Performance - Worst Case (Seen Items)]");
    let start_worst = Instant::now();
    for item in &dataset {
        // Assign the result to a volatile variable to prevent compiler optimization
        let _ = std::hint::black_box(bf.contains(item));
    }
    let duration_worst = start_worst.elapsed();
    print_timing(duration_worst, n);

    // --- Metric 4: Average Case Lookup (Unseen Items) ---
    // In a well-tuned Bloom Filter (50% bits set), an unseen item
    // often fails on the 1st or 2nd bit check.
    println!("\n[Lookup Performance - Average Case (Unseen Items)]");

    // Generate new random items that are likely NOT in the set
    let mut unseen_dataset = Vec::with_capacity(n);
    for _ in 0..n {
        unseen_dataset.push(rng.next_u64());
    }

    let start_avg = Instant::now();
    for item in &unseen_dataset {
        let _ = std::hint::black_box(bf.contains(item));
    }
    let duration_avg = start_avg.elapsed();
    print_timing(duration_avg, n);

    // --- Metric 5: Best Case Lookup (Empty Filter) ---
    // The best case is checking against an empty filter; fails on the 1st bit.
    println!("\n[Lookup Performance - Best Case (Empty Filter)]");
    let empty_bf: BloomFilter<u64> = BloomFilter::new(n, fp_rate);

    let start_best = Instant::now();
    for item in &dataset {
        let _ = std::hint::black_box(empty_bf.contains(item));
    }
    let duration_best = start_best.elapsed();
    print_timing(duration_best, n);

    println!("\n=========================================================\n");
}

pub fn clear(&mut self)

Clears all bits in the filter.

pub fn memory_usage_bytes(&self) -> usize

Returns the approximate memory usage of the bit vector in bytes.

Examples found in repository

examples/benchmark.rs (line 52)

fn run_benchmark(n: usize, fp_rate: f64) {
    // --- Setup ---
    let mut bf = BloomFilter::new(n, fp_rate);
    let mut rng = Random::new(12345);

    println!("\n---------- Bloom Filter Performance Benchmark -----------\n");
    println!("Items:          {}", n);
    println!("Target FP Rate: {}", fp_rate);
    println!("Hash Count:     {}", bf.hash_count());
    println!("\n---------------------------------------------------------\n");

    // Generate data
    let mut dataset = Vec::with_capacity(n);
    for _ in 0..n {
        dataset.push(rng.next_u64());
    }

    // --- Metric 1: Memory Usage ---
    let ki = 1024.0;
    let memory_bytes = bf.memory_usage_bytes();
    let memory_mb = memory_bytes as f64 / ki / ki;
    println!("[Memory Usage]");
    println!(
        "{:<22}{:.2} MB ({} bytes)",
        "Bit Vector Size", memory_mb, memory_bytes
    );
    println!(
        "{:<22}{:.2} bits",
        "Bits per item",
        (memory_bytes * 8) as f64 / n as f64
    );

    // --- Metric 2: Insert Performance ---
    println!("\n[Insertion Performance]");
    let start_insert = Instant::now();
    for item in &dataset {
        bf.insert(item);
    }
    let duration_insert = start_insert.elapsed();
    print_timing(duration_insert, n);

    // --- Metric 3: Worst Case Lookup (Seen Items) ---
    // The worst case for Bloom Filter is when the item has been seen before.
    // The algorithm MUST compute all k hashes and check k bits.
    println!("\n[Lookup Performance - Worst Case (Seen Items)]");
    let start_worst = Instant::now();
    for item in &dataset {
        // Assign the result to a volatile variable to prevent compiler optimization
        let _ = std::hint::black_box(bf.contains(item));
    }
    let duration_worst = start_worst.elapsed();
    print_timing(duration_worst, n);

    // --- Metric 4: Average Case Lookup (Unseen Items) ---
    // In a well-tuned Bloom Filter (50% bits set), an unseen item
    // often fails on the 1st or 2nd bit check.
    println!("\n[Lookup Performance - Average Case (Unseen Items)]");

    // Generate new random items that are likely NOT in the set
    let mut unseen_dataset = Vec::with_capacity(n);
    for _ in 0..n {
        unseen_dataset.push(rng.next_u64());
    }

    let start_avg = Instant::now();
    for item in &unseen_dataset {
        let _ = std::hint::black_box(bf.contains(item));
    }
    let duration_avg = start_avg.elapsed();
    print_timing(duration_avg, n);

    // --- Metric 5: Best Case Lookup (Empty Filter) ---
    // The best case is checking against an empty filter; fails on the 1st bit.
    println!("\n[Lookup Performance - Best Case (Empty Filter)]");
    let empty_bf: BloomFilter<u64> = BloomFilter::new(n, fp_rate);

    let start_best = Instant::now();
    for item in &dataset {
        let _ = std::hint::black_box(empty_bf.contains(item));
    }
    let duration_best = start_best.elapsed();
    print_timing(duration_best, n);

    println!("\n=========================================================\n");
}

pub fn hash_count(&self) -> u32

Returns the number of hash functions (k) being used.

Examples found in repository

examples/simple.rs (line 18)

fn main() {
    // Configuration
    let expected_elements = 100_000;

    // You can initialize with a false positive rate
    let fp_rate = 0.01;
    let mut filter = BloomFilter::new(expected_elements, fp_rate);

    // OR initialize using a specific hash count (commented out example)
    // let hashes = 7u32;
    // let mut filter = BloomFilter::new(expected_elements, hashes);

    println!("Initializing Bloom Filter...");
    println!("Expected elements: {}", expected_elements);
    println!("Target False Positive Rate: {}", fp_rate);
    println!("Actual Hash Count (k): {}", filter.hash_count());

    // Insert data
    println!("Inserting values 0 to {}...", expected_elements);
    for i in 0..expected_elements {
        filter.insert(&i);
    }

    // Check true positives
    println!("Checking 10 known values...");
    let mut present_count = 0;
    for i in 0..10 {
        if filter.contains(&i) {
            present_count += 1;
        }
    }
    println!("Found {}/10 known values (Should be 10)", present_count);

    // Check false positives
    // We check numbers outside the inserted range.
    let check_range_start = expected_elements;
    let check_range_end = expected_elements + 10_000;
    println!(
        "Checking range {} to {} for false positives...",
        check_range_start, check_range_end
    );

    let mut fp_count = 0;
    for i in check_range_start..check_range_end {
        if filter.contains(&i) {
            fp_count += 1;
        }
    }

    let actual_fp_rate = fp_count as f64 / 10_000.0;
    println!("False Positives found: {}", fp_count);
    println!(
        "Actual FP Rate: {:.4} (Target: {})",
        actual_fp_rate, actual_fp_rate
    );
}

examples/benchmark.rs (line 41)

fn run_benchmark(n: usize, fp_rate: f64) {
    // --- Setup ---
    let mut bf = BloomFilter::new(n, fp_rate);
    let mut rng = Random::new(12345);

    println!("\n---------- Bloom Filter Performance Benchmark -----------\n");
    println!("Items:          {}", n);
    println!("Target FP Rate: {}", fp_rate);
    println!("Hash Count:     {}", bf.hash_count());
    println!("\n---------------------------------------------------------\n");

    // Generate data
    let mut dataset = Vec::with_capacity(n);
    for _ in 0..n {
        dataset.push(rng.next_u64());
    }

    // --- Metric 1: Memory Usage ---
    let ki = 1024.0;
    let memory_bytes = bf.memory_usage_bytes();
    let memory_mb = memory_bytes as f64 / ki / ki;
    println!("[Memory Usage]");
    println!(
        "{:<22}{:.2} MB ({} bytes)",
        "Bit Vector Size", memory_mb, memory_bytes
    );
    println!(
        "{:<22}{:.2} bits",
        "Bits per item",
        (memory_bytes * 8) as f64 / n as f64
    );

    // --- Metric 2: Insert Performance ---
    println!("\n[Insertion Performance]");
    let start_insert = Instant::now();
    for item in &dataset {
        bf.insert(item);
    }
    let duration_insert = start_insert.elapsed();
    print_timing(duration_insert, n);

    // --- Metric 3: Worst Case Lookup (Seen Items) ---
    // The worst case for Bloom Filter is when the item has been seen before.
    // The algorithm MUST compute all k hashes and check k bits.
    println!("\n[Lookup Performance - Worst Case (Seen Items)]");
    let start_worst = Instant::now();
    for item in &dataset {
        // Assign the result to a volatile variable to prevent compiler optimization
        let _ = std::hint::black_box(bf.contains(item));
    }
    let duration_worst = start_worst.elapsed();
    print_timing(duration_worst, n);

    // --- Metric 4: Average Case Lookup (Unseen Items) ---
    // In a well-tuned Bloom Filter (50% bits set), an unseen item
    // often fails on the 1st or 2nd bit check.
    println!("\n[Lookup Performance - Average Case (Unseen Items)]");

    // Generate new random items that are likely NOT in the set
    let mut unseen_dataset = Vec::with_capacity(n);
    for _ in 0..n {
        unseen_dataset.push(rng.next_u64());
    }

    let start_avg = Instant::now();
    for item in &unseen_dataset {
        let _ = std::hint::black_box(bf.contains(item));
    }
    let duration_avg = start_avg.elapsed();
    print_timing(duration_avg, n);

    // --- Metric 5: Best Case Lookup (Empty Filter) ---
    // The best case is checking against an empty filter; fails on the 1st bit.
    println!("\n[Lookup Performance - Best Case (Empty Filter)]");
    let empty_bf: BloomFilter<u64> = BloomFilter::new(n, fp_rate);

    let start_best = Instant::now();
    for item in &dataset {
        let _ = std::hint::black_box(empty_bf.contains(item));
    }
    let duration_best = start_best.elapsed();
    print_timing(duration_best, n);

    println!("\n=========================================================\n");
}

Trait Implementations

impl<T: Clone + ?Sized> Clone for BloomFilter<T>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug + ?Sized> Debug for BloomFilter<T>

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

Formats the value using the given formatter.