A strong answer
A lookup hashes the key, turns the hash into a slot, and compares the keys stored at or near that slot. Hashing the key and computing the slot take the same time however many entries the table holds. What varies is how many stored keys the lookup has to compare before it finds its key or proves the key is missing. On average that number is small and constant, for two reasons: a good hash function spreads keys evenly so each slot gets about the same share, and the table keeps its load factor, the number of entries divided by the number of slots, below a fixed limit by growing as it fills.
With chaining, the average list then holds a number of entries equal to the load factor, such as 0.75, however large the table grows. With linear probing, a lookup for a missing key checks about 2.5 slots when the table is half full and 8.5 when it is 75% full. Neither number grows with the number of entries, so lookups are O(1) on average.
The worst case is many keys landing on the same slot. A lookup then has to walk past all of them: a list of n entries with chaining, or a run of n occupied slots with probing. That is O(n). It can happen through a poor hash function that ignores part of the key, through extreme bad luck, or through an attacker who chooses colliding keys on purpose.
Real hash maps make the worst case rare or less severe. They mix the hash so that every part of the key matters, add a secret random key so that attackers can't predict collisions, and, in Java's case, turn a long chain into a balanced tree so that even a crowded slot is searched in O(log n). Inserts are O(1) amortized rather than O(1) every time: the insert that triggers a resize moves every entry, but doubling makes resizes rare enough that the average stays constant.
What the interviewer is listening for
- A lookup's cost is the number of keys it compares, not the size of the table.
- Average O(1) depends on two things: a hash that spreads keys, and a load factor kept below a limit.
- The worst case is many keys in one slot, and you can name how that happens.
- A strong answer adds the amortized cost of inserts, or how real implementations defend against the worst case.
Common mistakes
- Saying a lookup is O(1) "because array access is O(1)". The array access is constant, but resolving collisions isn't.
- Claiming collisions don't happen with a good hash function. They are certain once there are more keys than slots, and likely long before that.
- Forgetting the cost of hashing itself: hashing a string of length k takes O(k) time.