Why does a plain hash map make no promise about iteration order?
answer
- where does an entry physically live?
- iteration scans slots, not history
- index comes from hash and capacity
- nothing records when a key arrived
- observed order is not a contract
basics
~20 sIteration walks the internal bucket array from the first slot to the last, so the order falls out of each key's hash value and the table's current capacity. Nothing in that arrangement records when a key arrived, and no implementation commits to keeping it.
solid answer
~40 sA hash map places each entry in the bucket its key's hash selects, and iteration simply scans the bucket array in index order, emitting whatever it finds. The sequence you observe is therefore a function of the hash values and the current capacity — two accidents of the data — not a property the structure exposes. On small maps with small, dense keys it often looks stable or even insertion-like, which is exactly what misleads people into asserting on it. Treat any observed order as an implementation detail: if you need insertion order, reach for an insertion-order-preserving map; if you need a defined output order, sort the keys at the point of output. Anything else is a test that passes until the data changes.
go deeper
Be ready to state that a plain hash map has no ordering guarantee and to say why in one breath: iteration scans the bucket array, and a key's slot comes from its hash and the capacity, not from when you added it.
An interviewer expects the mechanics: slot index from hash reduced by capacity, collision handling deciding within-slot placement, and iteration as a plain left-to-right sweep of slots. Explain why the order is deterministic within a run yet still not a contract.
Show you catch this in review. Point at the code path where map iteration feeds a serialized artifact or an assertion, and name the fix you would require — sort at output, or an order-preserving structure when order carries meaning.
Own the policy. Decide whether your codebase treats iteration order as forbidden ground everywhere, and back that with a review rule or lint rather than folklore, because the cost of this assumption lands months later on someone who did not make it.
## What iteration actually does A hash map is, underneath, an array of slots (buckets) plus a hash function. To store a key, the table computes `h = hash(key)` and reduces it to a slot index, typically `h mod capacity` or a mask of the low bits. Entries that land in the same slot are handled by chaining (a small list per slot) or by open addressing (probing forward to the next free slot). Iteration has no separate index. It walks slot 0, slot 1, slot 2, ... to the end of the array, emitting each entry it encounters. That is the whole algorithm. Consequently the sequence you see is determined by three things and nothing else: the hash values of the keys present, the current capacity, and the collision-handling rule that decided where colliding keys ended up. ## Why that means "no promise" None of those three inputs has anything to do with the order in which you inserted keys. The table stores no arrival timestamp, no sequence number, no back-pointer to a list of insertions — storing one would cost memory and work on every write, which is precisely the cost a plain hash map declines to pay. So there is nothing in the data structure from which insertion order could be reconstructed, even in principle. It is important to be exact about what "no promise" means. Within a single run of a single implementation, iteration is usually *deterministic*: the same keys inserted in the same sequence give the same output every time you iterate. Deterministic is not the same as guaranteed. The order is a byproduct that the implementation is free to change — and does change when the table grows, when the implementation is upgraded, or, in designs that mix a per-process random value into hashing or into the iteration start point, from one process to the next. ## The illusion of stability The reason this trap is so effective is that small examples lie. With a handful of small integer-like keys and a capacity of, say, 16, hashes often reduce to slots in a tidy ascending pattern; if you also inserted those keys in ascending order, iteration looks exactly like insertion order. A candidate then generalises from a five-element example to a contract. The same code with two hundred string keys, or with the same keys after the table has grown, emits an order nobody predicted. ## What different structures actually promise - A plain hash map: *nothing*. Fast lookup and insertion, no order. - An insertion-order-preserving (linked-hash) map: entries come back in the order they were first inserted, because the structure additionally maintains a list linking entries in arrival order. You pay extra memory per entry and a little bookkeeping per write for that guarantee. - A sorted/ordered map: entries come back in key order, at logarithmic lookup cost rather than expected constant. - Sorting at output: keep the fast map, and impose an order only where a human or a diff tool will look at the result. Mainstream runtimes have made deliberately different calls here, which is itself the proof that no universal contract exists: Go randomizes the starting point of map iteration so that no program can accidentally depend on an order, Python's dictionaries have specified insertion order since 3.7, and Ruby's hashes have promised it far longer. The same concept, three different published contracts — so a habit learned in one is a bug in another. ## How this shows up in real work The classic symptom is a serialized artifact — a generated document, a report, an export — whose field or line order is produced by iterating a map. Nobody wrote a spec for that order, but a test asserts on the exact text, or a versioned archive diffs one run against the last. It works for months. Then the data grows, or a runtime is upgraded, and the order moves. Nothing is broken except an assumption that was never true. ## What to say in an interview Name the mechanism (bucket-array scan), name the inputs (hash values, capacity, collision handling), and then state the rule crisply: observed order is an implementation detail, and the only orders you may rely on are the ones a structure or your own code explicitly produces. If pressed for a fix, give both — sort at output when the order is cosmetic or diff-facing, switch to an order-preserving structure when the order is genuinely part of the meaning.
- If the order looked exactly like insertion order in your tests, what usually explains that?Coincidence at small scale. A handful of small, dense keys often reduce to ascending slot indexes, so a bucket-order scan happens to reproduce the order you typed them in. Add more keys, use string-like keys, or let the table grow, and the coincidence disappears. A five-element example is the worst possible evidence for an ordering claim.
- You need fast lookup and a defined output order — what are your options and what do they cost?Three. Sort the keys when writing the output: keeps the fast map, costs `O(n log n)` per emission and only where you emit. Use an insertion-order-preserving map: order guaranteed, costs extra memory per entry plus link maintenance on writes. Use an ordered map: keys come back sorted, but lookups become logarithmic rather than expected constant.
- If you remove a key and immediately re-insert it, does it return to its old position in iteration?In a plain hash map there is no "old position" to return to — the key lands in whatever slot its hash selects, which is typically the same slot as before, so the visible order may well look unchanged. That is not a guarantee either: with open addressing, deletions and later insertions can shift probe positions, and in an insertion-order-preserving map the re-inserted key moves to the end.
It is a coat-check with numbered pegs: your ticket number decides your peg, and the attendant collects coats by walking the pegs left to right. The sweep has no idea who arrived first.
saying these in an interview costs you the question
- Says a hash map iterates in insertion order
- Believes each iteration returns a freshly shuffled order
- Assumes the order will hold because it held in every test
- Claims keys come back sorted because lookups are fast
- Treats a five-element example as proof of an ordering rule