Step 6 of 6

Your own keys, and grouping

Any type can be a value in a map. A key has to support what the map does with it:

• HashMap and HashSet hash keys and compare them for equality, so keys need the traits Hash and Eq.
• BTreeMap and BTreeSet sort keys, so keys need Ord.

A trait is a named set of abilities a type can have (module 22 covers them). Strings, integers, chars, bools, and tuples and arrays of them already have these. Your own structs and enums don't, until you ask:

use std::collections::HashMap;

struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut seen: HashMap<Point, u32> = HashMap::new();
    seen.insert(Point { x: 1, y: 2 }, 1);
}

error[E0599]: the method `insert` exists for struct `HashMap<Point, u32>`, but its trait bounds were not satisfied

The fix is one line above the type: #[derive(PartialEq, Eq, Hash)]. You've used #[derive(Debug)] already; derive writes these abilities for you too. PartialEq and Eq give == (field by field), and Hash computes a hash from all the fields. Deriving them together guarantees the rule maps rely on: equal keys always have equal hashes.

use std::collections::HashMap;

#[derive(Debug, PartialEq, Eq, Hash)]
enum Priority {
    Low,
    High,
    Urgent,
}

fn main() {
    let tickets = [(101, Priority::High), (102, Priority::Low), (103, Priority::Urgent), (104, Priority::High)];

    let mut by_priority: HashMap<Priority, Vec<u32>> = HashMap::new();
    for (id, p) in tickets {
        by_priority.entry(p).or_default().push(id);
    }

    for p in [Priority::Urgent, Priority::High, Priority::Low] {
        println!("{:?}: {:?}", p, by_priority[&p]);
    }
}

Urgent: [103]
High: [101, 104]
Low: [102]

• The enum derives PartialEq, Eq and Hash, so it can be a key (and Debug, so it can be printed).
• HashMap<Priority, Vec<u32>> maps each key to a list: this is grouping, one of the most common map patterns.
• entry(p).or_default() gives the existing list, or a new empty Vec the first time, and .push(id) adds to it.
• Printing loops over a fixed array of priorities rather than over the map, so the order is ours, not the hash's.

Tuples as keys

Tuples of hashable types are hashable, which makes sparse grids easy: store only the cells that hold something.

use std::collections::HashMap;

fn main() {
    let mut board: HashMap<(usize, usize), char> = HashMap::new();
    board.insert((0, 0), 'X');
    board.insert((1, 1), 'O');
    board.insert((0, 2), 'X');

    for row in 0..3 {
        let mut line = String::new();
        for col in 0..3 {
            match board.get(&(row, col)) {
                Some(&mark) => line.push(mark),
                None => line.push('.'),
            }
        }
        println!("{line}");
    }
}

X.X
.O.
...

Common mistakes

• Floats as keys. f64 isn't Eq or Hash (NaN isn't equal to itself), so HashMap<f64, _> can't insert. Use integers (cents instead of dollars, millimeters instead of meters) or a string form.
• Deriving Hash without Eq (or the other way round): derive both, plus PartialEq.
• Expecting derives on a struct with an un-hashable field. If a field is an f64, the derive fails for the same reason.

Your task

Write fn group_by_department(staff: &[(&str, &str)]) -> HashMap<String, Vec<String>>. Each pair is (name, department). Return a map from each department to the names in it, in the order they appear in staff.

Challenge 2

A cinema books seats in a HashSet<Seat>. Make Seat usable in a HashSet (derive what it needs), then write fn book(booked: &mut HashSet<Seat>, seat: Seat) -> String that returns "booked row R seat N" if the seat was free (and records it), or "row R seat N is taken" if it was already booked.

Challenge 3

A robot starts at (0, 0) and reads one line of moves: U (y + 1), D (y - 1), L (x - 1), R (x + 1); ignore any other character. Using a HashSet<(i32, i32)>, print how many distinct cells it visited (including the start), and how many moves landed on a cell it had already visited:

visited 4 cells
revisited 1 times

(That's the output for URDL, which walks a square back to the start.)

Previous: Set operations: union, intersection, difference