Why not just use a set or database index if disk and CPU are cheap?
Sets and indices work at application level but require memory (O(n) pointers) and serialize lookups through the software stack, causing context switches and cache misses. A Bloom filter in RAM answers with a single CPU op per hash function—millions per second with zero I/O, making it ideal for high-frequency checks like username uniqueness.
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.