Bloom Filter

Definitions

1. A space-efficient probabilistic data structure that tests whether an element is a member of a set. Can return false positives ('maybe in set') but never false negatives ('definitely not in set'). Uses multiple hash functions mapping to a bit array. Used by databases (skip disk reads), CDNs (cache presence), and spell checkers.

   In plain English: A memory-efficient way to quickly check if something is NOT in a set, with a small chance of false 'maybe yes' answers.

   Example: "Check the Bloom filter before hitting the database — if it says the key doesn't exist, it definitely doesn't. Saves 90% of unnecessary lookups."

Related Terms

• Allocator
• Array
• Big-O
• Binary Tree
• Hash Table
• Skip List
• Ring Buffer
• LRU Cache