What does an ordered map give you that a hash map does not, and what do you pay for it?
answer
- what a hash map deliberately throws away
- order of keys, not just membership
- everything between two keys, and nearest match
- root-to-leaf path on every operation
- logarithmic depth versus expected constant hashing
basics
~20 sAn ordered map keeps its keys in sorted order, so it supports in-order iteration, range scans between two keys, and nearest-key lookups. You pay O(log n) on every insert, lookup and delete instead of a hash map's expected O(1).
solid answer
~50 sA hash map places each key in a bucket derived from its hash, so it answers exactly one question fast: is this precise key present? Iteration order is arbitrary and may change as the table grows. An ordered map keeps keys sorted by a comparison rule, which buys three things: iteration in key order in `O(n)` with no sort step, range queries ("everything between 09:00 and 11:00") as a `O(log n)` locate plus `O(k)` walk, and nearest-key queries — the largest key at or below a value, the smallest at or above. The price is that every operation walks a root-to-leaf path, so it is `O(log n)` rather than expected `O(1)`, with worse cache locality and the cost of each comparison on top. Reach for ordering when you will ask "what's next", "what's before", "everything between" or "in order".
go deeper
Be ready to name the three things ordering buys — in-order iteration, range scans, nearest-key lookups — and to say the cost out loud as O(log n) per operation versus expected O(1).
Explain why hash iteration order is arbitrary in the first place, and quantify the alternative: one sort of the key set is O(n log n) plus a full copy, repeated every time order is needed.
Show that you pick from the query list, not from habit. Say which feature requirements make ordering functional rather than a nicety, and mention comparison cost and cache locality as the real constant factors.
Own the framing that ordering is a data-model decision, not a container preference: it dictates what queries the service can offer cheaply later, and retrofitting it after the access pattern is set is a migration, not a swap.
## Two maps, two different promises Both structures store key/value pairs and both answer "give me the value for this key". They differ in what else they promise. A **hash map** computes a hash of the key and uses it to pick a bucket. The bucket layout is a function of the hash, not of the key's order, so the sequence in which entries come out of iteration is arbitrary — and may change entirely when the table grows and every entry is rehashed. That arbitrariness is not a defect; it is the price of turning a key straight into an address. An **ordered map** keeps its entries sorted by a comparison rule — the key type's natural order, or a comparator supplied at construction — and maintains that order across every insertion and deletion. Production implementations are balanced search structures (red-black trees are the classic choice), where "balanced" means the height stays within a constant factor of `log n`. ## The three capabilities ordering buys **1. Sorted iteration.** Walking an ordered map yields keys from smallest to largest in `O(n)` total, with no sorting step and no temporary copy. To get the same from a hash map you extract all keys and sort them: `O(n log n)` plus a full copy of the key set, repeated every time you need it. **2. Range queries.** "Every booking that starts between 09:00 and 11:00" is a locate-then-walk: `O(log n)` to find the first key at or after 09:00, then `O(k)` to emit the `k` matching entries. Total `O(log n + k)` — proportional to the *answer*, not to the dataset. A hash map has to examine all `n` keys, because nothing about a bucket tells you whether the key inside falls in the interval. **3. Nearest-key queries.** *Floor* (the largest key at or below `x`) and *ceiling* (the smallest key at or above `x`) answer "what applies at this point" and "what comes next" in `O(log n)`. A hash map answers only "is exactly this key present"; it knows nothing about neighbours. Smallest and largest key are likewise cheap in an ordered map and are a full scan in a hash map. ## What ordering costs Every operation — lookup, insert, delete — descends a path from the root, and balancing keeps that path at `O(log n)` entries. Concretely: about 20 comparisons at a million entries, about 30 at a billion. That is small, but it is not one hash-and-probe, and three further costs ride along: - **Comparison cost.** The `log n` counts *comparisons*, not machine cycles. Comparing fixed-width timestamps is nearly free; comparing long composite text keys is not, and there the constant factor dominates the asymptotics. - **Locality.** An entry-per-node layout means pointer chasing across scattered memory, whereas a bucket table walks a contiguous array. Cache behaviour usually favours the hash map. - **Comparability requirement.** Keys must define a consistent total order. A comparator that is inconsistent (says `a < b` and `b < a`, or disagrees with equality) silently loses or duplicates entries — the ordered-map analogue of a broken hash/equality pair. ## The decision rule Ask what queries the feature actually issues. If every one is an exact-key lookup on an opaque identifier and iteration order is irrelevant, the hash map is the default and the right default. If the feature ever asks *what's next*, *what's before*, *everything between*, or *in order*, ordering is a functional requirement and the ordered map's `O(log n)` is what it costs. ## The half-answer to avoid "I'll use a hash map and just sort the keys when I need order." That is correct when order is needed **once**, at the end of a batch: one `O(n log n)` sort against `n` cheap inserts beats `n` logarithmic inserts. It is wrong when order is needed **continuously** — a live dataset re-sorted on every query pays `O(n log n)` each time, while the ordered map amortises the same work into `O(log n)` per mutation and keeps the answer ready. ## One more difference worth naming The ordered map's `O(log n)` has no dependence on how the keys are distributed, because it never hashes anything — it only compares. The hash map's expected `O(1)` assumes keys spread across buckets. That difference matters mostly at the latency tail, which is a separate discussion, but it is why "the hash map is simply faster" is a claim about the average case and not about the guarantee.
- If you only need the keys in sorted order once, at the very end, is an ordered map still the right choice?Usually not. Collecting into a hash map costs expected `O(1)` per insert and one `O(n log n)` sort at the end, which beats paying `O(log n)` on every one of the n insertions to keep an order you never consult in between. The ordered map wins when order is queried repeatedly while the data is still changing — then the sort would be re-run over and over.
- Does an ordered map's O(log n) depend on how well the keys hash?No — it never hashes them. The bound comes from the height of a balanced search structure, so it holds for any key distribution, including keys chosen by an attacker. What it does depend on is the comparison: cost per comparison sets the constant factor, and an inconsistent comparison rule breaks the structure outright.
- Can an ordered map iterate in insertion order instead of key order?No. Its only order is the comparison order over keys; insertion history is not stored anywhere. Preserving arrival order is a different structure's job — a hash map paired with a link list of entries — and that hybrid gives you insertion order but not range or nearest-key queries.
A hash map is a coat check: hand over the ticket, get the coat instantly, but nobody can tell you which coat is next to it. An ordered map is a shelf of files in alphabetical order: slightly slower to reach one, but you can read the neighbours and any stretch in between.
saying these in an interview costs you the question
- Calls an ordered map just a hash map that iterates sorted
- Assumes hash maps iterate in insertion or sorted order
- Thinks sorting a hash map's keys on demand is free
- Says ordered maps are always slower, so never worth it
- Cannot name a query a hash map simply cannot answer