What is the time complexity of hash table operations?
Updated Feb 20, 2026
Short answer
Insert, lookup, and delete are all O(1) on average, because a hash function computes the bucket index directly rather than searching. The worst case is O(n), when every key collides into one bucket and the operation degenerates into scanning a list. The average case holds only while the hash function distributes well and the load factor stays bounded.
Deep explanation
The O(1) claim is an average over a good hash function and a bounded load factor. Both conditions can fail.
| Operation | Average | Worst case |
|---|---|---|
| Insert | O(1) | O(n) |
| Lookup | O(1) | O(n) |
| Delete | O(1) | O(n) |
| Iterate all | O(n + m) | O(n + m) |
m is the bucket count — iteration must walk empty buckets too, so a large sparse table iterates slower than its element count suggests.
Why average O(1). With n entries in m buckets, the expected chain length is the load factor n/m. Keep that below a constant — implementations resize at around 0.75 — and every operation touches a constant number of entries.
Why worst case O(n). If every key hashes to the same bucket, the table becomes one long chain and every lookup scans all of it. This is not just theoretical: hash-flooding attacks craft colliding keys deliberately, which is why Python and Rust randomise their hash seed per process. Java's HashMap caps the damage by converting a long chain to a red-black tree, giving O(log n) instead of O(n).
Resizing is amortised. Growing the table rehashes every entry — a single O(n) insert. Spread across the insertions that caused the growth, it averages to O(1). It does mean one unlucky insert can be slow, which matters for latency-sensitive code.
Real-world example
Deduplicating 1,000,000 records:
seen = set()for record in records: # 1,000,000 iterations if record.key in seen: # O(1) average continue seen.add(record.key) # O(1) averageTotal O(n). The list equivalent — if record.key in seen_list — is O(n) per check, making the whole loop O(n²): a hundred billion comparisons instead of a million.
If you know the size up front, presizing avoids the repeated rehashing entirely: dict(capacity) in languages that expose it, or HashMap::with_capacity(1_000_000) in Rust.
Common mistakes
- - Stating O(1) without the average-case qualifier — interviewers are usually listening for the worst case.
- - Forgetting that iteration is O(n + m), so a huge table that has been mostly emptied still iterates slowly.
- - Ignoring the cost of the hash function itself
- hashing a long string is O(k) in its length, so 'constant time' is constant in the *number of entries*, not free.
- - Assuming resizing is free — it is amortised O(1) but individually O(n), which can breach a latency budget.
- - Overlooking that a poor or attacker-controlled hash collapses everything to O(n).
Follow-up questions
- Why is iteration O(n + m) rather than O(n)?
- What is the cost of hashing a key itself?
- How does Java's HashMap avoid the O(n) worst case?
- When is a sorted structure preferable despite worse complexity?