Bloom Filter
PerformanceA tiny, probabilistic 'have I possibly seen this before?' data structure — no false negatives, but occasional false positives, in exchange for huge memory savings.
A Bloom filter is a compact bit array plus several hash functions, used to test set membership. Insert an item by hashing it k different ways and setting those k bits; to check membership, hash the query the same k ways and see if all those bits are set. If any bit is 0, the item is *definitely* not in the set (no false negatives). If all bits are 1, the item is *probably* in the set (possible false positive, tunable by array size/hash count) — but it uses a small constant amount of memory regardless of how large or how long the strings you're storing are, unlike a hash set which stores the actual data.
How it connects
Bloom Filter as the source, with the components it typically interacts with.
- → Database Types (SQL, NoSQL & Beyond): Bloom filters sit in front of on-disk lookups (e.g. LSM-tree SSTables in Cassandra/RocksDB) to skip disk reads for keys that definitely don't exist.
- → Caching: A bloom filter can guard a cache to avoid caching/looking up known-absent keys, cutting down on wasted cache-miss round trips.
- → Search & Indexing (Inverted Index): Search engines use bloom filters per segment to quickly rule out segments that can't contain a given term before doing real disk I/O.