Bloom filters

A Bloom filter answers 'have I seen this item?' using very little memory, at the price of occasional mistakes in one direction. It's a bit array, all zeros at the start, plus k hash functions. To add an item, hash it k times and set those k bits to 1. To check an item, hash it the same way: if any of its bits is 0, it was definitely never added. If all are 1, it was probably added.

The 'probably' is because other items may have set those same bits. So a Bloom filter can give false positives but never false negatives. It can't list its items, and plain Bloom filters can't delete them (clearing a bit could erase another item).

import hashlib
class Bloom:
    def __init__(self, m=1024, k=3):
        self.m, self.k, self.bits = m, k, bytearray(m)
    def _idx(self, item):
        for i in range(self.k):
            h = hashlib.sha256(f"{i}:{item}".encode()).digest()
            yield int.from_bytes(h[:8], "big") % self.m
    def add(self, item):
        for i in self._idx(item): self.bits[i] = 1
    def maybe_contains(self, item):
        return all(self.bits[i] for i in self._idx(item))

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
struct Bloom { bits: Vec<bool>, k: u64 }
impl Bloom {
    fn idx<T: Hash>(&self, item: &T, i: u64) -> usize {
        let mut h = DefaultHasher::new();
        i.hash(&mut h); item.hash(&mut h);
        (h.finish() % self.bits.len() as u64) as usize
    }
    fn add<T: Hash>(&mut self, item: &T) {
        for i in 0..self.k { let j = self.idx(item, i); self.bits[j] = true; }
    }
    fn maybe_contains<T: Hash>(&self, item: &T) -> bool {
        (0..self.k).all(|i| self.bits[self.idx(item, i)])
    }
}

The false-positive rate depends on how full the bit array is. More bits per item means fewer collisions. A common rule of thumb: about 10 bits per item with about 7 hash functions gives roughly a 1% false-positive rate. Compare that with storing each item: a URL might take 50–100 bytes, while the filter needs about 1.2 bytes per URL.

As you add items beyond what the filter was sized for, more bits become 1 and the false-positive rate climbs towards 100%. So you size the filter for the expected number of items in advance. Use a Bloom filter as a cheap first check in front of something expensive and exact, never as the final answer when a wrong 'yes' matters.