What is a hash collision and how do chaining and open addressing handle it?
A hash collision occurs when two distinct keys produce the same hash value modulo the table size, and therefore map to the same bucket. Because hash functions compress a large key space into a small fixed-size array, collisions are inevitable -- by the birthday paradox, they become likely well before the table is full.
Chaining (separate chaining) resolves collisions by allowing each bucket to hold multiple entries. Each bucket is the head of a linked list (or in modern implementations, a dynamic array or tree). When two keys hash to the same bucket, both are appended to that bucket's list. Lookup requires computing the hash, jumping to the bucket, then linearly scanning the list for the matching key. Average-case time complexity is O(1) when load factor is low. Worst case -- all keys in one bucket -- degrades to O(n). Java's HashMap uses chaining and switches each bucket's list to a red-black tree when the bucket exceeds 8 entries, keeping worst-case lookup at O(log n).
Open addressing resolves collisions by finding a different slot within the same array. When a collision occurs, the algorithm probes a sequence of slots until it finds an empty one. The three main probe strategies are: linear probing (check next slot), quadratic probing (jump by i-squared positions), and double hashing (use a second hash function to determine jump size). Open addressing avoids the overhead of pointer-chasing and is more cache-friendly because all data stays in a contiguous array. However, it is sensitive to load factor -- performance degrades rapidly above 70-80% occupancy. Deletions are also more complex: you cannot simply mark a slot empty or you will break probe chains; you must use a tombstone marker. Python's dict uses open addressing with a compact table and pseudo-random probing derived from the key's hash.
| Aspect | Chaining | Open Addressing |
|---|---|---|
| Storage | Linked lists or arrays per bucket (extra allocations) | All data in one contiguous array |
| Cache performance | Worse -- pointer-chasing to list nodes | Better -- sequential memory access |
| Load factor tolerance | Can exceed 1.0; degrades gracefully | Degrades sharply above ~70-80% |
| Deletion | Simple -- remove node from list | Complex -- requires tombstone markers |
| Worst-case lookup | O(n) per bucket (O(log n) with tree buckets) | O(n) with severe clustering |
| Memory overhead | Higher -- pointers + allocations per entry | Lower -- no extra allocation per entry |
| Real-world usage | Java HashMap, most hash table textbooks | Python dict, C++ unordered_map (some impls) |
Candidate correctly defines both strategies at a high level and knows chaining uses lists while open addressing probes the array, but cannot discuss load factor sensitivity, cache behavior, or deletion complexity.
Candidate explains both strategies precisely, discusses trade-offs (cache locality, load factor sensitivity, deletion complexity), mentions probe sequence variants (linear/quadratic/double hashing), and cites a real implementation example.
Reading the answer is step one. Explaining it unprompted — under interview pressure — is what actually matters. Get AI-graded feedback on your answer with follow-up probes on your weak points.
Get Graded — Free Assessment