Hash map or array?
“When would you use a hash map instead of an array, and when is an array the better choice?”
What this tests
- Whether the candidate understands that both offer
O(1)access but on different key domains. - Awareness of the hidden costs of hashing: constants, memory overhead, worst-case collisions.
- Ability to spot when keys are dense small integers and an array is strictly better.
- Understanding of ordering guarantees.
Strong answer
An Array gives O(1) access when the key is an index: a dense range of small non-negative integers. A Hash Map gives expected O(1) access for arbitrary keys — strings, sparse integers, tuples — by computing an index from the key. So the first question is "what is my key domain?"
A strong candidate names the costs of the hash map: hashing every key, pointer chasing on collisions, typically 2–4× the memory of a packed array, no ordering, and an O(n) worst case under adversarial keys. When keys are characters (26 letters) or values bounded by 10^5, an array of counts is faster, smaller, cache friendly, and deterministic.
They also mention ordering: an array preserves insertion order and supports range scans, which a hash map does not. If the problem needs "the k-th element" or "everything between a and b", an array (possibly sorted) or a tree is right; if it needs "does key x exist", a hash map or set is right.
Green flags · Red flags
- Asks what the keys are before choosing.
- Says a frequency array of size 26 or 128 beats a hash map for characters.
- Mentions memory overhead and cache behaviour, not just big-O.
- Knows hash map
O(1)is expected, not worst case. - Notes that arrays keep order and hash maps do not.
- Says hash maps are "always O(1)" with no qualification.
- Uses a hash map for keys
0..25without noticing an array would do. - Believes arrays require knowing the size and therefore are never usable dynamically.
- Cannot explain what a hash function does.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
0..100. Which do you pick?10^9 but there are only 10^4 of them.