How many hash functions and how large should the bit array be?
The optimal number of hash functions is ln(2) × (m/n), where m is array size and n is expected elements. For 1% false positives, you need roughly 9.6 bits per element; for 0.1%, roughly 14.4 bits. A 10 million element set with 1% FP rate needs only ~12 MB.
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 does an index's internal data structure matter if it all ends up 'faster than a scan'?
- Why is disk I/O the thing index structures are actually optimizing for?
- Why can't a hash index handle range queries?
- What makes a bitmap index different from a B-tree, and when is it better?
- Why do B-trees stay balanced automatically as data is inserted?
- Why does a database need an index at all — why can't it just scan the table?
- When is a hash index better than a B-tree index?
- What is a composite index and why does column order matter?
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.