How a hash table works

Why is a dict lookup O(1) when a list lookup is O(n)?

Because a dict computes where to look instead of searching for it. The key is fed through a hash function, which turns it into a number, and the remainder of that number by the table size is an index. Going to an index is one step, whatever the table size. The only searching left is inside that one slot, and the table keeps itself big enough that a slot holds one or two keys on average. A list has no such arithmetic: it has to compare the value against each element until it finds one that matches.

What actually happens when two keys collide?

Nothing exceptional, because collisions are the normal case rather than a failure. Two designs handle them. Separate chaining keeps a small list in each bucket and appends the second key to it, so a lookup scans that list. Open addressing, which is what CPython uses, keeps one key per slot and follows a fixed sequence of other slots until it finds the key or an empty slot. Either way the extra cost is proportional to how crowded the table is, and the resizing rule keeps that small.

Why can a list not be a dict key?

Because a key has to keep the same hash for as long as it is in the table, and a list can change. The table files a key under a number computed when it was inserted, and it never recomputes it. Change the key and the entry stays where it was, filed under an address that no longer matches, and nothing will find it again. Rather than let you create that situation, Python refuses: lists, sets and dicts have no usable hash. Tuples and frozensets do, as long as everything inside them does too.

Is it O(1) or amortized O(1)?

Lookup is O(1) on average, with no amortising involved. Insert is amortized O(1): almost every insert is a single write, but the ones that push the table past its load factor rebuild the whole thing into a table twice the size. That cost, spread over the inserts that caused it, is a constant per insert, because the table doubles rather than growing by a fixed amount. Saying “amortized constant for insert, average constant for lookup” is the precise version, and it is worth about four seconds.

What should I say when an interviewer asks about the worst case?

Say it is O(n), say why, and say why it does not usually matter. Every key can land in the same bucket, which turns the lookup into a scan of everything. With Python's own hash on ordinary data that does not happen by accident, and it is why the hash of a string is randomised per process: it makes it hard for an attacker to craft keys that all collide on purpose. If the interviewer is asking because the keys are attacker-controlled, that is the answer they want to hear.