42. What is a Bloom filter?
HardSymbol tables & hashing
Technical
Show model answer
A Bloom filter is a bit array plus k hash functions. Adding an item sets k bits; a lookup checks those bits. It can return false positives ("maybe present") but never false negatives, using far less memory than storing the items. Uses: avoiding unnecessary disk reads, caching, and spam or URL checks.