Bloom Filter
A Bloom filter approximates set membership with k hash functions and a bit array, offering space efficiency at the cost of a false-positive rate.
Purpose
To provide space-efficient approximate membership queries for caches and databases.
Mechanism
Insert: hash the element with k functions and set the corresponding bits. Query: if all k bits are 1 the element is probably present (false-positive rate p≈(1-e^(-kn/m))^k). It never yields false negatives. Deletion is unsupported in the standard version.
Use cases
- Cache filtering
- Database query optimization
- Deduplication