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).

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.

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.