Bloom Filters

overview

Summary

Bloom filters are probabilistic data structures for fast set membership tests with tiny memory. They use a bit array and k independent hash functions. Insertion sets k bits; queries check those bits. Results can yield false positives but never false negatives, and standard versions do not support deletes. Choose bit-array size m and number of hashes k to meet a target false positive rate. Common uses include databases, caches, and networking. Time is O(k) per operation with compact O(m) space.