spider_util/
bloom_filter.rs

1//! # Bloom Filter Module
2//!
3//! Implements a memory-efficient Bloom Filter for duplicate URL detection.
4//!
5//! ## Overview
6//!
7//! The Bloom Filter module provides an efficient probabilistic data structure
8//! for testing whether an element is a member of a set. In the context of web
9//! crawling, it's used to quickly check if a URL has potentially been visited
10//! before, significantly reducing the need for expensive lookups in the main
11//! visited URLs cache. The filter trades a small probability of false positives
12//! for substantial memory savings and performance gains.
13//!
14//! ## Key Components
15//!
16//! - **BloomFilter**: Main struct implementing the Bloom Filter algorithm
17//! - **Bit Vector**: Memory-efficient storage using a vector of 64-bit integers
18//! - **Hash Functions**: Multiple hash functions using double hashing technique
19//! - **Might Contain**: Probabilistic membership testing method
20//!
21//! ## Algorithm Details
22//!
23//! The implementation uses a bit vector for memory efficiency and applies double
24//! hashing to generate multiple hash values from two initial hash functions.
25//! This approach reduces the computational overhead of calculating multiple
26//! independent hash functions while maintaining good distribution properties.
27//! The filter supports configurable size and number of hash functions.
28//!
29//! ## Example
30//!
31//! ```rust,ignore
32//! use spider_util::bloom_filter::BloomFilter;
33//!
34//! // Create a Bloom Filter with capacity for ~1M items and 5 hash functions
35//! let mut bloom_filter = BloomFilter::new(5_000_000, 5);
36//!
37//! // Add items to the filter
38//! bloom_filter.add("https://example.com/page1");
39//! bloom_filter.add("https://example.com/page2");
40//!
41//! // Check if items might be in the set (with possibility of false positives)
42//! assert_eq!(bloom_filter.might_contain("https://example.com/page1"), true);
43//! assert_eq!(bloom_filter.might_contain("https://example.com/nonexistent"), false); // Likely, but not guaranteed
44//! ```
45
46use seahash::hash;
47use std::collections::hash_map::DefaultHasher;
48use std::hash::{Hash, Hasher};
49
50/// A proper Bloom Filter implementation using a bit vector for memory efficiency.
51/// This is used for efficiently checking if a URL has potentially been visited before,
52/// reducing the need for expensive lookups in the main visited URLs cache.
53pub struct BloomFilter {
54    bit_set: Vec<u64>,
55    num_bits: u64,
56    hash_functions: usize,
57}
58
59impl BloomFilter {
60    /// Creates a new BloomFilter with the specified capacity and number of hash functions.
61    pub fn new(num_bits: u64, hash_functions: usize) -> Self {
62        let size = ((num_bits as f64 / 64.0).ceil() as usize).max(1);
63        Self {
64            bit_set: vec![0; size],
65            num_bits,
66            hash_functions,
67        }
68    }
69
70    /// Adds an item to the BloomFilter.
71    pub fn add(&mut self, item: &str) {
72        for i in 0..self.hash_functions {
73            let index = self.get_bit_index(item, i);
74            let bucket_idx = (index / 64) as usize;
75            let bit_idx = (index % 64) as usize;
76
77            if bucket_idx < self.bit_set.len() {
78                self.bit_set[bucket_idx] |= 1u64 << bit_idx;
79            }
80        }
81    }
82
83    /// Checks if an item might be in the BloomFilter.
84    /// Returns true if the item might be in the set, false if it definitely isn't.
85    pub fn might_contain(&self, item: &str) -> bool {
86        for i in 0..self.hash_functions {
87            let index = self.get_bit_index(item, i);
88            let bucket_idx = (index / 64) as usize;
89            let bit_idx = (index % 64) as usize;
90
91            if bucket_idx >= self.bit_set.len() {
92                return false;
93            }
94
95            if (self.bit_set[bucket_idx] & (1u64 << bit_idx)) == 0 {
96                return false;
97            }
98        }
99        true
100    }
101
102    /// Calculates the bit index for an item using double hashing technique.
103    fn get_bit_index(&self, item: &str, i: usize) -> u64 {
104        let mut hasher = DefaultHasher::new();
105        item.hash(&mut hasher);
106        let hash1 = hasher.finish();
107
108        let combined = format!("{}{}", item, i);
109        let hash2 = hash(combined.as_bytes());
110
111        let combined_hash = hash1.wrapping_add((i as u64).wrapping_mul(hash2));
112        combined_hash % self.num_bits
113    }
114}
spider_util/bloom_filter.rs

spider_util/
bloom_filter.rs
