Step 4 of 6

HashSet: have I seen this before?

A HashSet is like a HashMap with keys and no values: a collection of unique values with a very fast "is this in here?" check. Its insert returns a bool: true if the value was new, false if it was already there. That makes "have I seen this before?" a single call:

use std::collections::HashSet;

fn main() {
    let log = ["login ana", "login bo", "login ana", "logout bo", "login cy", "login ana"];
    let mut seen = HashSet::new();
    for line in log {
        if seen.insert(line) {
            println!("new: {line}");
        } else {
            println!("repeat: {line}");
        }
    }
    println!("{} unique lines", seen.len());
}

new: login ana
new: login bo
repeat: login ana
new: logout bo
new: login cy
repeat: login ana
4 unique lines

The output follows the order of the log array, which is fixed. We never print the set itself, because a HashSet has the same unpredictable order as a HashMap.

Other methods: contains(&value), remove(&value) (returns whether it was there), len, is_empty, and for x in &set to visit every element (in no particular order).

BTreeSet: unique and sorted

BTreeSet is to HashSet what BTreeMap is to HashMap: the same idea, kept in sorted order, so printing it is safe.

use std::collections::BTreeSet;

fn main() {
    let mut tags = BTreeSet::new();
    for t in ["rust", "web", "cli", "rust", "async", "web"] {
        tags.insert(t);
    }
    println!("{:?}", tags);
    println!("{} tags, has cli: {}", tags.len(), tags.contains("cli"));
}

{"async", "cli", "rust", "web"}
4 tags, has cli: true

Sets versus sort + dedup

In the vectors module you removed duplicates with sort then dedup. That works, but it loses the original order and needs all the data first. A set keeps values unique as they arrive, and checking membership doesn't slow down as it grows. A very common pattern: a HashSet to remember what you've seen, plus a Vec to keep the output in its original order.

Common mistakes

• Checking, then inserting: if !seen.contains(&x) { seen.insert(x); ... } looks the value up twice. if seen.insert(x) { ... } does both in one step.
• Printing a HashSet (or comparing its {:?} text in a test): the order changes between runs. Sort, or use a BTreeSet.
• f64 values in a set. Floats aren't Eq or Hash (NaN again), so HashSet<f64> won't let you insert. The last step covers which types can be keys.

Your task

Write fn first_repeat(ids: &[u32]) -> Option<u32> that scans the ids in order and returns the first one that appears for the second time, or None if every id is unique. Use a HashSet.

Challenge 2

Write fn dedupe_keep_order(lines: &[&str]) -> Vec<String> that removes repeated lines but keeps the first occurrence of each, in the original order (sort + dedup would scramble the order).

Challenge 3

A web server logs visits as user page lines. Print how many distinct users and distinct pages there were, then every distinct page in alphabetical order:

users: 3
pages: 2
about
home

Use a HashSet for the users (you only need the count) and a BTreeSet for the pages (you print them).

Previous: Counting with entry Next: Set operations: union, intersection, difference