The hash map is the first data structure that feels like cheating. Trade some memory, get lookup in constant time, move on. That trade is real and it is the right default. But O(1) is an average-case claim resting on assumptions, and it is worth knowing which ones.
One: the key is expensive to hash
Hashing a 32-bit integer is a couple of instructions. Hashing a string of length k reads all k characters. If your keys are long strings, every lookup carries an O(k) factor that the O(1) hides. On a problem where keys are whole substrings, that factor is often the difference between linear and quadratic.
This is what rolling hashes exist for: update the hash in O(1) as the window moves, instead of recomputing it from scratch.
Two: collisions are adversarial, not random
The average-case guarantee assumes keys distribute across buckets. An adversary who knows your hash function can supply keys that all land in one bucket, degrading lookups to a linear scan. This is not theoretical — hash-collision denial of service against language runtimes with fixed hash seeds was a real class of vulnerability, and contest problems have been set specifically to break the default hash in particular languages.
In C++, unordered_map with default hashing on integers is a known target. Adding a random seed to your hash, or using a sorted structure, is the standard defence.
Three: growth is not free
Insertion is amortised O(1) because the table resizes and rehashes occasionally. Amortised means the cost is spread across the sequence, not that no single insert is slow. If you have a hard latency requirement per operation, a resize is a spike. If you know the final size, reserving it up front removes the spikes entirely.
Four: iteration order is not order
A hash map has no meaningful order, and the order it happens to produce can change between runs, versions and insertion sequences. Any solution whose correctness depends on iteration order is wrong even when it passes. If you need order, that is what a sorted structure is for — and you are choosing to pay log n for it.
When to reach for something else
- →You need predecessor, successor, or range queries — use a balanced tree or a sorted array.
- →Keys are long strings sharing prefixes — use a trie; you get prefix queries for free.
- →Keys are small integers in a known range — use an array. It is a perfect hash with no hashing.
- →You need worst-case guarantees rather than average-case — use a tree.
The default is still right
None of this means avoid hash maps. It means know what you are buying: excellent average-case behaviour, no ordering, no worst-case guarantee, and a hidden cost proportional to key size. For the large majority of problems that trade is obviously correct, which is exactly why it is worth being able to recognise the minority where it is not.
Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.