HashMap fundamentals: get, get_mut and the Hash/Eq contract

Two functions over a HashMap<String, i64> built from a list of pairs.

pub fn lookup_report(pairs: Vec<(String, i64)>, queries: Vec<String>) -> Vec<i64>
pub fn bump_present(pairs: Vec<(String, i64)>, keys: Vec<String>) -> Vec<(String, i64)>

Build the map by inserting the pairs in order — so a duplicate key keeps the last value.

• lookup_report answers each query with its value, or -1 if the key is absent. Same order as queries.
• bump_present adds 1 to the value of each key in keys that is already in the map, ignoring the rest, then returns every entry as a (key, value) pair sorted by key ascending. A key listed three times is bumped three times.

Why the output has to be sorted

A HashMap has no order. Iterating one gives you the entries in whatever order the hash function and the current table layout produce, and Rust goes further than most languages: the order is randomised per map, per process. If you returned map.into_iter().collect() directly, this problem would pass on your machine and fail on the grader, or pass twice and fail the third time. Sorting is not decoration here, it is what makes the function a function. The next problem in this track is entirely about that.

The papercut: get takes &str, entry takes String

This is the single most common HashMap confusion in Rust, and the starter walks you into it:

let mut m: HashMap<String, i64> = HashMap::new();
m.get("a");            // fine
m.contains_key("a");   // fine
m.remove("a");         // fine
m.entry("a");          // error[E0308]: expected `String`, found `&str`

Why the asymmetry? Because of what each method might do.

get, contains_key and remove only ever look. They are generic:

pub fn get<Q>(&self, k: &Q) -> Option<&V>
where K: Borrow<Q>, Q: Hash + Eq + ?Sized

String: Borrow<str> holds, so you may hand them a &str — they hash it and compare it against the stored keys, and never need to keep it.

entry might insert. If the key turns out to be missing, or_insert(0) has to store a key in the table, and a borrowed &str cannot be stored in a HashMap<String, _>. So entry demands the owned key up front, whether or not it ends up needing it. Remember that: it is the reason the Entry API sometimes loses a benchmark, which you will measure in the next problem but one.

For bump_present you never need to insert, so get_mut is the right tool and the question does not arise.

Indexing panics

The starter also writes map[q], because that is what square brackets mean in every scripting language. In Rust, Index for HashMap is implemented as “unwrap the get“ — a missing key is a panic, not a None, not a default-constructed zero:

thread 'main' panicked at ...

One of the test cases queries a key that is not there, so you will meet it. This is a deliberate std design: HashMap gives you Index for the case where you have already proved the key exists and want terse code, and gives you get — returning Option — for every other case. Reaching for the panicking one by reflex is how a service falls over on a request nobody anticipated.

map.get(q) gives Option<&i64>. .copied() turns it into Option<i64>, and .unwrap_or(-1) supplies the sentinel.

::: question map.get(q).copied().unwrap_or(-1) — why not map.get(q).unwrap_or(&-1)? Both compile. The second borrows a temporary -1 and then you have an &i64 you must deref anyway. copied() (or cloned() for non-Copy values) moves the “get out of the reference” step earlier, where it is cheap and obvious, and leaves you with a plain Option<i64> that behaves like a value.

As a rule: convert Option<&T> to Option<T> as soon as T: Copy. It makes every downstream combinator read better. :::

The contract you are relying on

HashMap<K, V> requires K: Hash + Eq, and it requires them to agree:

if a == b, then hash(a) == hash(b)

Nothing in the type system enforces that. If you break it, the map does not crash — it quietly loses entries, because the lookup hashes to a bucket the key was never stored in. That is the kind of bug that survives a code review and shows up as “sometimes the cache misses”.

The usual way people break it is by deriving one half and hand-writing the other. clippy denies that by default:

#[derive(Hash)]
struct Key { id: u32, label: String }

impl PartialEq for Key {
    fn eq(&self, other: &Self) -> bool { self.id == other.id }  // ignores label
}
// error: you are deriving `Hash` but have implemented `PartialEq` explicitly

Two Keys with the same id and different labels are now equal but hash differently. The lint (derived_hash_with_manual_eq) is one of the small number clippy denies rather than warns about, which tells you how it rates the consequences.

A second way to break it is a key whose hash can change while it is in the map — a key containing a Cell, a RefCell, or an atomic. clippy’s mutable_key_type exists for exactly that. The map is not watching; if the key mutates, the entry becomes unreachable.

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