HashMap iteration order is random

Add up (key, value) pairs into one total per key, using a HashMap for the lookups, and return the totals in a deterministic order: the same input always gives the same output.

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

The contract

• Sum the values for each key. Return exactly one (key, total) per distinct key.
• Order the result by total, largest first. Where two totals are equal, order those entries by key, ascending.
• "Ascending key" means Rust's ordering on String, which compares the UTF-8 bytes. For example, every uppercase ASCII letter sorts before every lowercase one, so "Zeta" comes before "alpha".
• Keys are compared exactly: "a" and "A" are different keys.
• An empty input returns an empty Vec.
• Values may be negative or zero. The tests keep every value, every running total and every final total inside the i64 range, so plain += is enough.

Example: [("b", 5), ("a", 5), ("c", 1), ("d", 1), ("e", 9)] returns [("e", 9), ("a", 5), ("b", 5), ("c", 1), ("d", 1)]. e has the largest total; a and b tie at 5 and appear in key order, as do c and d.

Several tests contain ties on purpose. If you return entries in the order the map happens to iterate them, you will not fail consistently. A test may pass on one run and fail on the next.

HashMap iteration order changes between runs

A hasher is the function a HashMap uses to turn a key into the number that decides where the key is stored. Iterating a map visits keys in storage order, so the order depends on the hasher.

The program below inserts the same eight keys in the same order and prints them by iterating the map:

use std::collections::HashMap;

fn main() {
    let mut m = HashMap::new();
    for k in ["alpha", "bravo", "charlie", "delta", "echo", "foxtrot", "golf", "hotel"] {
        m.insert(k, 0);
    }
    let keys: Vec<&str> = m.keys().copied().collect();
    println!("{}", keys.join(" "));
}

Four separate runs of the same compiled program printed:

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

Your runs will print different orders again. The reason is the default hasher, RandomState. Its hash keys come from random seed data generated once per thread, and each new RandomState gets keys that differ from the previous one. So the order of one map usually changes from one run of the program to the next, and two maps in the same run usually iterate in different orders too. In practice, iterating one unchanged map twice in the same run gives the same order, but the documentation only promises an "arbitrary order", so do not build on even that.

Why the hasher is randomized: hash flooding

Keys that land in the same storage slot are said to collide, and the table has to do extra work to tell them apart. If the hash function is fixed and public, someone who controls your keys (for example, the field names in a web form) can pick many keys that collide. Inserts and lookups then slow from roughly constant time to time proportional to the number of colliding keys, and a modest request can use a large amount of CPU. This denial of service attack is called hash flooding or HashDoS. Public demonstrations in 2011 showed it working against the default hash tables of several popular web platforms.

Choosing colliding keys is much harder when the attacker does not know the hash key. That is why the standard library's default hasher is randomly seeded and designed to resist HashDoS. The documentation says the algorithm is currently SipHash 1-3 and may change. The cost is some hashing speed. If your keys are trusted and you have measured that hashing is a bottleneck, you can choose a different hasher, because HashMap<K, V, S> is generic over the hasher type S.

A side effect is that code which wrongly depends on iteration order tends to fail early, often in tests, instead of working by accident until something else changes.

The compile error in the starter

The starter adds up the totals correctly, then tries this sort:

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

Rust 1.98 rejects it:

error: lifetime may not live long enough

The note under the error says the closure's return type is (i64, &String) and that returning it requires the borrowed argument to outlive the returned value. The signature of sort_by_key is:

pub fn sort_by_key<K, F>(&mut self, f: F)
where
    F: FnMut(&T) -> K,
    K: Ord,

K is one type chosen for the whole call, and the signature does not tie it to the short borrow &T that each call of the closure receives. So the key cannot borrow from the element. Returning *total (a copied i64) or k.clone() (a new String) is allowed; returning k itself is not.

Two ways to make it compile:

// 1. Clone the key. sort_by_key calls the closure for both sides of every
//    comparison, so this allocates a new String each time.
out.sort_by_key(|(k, total)| (std::cmp::Reverse(*total), k.clone()));

// 2. Write a comparator. Nothing is cloned.
out.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));

How to read the second one: b.1.cmp(&a.1) compares the totals with the arguments swapped, which puts larger totals first. then_with runs its closure only when that first comparison returns Ordering::Equal, and a.0.cmp(&b.0) then orders the keys ascending.

If you want a key function but each key is expensive to build, sort_by_cached_key calls the closure once per element instead of once per comparison side.

Do not negate to reverse an order

-total looks like an easy way to sort descending, but it overflows for i64::MIN, whose negation does not fit in an i64. What happens then depends on the build. With overflow checks enabled (the default for debug builds) the program panics. With overflow checks disabled (the default for optimized builds such as rustc -O, which is how this site's runtime compiles Rust) the negation wraps back to i64::MIN, so the smallest total sorts first instead of last. The tests here do not include i64::MIN, but the habit is worth dropping. Swap the operands of cmp, as above, or wrap the key in std::cmp::Reverse, for example sort_by_key(|x| Reverse(x.1)). Reverse works for any Ord type, including ones that cannot be negated, such as String.

Which map should you use?

For this problem, use a HashMap to build the totals (many lookups, order does not matter), then sort a Vec to return. That is the shape the signature asks for.

A BTreeMap is the other common choice. It keeps keys sorted, so iterating it gives a reproducible order without randomization. Its lookups take O(log n) time instead of the hash map's expected O(1); which one is faster for your data is something to measure. Note that BTreeMap orders by key, while this problem orders by total first, so even with a BTreeMap you would still need to sort the result.

Grading compiles your code, runs the tests, and runs Clippy with warnings treated as errors.