Hash and the Hash/Eq contract

Count words case-insensitively.

pub fn count_case_insensitive(words: Vec<String>) -> Vec<(String, u64)>

["Hello", "HELLO"] collapses to one entry, ("hello", 2). Lower-case every key on the way out and sort the result before returning it.

The mechanism is fixed: wrap the word in struct CiWord(String), give it a PartialEq that ignores ASCII case, and use it as a HashMap key.

The contract

a == b   implies   hash(a) == hash(b)

That is the whole rule, and every hash table in existence depends on it. A HashMap finds a key by hashing it to a bucket and then comparing within that bucket. If two equal values hash to different buckets, the lookup goes to the wrong bucket, finds nothing, and reports the key as absent — the key you just inserted.

Note the implication only runs one way. Unequal values may hash the same; that is an ordinary collision and the map handles it. It is the other direction that is fatal.

Why this is the best example in the language

This is a cross-trait invariant. PartialEq lives in one impl, Hash in another, and no type signature connects them. The compiler cannot check it. There is no runtime assertion. The failure is silent, distant from its cause, and often intermittent — the sort of bug that eats an afternoon.

So clippy checks it, and denies it by default. Derive one and hand-write the other and you get:

error: you are deriving `Hash` but have implemented `PartialEq` explicitly

The starter ships exactly that: a derived Hash (which hashes the bytes, so "Hello" and "HELLO" hash differently) beside a case-insensitive PartialEq. Run it and look at the output as well as the lint — every word gets its own entry with a count of 1, and two entries render as the same lower-cased string. That is what a broken contract looks like from the outside.

Writing Hash by hand

use std::hash::{Hash, Hasher};

impl Hash for CiWord {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.0.to_ascii_lowercase().hash(state);
    }
}

You do not compute a hash value. You feed bytes to a hasher the caller supplies — which is how Rust lets the collection choose its own hash algorithm (and randomise its seed against collision attacks) while your type only decides what is significant.

The rule for writing it: hash exactly the parts your eq compares. Here eq compares the lower-cased form, so hash hashes the lower-cased form. If eq ignores a field, hash must ignore it too.

Two more facts

Hash normalisation is why eq_ignore_ascii_case and not to_lowercase. Unicode case folding is not a simple per-character map — ß upper-cases to SS, Turkish dotless ı has its own rules — so “case-insensitive” is a bigger promise than it looks. This problem is explicitly ASCII case-insensitive, and one of the hidden tests checks that you did not quietly claim more. (As a bonus, eq_ignore_ascii_case is dramatically faster than allocating a lower-cased String per comparison — measured at 32x on this toolchain.)

HashMap iteration order is not deterministic. It is not insertion order, it is not sorted, and it deliberately varies between runs because the hasher is seeded randomly. Any function that returns data out of a HashMap and wants a stable answer must sort it. Treat that as a standing rule for every problem in this course that touches a hash map.

Neighbouring lints

impl_hash_borrow_with_str_and_bytes (deny) catches a subtler version of the same contract violation involving Borrow. mutable_key_type warns about keys with interior mutability — a key whose hash can change after insertion breaks the map just as thoroughly. manual_hash_one suggests BuildHasher::hash_one for the one-shot case.

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