How does a hash map handle collisions?
A collision happens when two keys hash to the same bucket. Chaining stores colliding entries in a list inside the bucket; open addressing probes for the next free slot. Both keep lookups near O(1) on average if the table stays sparse.
Explain it simply
A hash map is like a wall of pigeonholes in a college office, one per department. A hash function turns a key (say, a student roll number) into a pigeonhole number. Two different roll numbers can land on the same number. That clash is a collision.
There are two common fixes:
- Chaining: each pigeonhole holds a small list. Colliding keys are added to that list, and a lookup scans only that short list.
- Open addressing: if the pigeonhole is taken, probe the next one (linear probing) or follow another fixed pattern until a free slot is found.
To keep chains short, the table tracks its load factor (entries divided by buckets) and resizes, usually doubling, when it gets too full.
Example
put("roll 17") -> hash -> bucket 3 (empty) -> store
put("roll 42") -> hash -> bucket 3 (collision) -> chain: [17, 42]
get("roll 42") -> bucket 3 -> scan chain -> foundWhat to say in the interview
"A collision is two keys mapping to the same bucket. Chaining keeps a list per bucket; open addressing probes for another slot. With a good hash function and a bounded load factor, operations are O(1) on average, but a poor hash or many collisions can degrade to O(n) in the worst case."
Common mistakes
- Saying a hash map is always O(1). It is O(1) on average, O(n) in the worst case.
- Believing collisions mean data is lost. A correct hash map stores both entries.