When a hash map is the wrong choice
“Hash maps are the default answer to many problems. Describe situations where a hash map is the wrong choice and what you would use instead.”
What this tests
- Whether the candidate understands what a hash map cannot do (order, ranges, predecessor).
- Awareness of worst-case behaviour and memory cost.
- Recognition that small integer keys make an array strictly better.
- Ability to name the right replacement for each shortcoming.
Strong answer
A Hash Map answers exactly one question fast: "what is stored under key k?" It fails in four situations. Ordering: it cannot give the smallest key, the next larger key, or all keys in a range. Those need a sorted structure — a balanced BST such as a Red-Black Tree for dynamic data, or a sorted array with Binary Search for static data, or a Min-Heap if only the minimum is needed.
Worst case: expected O(1) becomes O(n) under collisions, and adversarial inputs can trigger it deliberately. If latency guarantees matter, a balanced tree with O(log n) worst case is safer. Memory: buckets, pointers, and load factor headroom make a hash map several times larger than a packed array; for 10^7 entries that can be the difference between fitting in memory or not. Small integer keys: when keys are in 0..k for small k — characters, digits, bounded ids — a plain array is faster, denser, and iterates in order. Using a hash map here is a mild red flag in itself.
A strong candidate adds a fifth: hash maps hash the whole key, so they cannot answer prefix queries — "all words starting with pre" — which is what a Trie is for. And for "is this element probably present" over enormous sets with tolerable false positives, a Bloom Filter uses a fraction of the memory.
Green flags · Red flags
- Names ordering/range/predecessor queries as the primary limitation and the BST as the fix.
- Mentions worst-case degradation and when it matters.
- Quantifies memory overhead rather than saying "more memory".
- Swaps in an array for small integer keys without prompting.
- Mentions tries for prefix queries or bloom filters for membership at scale.
- Cannot name any situation where a hash map is wrong.
- Thinks a hash map keeps keys sorted.
- Suggests sorting the hash map's keys on every query to get order.
- Uses a hash map for a 26-letter frequency count without comment.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
O(log n) insert and "smallest element ≥ x".O(1) insert, delete, and random element.10^8 integer keys is out of memory. Options?