What is the average and worst-case time complexity for lookup in a Hash Table?

Difficulty: 4/10

hash table lookup, time complexity, collision handling

Hash Table Complexity

Hash Table lookup is expected O(1) on average when the hash function distributes keys well and the load factor is controlled. The worst case is O(n), because all keys could theoretically map to one bucket or an unfavorable probe sequence could examine many slots.

javascript

1
Average-case lookup: expected O(1).
2
Worst-case lookup: O(n) for a conventional chained or open-addressed table.
3
Performance depends on hash quality, load factor, collision strategy, and implementation.
4
Resizing helps maintain the expected constant-time behavior.
5
Some modern implementations can improve pathological bucket behavior to O(log n) using balanced trees.

Scenario Questions

0-2 years experience

2-5 years experience

1We noticed a spike in latency for a service that uses a hash map for session lookup. Walk me through how hash collisions could lead to worst‑case O(n) lookups and how you would debug it.

Follow-up Questions