spider_util/
bloom.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;
47
48/// A proper Bloom Filter implementation using a bit vector for memory efficiency.
49/// This is used for efficiently checking if a URL has potentially been visited before,
50/// reducing the need for expensive lookups in the main visited URLs cache.
51pub struct BloomFilter {
52    bit_set: Vec<u64>,
53    num_bits: u64,
54    hash_functions: usize,
55}
56
57impl BloomFilter {
58    /// Creates a new BloomFilter with the specified capacity and number of hash functions.
59    pub fn new(num_bits: u64, hash_functions: usize) -> Self {
60        let size = ((num_bits as f64 / 64.0).ceil() as usize).max(1);
61        Self {
62            bit_set: vec![0; size],
63            num_bits,
64            hash_functions,
65        }
66    }
67
68    /// Adds an item to the BloomFilter.
69    pub fn add(&mut self, item: &str) {
70        // Pre-compute hash of the item once
71        let item_bytes = item.as_bytes();
72        let hash1 = seahash::hash(item_bytes);
73        
74        for i in 0..self.hash_functions {
75            // Use double hashing: h(i) = hash1 + i * hash2
76            // hash2 is derived from the item and index without string concatenation
77            let hash2 = hash(&i.to_ne_bytes());
78            let combined_hash = hash1.wrapping_add((i as u64).wrapping_mul(hash2));
79            let index = combined_hash % self.num_bits;
80            
81            let bucket_idx = (index / 64) as usize;
82            let bit_idx = (index % 64) as usize;
83
84            if bucket_idx < self.bit_set.len() {
85                self.bit_set[bucket_idx] |= 1u64 << bit_idx;
86            }
87        }
88    }
89
90    /// Checks if an item might be in the BloomFilter.
91    /// Returns true if the item might be in the set, false if it definitely isn't.
92    pub fn might_contain(&self, item: &str) -> bool {
93        let item_bytes = item.as_bytes();
94        let hash1 = seahash::hash(item_bytes);
95        
96        for i in 0..self.hash_functions {
97            let hash2 = hash(&i.to_ne_bytes());
98            let combined_hash = hash1.wrapping_add((i as u64).wrapping_mul(hash2));
99            let index = combined_hash % self.num_bits;
100            
101            let bucket_idx = (index / 64) as usize;
102            let bit_idx = (index % 64) as usize;
103
104            if bucket_idx >= self.bit_set.len() {
105                return false;
106            }
107
108            if (self.bit_set[bucket_idx] & (1u64 << bit_idx)) == 0 {
109                return false;
110            }
111        }
112        true
113    }
114}
spider_util/bloom.rs

spider_util/
bloom.rs
