How does a Bloom filter guarantee no false negatives but allow false positives?
A key is added by hashing it through k functions and setting k bits to 1. On lookup, if ANY of the k bits is 0, the key is definitively absent (no false negatives). But all k bits being 1 proves nothing—other keys may have set those same bits. False positives are possible.
Answered in
Bloom Filters: The One-Way Membership TestA probabilistic data structure: zero false negatives, tunable false positives. Check membership in RAM with bits instead of database queries.
Read the full analysisOther questions this article answers
More system design questions
- Why doesn't Google just run Dijkstra faster?
- What is a shortcut edge and when is it precomputed?
- How much space do shortcut edges take compared to the original graph?
- Can Contraction Hierarchies handle dynamic graphs like traffic or road closure?
- Why contract low-degree nodes first instead of high-degree ones?
- What is a CRDT and why does it matter for real-time collaboration?
- How do CRDTs handle concurrent edits without a central server referee?
- Why did Figma move from operational transforms to CRDTs?
Every answer on Crashtech is written by the editor of the article it comes from — never auto-summarised. Browse all answers or the System Design beat.