skip to content

In Rust, why do two `HashMap<String, u32>` maps built from the same keys, in the same order, iterate in different orders?

level: middleimportance: should knowfreq 45%

answer

  1. order follows the hash
  2. the hidden third type parameter
  3. per-thread keys, bumped per map
  4. equality ignores order

basics

~20 s

Each HashMap gets its own RandomState: SipHash 1-3 keys taken from OS randomness once per thread and incremented for every new RandomState, so the same keys land in different buckets and iteration order usually differs between maps and runs.

solid answer

~40 s

`HashMap<K, V>` is `HashMap<K, V, RandomState>`, and std documents its iterators as visiting entries in arbitrary order. `RandomState::new()` reads random keys from the OS once per thread, caches them, and adds one to a key on every call, so each map hashes with a different SipHash 1-3 key pair; std's source says the bump exists because a shared deterministic order enabled a denial-of-service. Different keys mean different buckets, so the order usually differs per map and per run, while `a == b` still compares contents, not order. For stable output, sort the keys, use a `BTreeMap`, or reach for the `indexmap` crate; `BuildHasherDefault<DefaultHasher>` makes hashing repeatable but gives up HashDoS resistance and is not promised stable across releases.

code

rust · 14 lines
rust
use std::collections::HashMap;

fn order(m: &HashMap<String, u32>) -> Vec<&str> {
    m.keys().map(String::as_str).collect()
}

fn main() {
    let keys = ["alpha", "beta", "gamma", "delta", "epsilon", "zeta"];
    let a: HashMap<String, u32> = keys.iter().map(|k| (k.to_string(), 0)).collect();
    let b: HashMap<String, u32> = keys.iter().map(|k| (k.to_string(), 0)).collect();
    println!("a: {:?}", order(&a));
    println!("b: {:?}", order(&b));
    println!("a == b: {}", a == b);
}

go deeper

for a junior

Know that HashMap iteration order is arbitrary and changes between runs. If you need sorted output, sort the keys or use a BTreeMap.

for a middle

Explain RandomState: SipHash 1-3 keyed per map, keys cached per thread and incremented on each new map. Note that equality compares contents, not order.

for a senior

Diagnose flaky snapshots and order-dependent zips quickly, and pick the fix by cost: sort at the edge, BTreeMap, or IndexMap. Explain why a fixed hasher is the wrong fix for production code.

for a principal

Set the expectation that no output, API response or test may depend on HashMap order. Make sorted or insertion-ordered output an explicit choice in the type, not an accident of the hasher.

## Where a hash map's order comes from A `HashMap` places each entry in a bucket chosen from the key's **hash**. Iterating walks the buckets in memory order, so the order you see is a by-product of the hash values (and of the table's capacity and insertion history), not of the order you inserted. std documents every iterator on `HashMap` (`iter`, `keys`, `values`, `into_keys` and the rest) as visiting entries "in arbitrary order". The interesting Rust-specific part is why two maps with identical contents, built identically in the same process, usually disagree. ## `RandomState`: one key pair per thread, bumped for every map `HashMap<K, V>` is shorthand for `HashMap<K, V, RandomState>`. **`RandomState`** (in `std::hash`) is a `BuildHasher` holding two 64-bit keys, `k0` and `k1`. Each hasher it builds is a **SipHash 1-3** instance keyed with those two values, wrapped as `DefaultHasher`. Different keys mean different hashes for the same string, which means different buckets and a different iteration order. How `RandomState::new()` gets its keys, as std's source does it: 1. The first call on a thread asks the operating system for random keys and caches them in a **thread-local**. 2. Every call returns the cached pair, then **adds one to `k0`** in the cache. 3. So every `RandomState` (hence every `HashMap::new()`) on that thread gets a distinct key pair. The source comments give both reasons. Generating fresh random keys for every map (from a thread-local generator that periodically re-seeded from the OS) made code that creates many maps slow, so the keys are cached. And, in the source's words, "exposing a deterministic iteration order allows a form of DOS attack" (the reported case: copying one map, in its iteration order, into another that hashes identically can make the copy degrade badly). Incrementing the key per map gives every map its own order. As a result the order usually differs between runs (new OS keys) and between maps in one run (bumped keys). ## What this breaks - **Snapshot and golden tests** that print a map with `{:?}` or iterate it into a string pass on one run and fail on the next. - **Serialized output** (a JSON body, a CSV report, a log line) changes order between requests, which can churn diffs and caches. - **Code that zips two maps' iterators** assuming they line up position by position is wrong even when the maps are equal. - **`HashSet` output** has the same problem: a `HashSet<T>` is a `HashMap<T, ()>` with its own `RandomState`, so a set printed in an assertion message or joined into a string changes order the same way. None of this is a bug in the program that observes it; the program was relying on something std never promised. The fix is to make order an explicit property of the data at the point where it matters. What does **not** break is equality: `HashMap`'s `PartialEq` compares lengths and then looks up every key of one map in the other, so `a == b` is `true` for equal contents whatever the iteration order. ## Fixes, and what each one costs | Need | Fix | Cost | |---|---|---| | Stable output once | collect keys or pairs into a `Vec` and sort | O(n log n) at output time | | Always sorted | a `BTreeMap` (covered with ordered maps) | O(log n) lookups, needs `Ord` | | Insertion order | the `indexmap` crate's `IndexMap` | an extra dependency | | Repeatable hashing | `BuildHasherDefault<DefaultHasher>` | no HashDoS resistance | The last row needs care. `DefaultHasher::new()` always uses SipHash 1-3 with keys `(0, 0)`, so `BuildHasherDefault<DefaultHasher>` produces the same hashes on every run, and in practice the same order for the same insertion history. std's own documentation warns that a map built this way **is not resistant to HashDoS attacks**, and it says `DefaultHasher`'s algorithm is unspecified and should not be relied on across releases. A test that depends on this order can break on a toolchain upgrade. Sorting at the edge is the robust fix. ## What not to rely on - Insertion order: a `HashMap` never promises it. - The same order in two maps: the per-map key bump makes this false even in one thread. - The same order across runs: the OS keys change at every process start. - The algorithm: std says SipHash 1-3 is the current choice and "subject to change at any point in the future".

  • Why does `RandomState::new()` not ask the operating system for fresh keys every time?
    std's source explains that it once generated fresh random keys on every call, from a thread-local generator that periodically re-seeded from the OS, and that made code creating many hash maps on a thread excessively slow. It now fetches random keys once per thread, caches them in a thread-local, and increments one key on every call. Each map still gets distinct keys, and only the first map on a thread pays for the OS call.
  • Does `a == b` on two `HashMap`s care about iteration order?
    No. `HashMap`'s `PartialEq` returns `false` if the lengths differ and otherwise checks that every key of one map is found in the other with an equal value. Two maps with the same pairs compare equal even when their iterators disagree, and even though each was hashed with different keys.
  • A Rust snapshot test prints a `HashMap` with `{:?}` and flakes; what is the smallest robust fix?
    Make the output ordered at the edge: collect the pairs into a `Vec`, sort it, and print that, or convert to a `BTreeMap` just for the assertion. Swapping in a fixed hasher would hide the flake, but std does not promise `DefaultHasher`'s algorithm across releases, so the test could break on a toolchain upgrade, and the same pattern in production code would lose HashDoS resistance.

  • A HashMap iterates in insertion order
  • Two maps with the same keys iterate identically within one process
  • The order is fixed per binary, so snapshot tests of a HashMap are stable
  • BuildHasherDefault<DefaultHasher> is a free fix with no security cost
  • a == b is false when two maps iterate in different orders