use crate::hashing::double_hash;
pub struct BloomFilter {
bits: Vec<u64>,
m: usize, // number of bits
k: u32, // number of hash probes
}
impl BloomFilter {
pub fn with_params(n: usize, p: f64) -> Self {
let ln2 = std::f64::consts::LN_2;
let m = (-(n as f64) * p.ln() / (ln2 * ln2)).ceil() as usize;
let k = ((m as f64 / n as f64) * ln2).round().max(1.0) as u32;
let words = (m + 63) / 64;
BloomFilter { bits: vec![0u64; words], m, k }
}
fn indices(&self, key: &str) -> impl Iterator<Item = usize> + '_ {
let (h1, h2) = double_hash(key);
let m = self.m as u64;
(0..self.k as u64).map(move |i| (h1.wrapping_add(i.wrapping_mul(h2)) % m) as usize)
}
pub fn insert(&mut self, key: &str) {
for idx in self.indices(key) {
self.bits[idx / 64] |= 1u64 << (idx % 64);
}
}
pub fn contains(&self, key: &str) -> bool {
self.indices(key).all(|idx| self.bits[idx / 64] & (1u64 << (idx % 64)) != 0)
}
}
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
fn seeded_hash(key: &str, seed: u64) -> u64 {
let mut hasher = DefaultHasher::new();
seed.hash(&mut hasher);
key.hash(&mut hasher);
hasher.finish()
}
pub fn double_hash(key: &str) -> (u64, u64) {
let h1 = seeded_hash(key, 0x9E3779B97F4A7C15);
let mut h2 = seeded_hash(key, 0xC2B2AE3D27D4EB4F);
// h2 must be non-zero so probes don't all collapse to h1
if h2 == 0 {
h2 = 1;
}
(h1, h2)
}
use crate::bloom::BloomFilter;
use std::collections::VecDeque;
use std::sync::Mutex;
pub struct UrlFrontier {
inner: Mutex<Inner>,
}
struct Inner {
seen: BloomFilter,
queue: VecDeque<String>,
}
impl UrlFrontier {
pub fn new(expected_urls: usize, false_positive_rate: f64) -> Self {
UrlFrontier {
inner: Mutex::new(Inner {
seen: BloomFilter::with_params(expected_urls, false_positive_rate),
queue: VecDeque::new(),
}),
}
}
pub fn add_url(&self, raw: &str) -> bool {
let url = normalize(raw);
let mut inner = self.inner.lock().unwrap();
if inner.seen.contains(&url) {
return false;
}
inner.seen.insert(&url);
inner.queue.push_back(url);
true
}
pub fn next_url(&self) -> Option<String> {
self.inner.lock().unwrap().queue.pop_front()
}
}
fn normalize(raw: &str) -> String {
let trimmed = raw.trim().trim_end_matches('/');
trimmed.to_ascii_lowercase()
}
A bloom filter is a compact probabilistic set: it answers "have I seen this URL?" using a fraction of the memory a HashSet<String> would need, at the cost of occasional false positives (it may claim to have seen a URL it hasn't) but never false negatives. This makes it ideal for a crawler frontier, where the goal is to avoid re-fetching pages and a rare skipped-but-actually-new URL is an acceptable trade for keeping billions of visited URLs in RAM.
In bloom.rs, the filter is a bit vector (Vec<u64> used as packed bits) plus k independent hash positions per key. Rather than instantiating k real hash functions, the code uses the Kirsch–Mitzenmacher double-hashing trick: two base hashes h1 and h2 are combined as h1.wrapping_add(i * h2) to derive each of the k indices. BloomFilter::with_params sizes the bit array m and derives k from the target item count n and desired false-positive rate p using the standard formulas m = -n·ln(p)/ln(2)^2 and k = (m/n)·ln(2). insert sets bits; contains returns false only if any bit is unset, which is the guarantee that underpins zero false negatives.
hashing.rs isolates the two base hashes so the filter stays agnostic about the algorithm. It uses DefaultHasher seeded with two different constants, giving statistically independent 64-bit values — cheap and dependency-free, though a production system might prefer a faster non-cryptographic hash like xxHash.
frontier.rs shows the real use: UrlFrontier wraps the filter with a queue and a Mutex so worker threads can call add_url concurrently. The critical detail is contains-then-insert under one lock, avoiding a race where two threads both enqueue the same URL. It also normalizes URLs before hashing so trivial variations collapse to one key.
The main pitfall to remember: a bloom filter cannot delete or resize cleanly, and its accuracy degrades as it fills past the design capacity n, so with_params must be sized for the expected crawl volume up front. When false positives become intolerable, engineers reach for a counting or scalable bloom variant instead.
Related snips
use crossbeam::channel::unbounded;
use std::thread;
fn main() {
let (tx, rx) = unbounded();Crossbeam for advanced concurrent data structures
// Creating a Promise
const myPromise = new Promise((resolve, reject) => {
const success = true;
setTimeout(() => {
if (success) {Promises and async/await patterns for asynchronous JavaScript
use std::sync::mpsc;
use std::thread;
fn main() {
let (tx, rx) = mpsc::channel();Channels (mpsc) for message passing between threads
export type Settled<R> =
| { status: 'fulfilled'; value: R }
| { status: 'rejected'; reason: unknown };
export interface ConcurrencyOptions {
limit: number;Simple concurrency limiter for batch operations
package pools
import (
"bytes"
"sync"
)sync.Pool for bytes.Buffer to reduce allocations in hot paths
import Foundation
import UIKit
class ImageProcessor {
// Background processing with main thread updates
func processImage(_ image: UIImage, completion: @escaping (UIImage?) -> Void) {Grand Central Dispatch for concurrency
Share this code
Here's the card — post it anywhere.
