Hash Table Operations

Average case: $O(1)$ for insert, lookup, delete. Worst case: $O(n)$ if all keys collide (hash to the same index).

Collisions are rare with good hash functions and proper table sizing. In competitive programming, assume $O(1)$ unless you're dealing with adversarial inputs.

Some judges craft test cases to break weak hash functions. If you get TLE, consider using a tree-based map ($O(\log n)$) instead. Time: $O(1)$. Space: $O(n)$.