Core Concept Mastery • DSA Module
On average, search and insert in a hash table are O(1). In the worst case (e.g. many keys in one slot or one long chain), they can be O(n). Space is O(n): we use a table that can be larger than the number of items to keep collisions low.
| Op | Avg | Worst |
|---|---|---|
| Search | O(1) | O(n) |
| Insert | O(1) | O(n) |
Worst case O(n) happens when many keys go to the same slot (e.g. one long list or many steps). So we want a good hash and a low load factor.
Space is O(n). We may use a table bigger than n (empty slots) to get fast speed. That is the trade-off.
Time: average vs worst
Average case: the hash spreads keys, so we go to one slot (and maybe a short list or a few steps). So search and insert are O(1) on average.
Worst case: if many keys go to the same slot, we have a long list or many steps. Then we may have to look through all of them. So worst case is O(n).
Space
We need O(n) space for the n items. We often use a table bigger than n (extra empty slots) to reduce collisions. So we trade space for speed.
We trade some extra space (empty slots) for speed. When the hash spreads keys well and load factor is low, we get O(1) on average. When things pile up in one place, we can hit O(n).