Why can a hash map's iteration order change after an insert that touched no existing entry?

## The placement rule has two inputs, not one People remember "a key's position comes from its hash" and stop there. The rule is really `slot = reduce(hash(key), capacity)` — usually `hash mod capacity`, or a mask of the low bits when capacity is a power of two. The hash of a key is fixed for the life of that key. The capacity is not. So every change of capacity is a change of address for potentially every key in the table, without a single key being modified. ## When capacity changes Hash tables keep occupancy below a load factor — commonly somewhere around 0.7 for open addressing, often near 0.75 for chaining — because performance degrades as the table fills: chains lengthen, probe sequences lengthen. When an insertion pushes `size / capacity` past that threshold, the table grows, typically by doubling, and re-places every entry. That re-placement is the operation that makes insertion *amortized* expected `O(1)` rather than plain `O(1)`: the individual insert that triggers growth does `O(n)` work. The fragment below shows both halves — the sweep that produces iteration order, and the growth step that rewrites the slot every key sits in. ## Why the emitted sequence moves Under capacity 16, two keys whose hashes are 5 and 21 both reduce to slot 5 and share a chain. Under capacity 32 they reduce to 5 and 21 — different slots, now separated by sixteen positions in the sweep, and with other keys interleaved between them. Meanwhile a key that was at slot 15 (late in the sweep) may still be at slot 15, which is now early in a 32-slot sweep. The relative order of essentially the whole table can change. Under open addressing the effect is the same for a different reason: probe sequences are computed against capacity, so which key won a contested slot and which got pushed forward can invert. There is a second, smaller source of movement even without growth. Within one chain, an implementation may prepend new entries (making the newest key appear first) or append them (oldest first); a bucket that overflows into a different internal representation reorders its own contents. Deletions in open-addressing tables leave tombstones and change where later insertions settle. None of this is visible from the outside, and none of it is promised. ## The failure this produces in real systems The damaging version is not a crash. Consider a billing export that writes one line per line-item by iterating a map keyed by item identifier, archived monthly and diffed against the previous month for audit. For a year the account has fewer items than the resize threshold, and the export's line order is stable enough that reviewers come to expect it. One month the account crosses that threshold: the table doubles, the export emits the same content in a different sequence, and the diff shows the entire file as changed. Now someone must prove that nothing substantive changed — the cost of the bug is investigator hours, not downtime, and it recurs at every subsequent threshold. Note the shape of the trigger: the input that changed was *volume*, not code and not the map's contents. That is why this class of bug survives code review and skips staging, where the fixture data set is small. ## "Then I'll pre-size it" Pre-sizing the table so it never grows removes the most common perturbation, and it is a legitimate performance optimisation. It is not a fix for an ordering dependency. The order is still a byproduct of hashing under a specific implementation; an upgrade that changes the growth policy, the reduction step, the chain insertion end, or the overflow representation moves it again, and some implementations deliberately vary it between processes. Pre-sizing converts a bug that fires this quarter into one that fires after an upgrade, which is worse, because by then nobody remembers the assumption. Different runtimes have made visibly different choices here, which underlines that none of it is portable: Go deliberately randomizes where map iteration starts, while Python's dictionaries specify insertion order and keep it across resizes — so the same "iterate and write" code is deterministic in one and deliberately not in the other. ## The correct fixes Impose the order where the order matters: sort keys at the serialization boundary, or hold the data in an insertion-order-preserving structure when arrival sequence is part of the meaning. And make the consumer honest — a diff or an assertion that compares parsed structures rather than raw text stops caring about the order entirely, which is usually the cheapest correct answer.