Is k-hash or k-independent truly required, or can I use one hash with k-fold output?
Theoretically, k-independent hashing is optimal. In practice, a single strong hash function with k different seeds or outputs per seed (via a counter or slice offset) works well and often performs better than k separate hash implementations due to CPU cache locality.
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.