HashMap iteration order is random

Aggregate (key, value) pairs into per-key totals — using a HashMap, for the O(1) lookups — and return them in a deterministic order.

pub fn stable_summary(pairs: Vec<(String, i64)>) -> Vec<(String, i64)>

Sum the values for each key. Return one (key, total) per distinct key, ordered by total descending, and where totals tie, by key ascending.

Several test cases contain tie groups on purpose. If you return the map’s own iteration order, you will not fail consistently — you will fail sometimes. That is the lesson, and it is stated up front so that the flakiness teaches instead of infuriating.

HashMap really does shuffle itself

Here is the same program, an eight-key map built in the same order, run four times in a row:

charlie foxtrot golf delta echo alpha bravo hotel
charlie bravo delta echo alpha hotel golf foxtrot
golf foxtrot echo bravo hotel alpha delta charlie
echo foxtrot charlie golf alpha bravo delta hotel

Four runs, four orders. Nothing changed but the process.

This is not sloppiness, and it is not “hash tables are unordered, deal with it” — Rust goes further than that deliberately. HashMap‘s default hasher is RandomState, which pulls a fresh random key per map, from a per-thread seed initialised once per process. Two maps in the same program have different orders. The same map in two runs has different orders.

Why: hash flooding

If your hash function is fixed and public, an attacker who can choose your keys can choose keys that all land in the same bucket. Every insert and lookup then degrades from O(1) to O(n), the table becomes a linked list, and a request that should take a microsecond takes a second. In 2011 this took down the default configuration of most web frameworks at once — POST a form with a few thousand colliding parameter names and the server melts. It is called a HashDoS, and it is a real, cheap, remote denial of service.

You cannot construct colliding keys for a hash function whose key you do not know. Rust made the safe-by-default choice: SipHash 1-3 with a per-map random key. You pay a little throughput on every hash, and you are immune to a whole attack class without having to have heard of it. If you have measured, and your keys are trusted, and hashing is your bottleneck, you can swap the hasher — HashMap<K, V, S> is generic over it — but that is an informed decision, not a default.

The randomisation also has a second, quieter benefit: it makes it impossible to accidentally depend on the order. In a language where the order is arbitrary-but-stable, code that relies on it works for years and then breaks when someone upgrades the runtime. Here it breaks on the second run, at your desk.

::: question So when is it fine to iterate a HashMap? Whenever the operation does not care about order: summing values, counting entries, finding a maximum, building another unordered collection, checking a predicate over all entries. Order-independence is a property of what you are doing, not of the collection.

It stops being fine the moment the result escapes in an ordered form — printed, serialised, hashed, compared, or returned as a Vec. Then you sort, or you use a BTreeMap. clippy has a restriction lint, iter_over_hash_type, for codebases that want to ban the whole thing; it is off by default because the ban is too blunt for most projects. :::

The compile error in the starter

The starter aggregates correctly and then tries the obvious sort:

out.sort_by_key(|(k, total)| (-total, k));

error: lifetime may not live long enough

sort_by_key has signature fn sort_by_key<K: Ord, F: FnMut(&T) -> K>(...). The key type K is a single type chosen once, for the whole call — it has no connection to the lifetime of the &T handed to the closure. So the closure is not allowed to return anything borrowed from its argument. It can return total (a copy), or k.clone() (an owned String), but not k itself.

This is not a wart; it is what makes sort_by_key able to hold keys while it shuffles elements around. But it does mean the “sort by a field of a struct” reflex hits a wall the first time the field is a String.

Two ways out:

// 1. Clone the key. Correct, allocates once per comparison batch.
out.sort_by_key(|(k, total)| (-total, k.clone()));

// 2. Compare instead of key-ing. No allocation, and it reads as the spec.
out.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));

Read the second one out loud: “compare b’s total to a’s total” — arguments swapped, which is what makes it descending — “and if that is Equal, compare a’s key to b’s key” ascending. Ordering::then_with chains tie-breakers and only evaluates the next one when the previous was Equal.

A trap in the first version worth naming

-total to reverse a sort is a habit worth losing. This whole site compiles with -O, which means overflow checks are off: -i64::MIN does not panic, it wraps back to i64::MIN and your “descending” order puts the smallest value first. std::cmp::Reverse exists for this — sort_by_key(|x| Reverse(x.1)) — and it works for every Ord type, not just the negatable ones.

Which map should you have used?

For this problem: a HashMap to aggregate (many lookups, order irrelevant), then a sorted Vec to return. That is the shape the signature asks for and it is the right shape in general.

But notice how often the answer is just “use a BTreeMap“. If the data is small, or you were going to sort at the end anyway, BTreeMap gives you ordered iteration for free, no randomisation, no sort step, and reproducible output in tests and logs. Its O(log n) lookups lose to a hash map in theory and frequently win in practice for small maps, because it does not hash and it is cache-friendly. Reach for HashMap when lookups dominate; reach for BTreeMap when order or determinism is part of the answer.

Remember the grade is compile + tests + clippy -D warnings.