Open Addressing vs Separate Chaining: The Hash Table Follow-Up Question
After you use a dictionary in a coding round, a curious interviewer may ask: "What happens when two keys hash to the same bucket?" A one-line answer is fine, but a short trade-off discussion is what separates a strong signal from a neutral one.
Separate chaining
Each bucket holds a small list (or tree) of entries. Insertion appends to the bucket; lookup scans it. Java's HashMap uses this and converts long chains into balanced trees once a bucket passes eight entries, which caps worst-case lookup at O(log n) instead of O(n).
- Deletion is simple: remove the node from the chain.
- Load factor can exceed 1 without breaking anything, only slowing down.
- Cost: an extra pointer per entry and poor cache locality.
Open addressing
All entries live in one flat array. On a collision you probe other slots: linear probing (next slot), quadratic probing, or double hashing. CPython's dict and many high-performance maps such as Abseil's Swiss tables use variants of this.
- Excellent cache behaviour, since probes touch neighbouring memory.
- Must resize before the table fills up; performance collapses as load approaches 1.
- Deletion is tricky: you cannot just empty a slot, or later probes stop early. Implementations mark slots as deleted and clean them up on resize.
How to frame the answer
Name both strategies, give one real-world example of each, then tie it to the problem in front of you. For example: "For this interval cache I'd expect heavy reads and few deletes, so open addressing with linear probing is a good fit; if we needed frequent deletes I'd lean toward chaining." Finish with the complexity: average O(1) for both, worst case O(n) unless the chains are trees.
Bonus point
Mention hash flooding: an attacker who can choose keys can force every key into one bucket. That is why many languages randomise their string hash seed per process.
Disclosure: I work on AI interview copilot at Linkjob AI, which builds tools for interview practice and live interview support. This note is my own write-up and is not sponsored by the host.