When is an ordered map's O(log n) worst case preferable to a hash map's expected O(1)?
answer
- read the adjectives on both bounds
- expected assumes something about the keys
- amortized hides one very slow operation
- who gets to choose the keys
- mean versus p99 is the real question
basics
~20 sWhen the latency tail matters more than the average. A balanced ordered map bounds every operation at O(log n) whatever the keys look like, while expected O(1) degrades under collisions and hides an occasional full-table rehash.
solid answer
~50 sExpected `O(1)` carries two pieces of fine print. It is *expected* — an average over keys that spread well across buckets; keys that collide, whether by bad luck or by an attacker choosing them, degrade toward a linear scan of one bucket. And it is *amortized* — a single insertion that triggers growth rehashes every entry, so one operation in the sequence costs `O(n)` while the average stays constant. A balanced ordered map makes neither trade: every operation walks a path bounded by the structure's height, roughly 20 comparisons at a million entries and 30 at a billion, with no dependence on how the keys are distributed and no periodic bulk copy. So on a request path with a strict p99 budget, or a map keyed by values an untrusted caller supplies, the predictable logarithm can beat the faster average. On throughput-oriented work with well-behaved keys, the hash map still wins.
go deeper
Know that the constant-time claim for hash lookups is an expected cost, not a guarantee, and that a balanced ordered map's logarithmic bound holds for every operation.
Explain both qualifiers precisely: expected assumes the keys spread across buckets, and amortized means one insertion can rehash everything while the average stays constant.
Argue from the requirement. Name the tail-latency budget or the untrusted-key boundary that makes predictability worth a worse average, and concede where the hash map still wins.
Own the risk framing: whether the service's contract is a mean or a percentile, whether key sources cross a trust boundary, and whether the team can defend a probabilistic bound in a capacity model.
## Reading the two bounds precisely The comparison is usually stated as "O(1) beats O(log n)", which drops exactly the qualifiers that decide the question. **A hash map's lookup is expected O(1).** *Expected* means averaged over a distribution of keys assumed to spread across buckets. It is not a guarantee about any single operation, and it is not a claim about adversarial input. When many keys land in one bucket, that bucket's contents must be searched — linear in the collision chain unless the implementation escalates to something better-behaved. Worst case for the structure is `O(n)`. **A hash map's insert is expected O(1) amortized.** *Amortized* is a statement about the total cost of a worst-case *sequence*, not about any one operation. Growth-doubling tables rehash every existing entry when the load factor crosses its threshold: that single insertion is `O(n)`. Spread across the insertions that preceded it, the average stays constant — but the individual request that paid it saw a full-table pause. **A balanced ordered map's operations are O(log n) worst case.** No distribution assumption, no amortization, no bulk copy. The bound comes from the height of a balanced structure — red-black ordered maps keep height within a constant factor of `log n` by construction — so the *guarantee* and the *typical* case are the same number. ## Where the guarantee is worth buying **A hard tail budget.** If the requirement is "p99 under 5 ms" rather than "mean under 5 ms", the mean is not the metric being defended. A structure whose slowest operation is 30 comparisons is easier to reason about than one whose slowest is a rehash of ten million entries, even when the second is faster 99.9% of the time. On a large map the rehash is not microseconds, and it lands on whichever unlucky request triggered it. **Untrusted keys.** When a caller chooses the keys — request parameters, uploaded identifiers, header names — a party who knows the hash function can manufacture keys that collide, turning every lookup into a scan and the endpoint into an amplification lever. The standard mitigation is a keyed, randomized hash such as SipHash, seeded per process so the collisions cannot be precomputed. An ordered map needs no such mitigation: comparisons cannot be made to collide, and an attacker choosing keys still gets `O(log n)`. **Skewed or degenerate key spaces.** A weak hash over structured keys — sequential identifiers with a fixed high prefix, values whose low bits are always zero — can concentrate entries in a few buckets even with no attacker present. Ordering does not care: the comparison rule is total whatever the keys look like. **Auditability.** A logarithmic bound is easy to defend in a design review and easy to model in a capacity plan. "Expected constant, given the keys behave" requires you to argue about the keys. ## Where the guarantee is not worth buying Be honest about the other side, or the argument becomes its own misconception. - On average, the hash map is genuinely faster and usually by a wide margin: one hash and a probe against ~20 dependent memory accesses, each following a pointer into cold cache. The ordered map's constant factor is worse in both time and memory per entry. - Mature hash implementations attenuate the failure modes: randomized seeding blunts collision attacks, and escalating an over-full bucket to an ordered sub-structure caps the degenerate case at logarithmic rather than linear. Incremental resizing schemes spread the rehash across many operations instead of paying it all at once. - If the comparison itself is expensive — long composite text keys, a comparator doing normalization — the ordered map's `log n` comparisons can cost far more wall time than a single hash of the same key. - Throughput-oriented batch work does not care about tails at all. There, the average *is* the metric, and the hash map wins on it. ## The ordered map's own hiccups It is not pause-free by magic; it is pause-free because it never does bulk work. Rebalancing after an insertion or deletion is local and bounded — a constant number of local restructurings on the path just walked — so no single update touches a large fraction of the entries. That is the structural reason the worst case and the typical case coincide, and it is a different property from "it is fast". ## How to actually decide Ask which metric the requirement names. If it is a mean or a throughput number and the keys are yours, default to the hash map. If it is a tail percentile, or the keys come from outside your trust boundary, the predictable logarithm is a legitimate and defensible choice — and if you *also* need ordering, the decision has already been made for you on functional grounds and this whole comparison is moot.
- What single hash-map operation can cost O(n), and who pays for it?An insertion that pushes the load factor past its threshold triggers growth: a larger table is allocated and every existing entry is rehashed into it, which is linear in the size of the map. Amortization spreads that cost across the preceding insertions on paper, but in production one request pays the whole thing, which is why it shows up as a periodic latency spike rather than a slow average.
- Does an ordered map have a comparable pause of its own?No bulk one. Restoring balance after an update is local work bounded by a constant number of restructurings along the path just walked, so no single operation touches a large share of the entries. Its costs are steady instead: a worse constant factor per operation, more memory per entry, and poor cache locality from pointer chasing.
- Modern hash maps use randomized hashing, so is the collision-attack argument obsolete?It is much weaker, not gone. A per-process random seed with a keyed hash such as SipHash means collisions cannot be precomputed offline, which removes the cheap attack. What remains is that the guarantee is still probabilistic and depends on the implementation actually doing this — worth verifying rather than assuming when keys cross a trust boundary.
- How would you confirm that a periodic p99 spike really is a container growth pause?Correlate the spike times with map size: the pauses should appear at sizes near successive growth thresholds, roughly doubling in spacing, and should scale with the number of entries rather than with request rate. Pre-sizing the container to its expected final capacity is the cheap experiment — if the spikes disappear, the diagnosis holds.
saying these in an interview costs you the question
- Says hash lookups are O(1), full stop
- Treats amortized as the same thing as average-case
- Believes expected O(1) holds for attacker-chosen keys
- Ignores that one insertion can rehash the whole table
- Claims an ordered map is faster on average than hashing
- Argues from asymptotics without naming the latency metric