Rust HashSet

A HashSet is a collection that stores each value at most once. It records which values are present.

Counting different values by hand takes a loop

A plain Vec keeps repeats, so counting the different values means checking every item against the ones before it:

fn main() {
    let logins = vec!["ada", "bo", "ada", "cy", "bo"];
    let mut unique = 0;
    for (i, name) in logins.iter().enumerate() {
        if !logins[..i].contains(name) {
            unique += 1;
        }
    }
    println!("{} logins, {} different people", logins.len(), unique);
}

Each value at most once

insert answers true when the value was new. It answers false when it was already there. The set keeps one copy either way:

let mut seen = HashSet::new();
println!("first = {} again = {}", seen.insert(7), seen.insert(7));

Ask whether a value is in the set

contains tests membership, and len counts the different values:

let seen: HashSet<i32> = [7, 8].into_iter().collect();
println!("has 7 = {} has 9 = {} count = {}", seen.contains(&7), seen.contains(&9), seen.len());

In either set: union

union gathers every value from both sets. Set results arrive in no promised order, so this collects and sorts them before printing:

let a: HashSet<i32> = [1, 2, 3].into_iter().collect();
let b: HashSet<i32> = [2, 3, 4].into_iter().collect();
let mut u: Vec<i32> = a.union(&b).copied().collect();
u.sort();
println!("union = {:?}", u);

In a but not in b: difference

difference keeps the values the second set does not have:

let a: HashSet<i32> = [1, 2, 3].into_iter().collect();
let b: HashSet<i32> = [2, 3, 4].into_iter().collect();
let mut d: Vec<i32> = a.difference(&b).copied().collect();
d.sort();
println!("only a = {:?}", d);

Is one set inside another? (is_subset, is_superset)

is_subset asks whether every value of one set lives in another — the shape of a permission check. is_superset asks the same question from the bigger side:

use std::collections::HashSet;

let needed: HashSet<&str> = ["read", "write"].into_iter().collect();
let granted: HashSet<&str> = ["read", "write", "admin"].into_iter().collect();
println!("all covered = {}", needed.is_subset(&granted));
println!("covers needs = {}", granted.is_superset(&needed));

No overlap at all (is_disjoint)

is_disjoint is true only when the two sets share not a single value:

use std::collections::HashSet;

let morning: HashSet<&str> = ["gym", "run"].into_iter().collect();
let evening: HashSet<&str> = ["read", "code"].into_iter().collect();
println!("no overlap = {}", morning.is_disjoint(&evening));

Example

use std::collections::HashSet;
fn main() {
    let mut a: HashSet<i32> = vec![1, 2, 3].into_iter().collect();
    let b: HashSet<i32> = vec![2, 3, 4].into_iter().collect();
    println!("add 4 = {} add 4 again = {}", a.insert(4), a.insert(4));
    println!("has 4 = {} len = {}", a.contains(&4), a.len());
    let mut union: Vec<i32> = a.union(&b).copied().collect();
    union.sort();
    println!("union = {:?}", union);
    let mut diff: Vec<i32> = a.difference(&b).copied().collect();
    diff.sort();
    println!("difference = {:?}", diff);
    let mut both: Vec<i32> = a.intersection(&b).copied().collect();
    both.sort();
    println!("intersection = {:?}", both);
    let mut either: Vec<i32> = a.symmetric_difference(&b).copied().collect();
    either.sort();
    println!("symmetric difference = {:?}", either);
}

Key points

A HashSet<T> stores each value at most once — inside std it is a HashMap<T, ()> where only the keys matter
A set is a list of members with no repeats: a value is in the set, or it is not.
A Vec answers that question only by searching every item, one by one.

In this example, set a starts as 1, 2, 3 and set b as 2, 3, 4. Adding 4 to a works the first time. It returns true. Adding it again returns false. A set holds each value once. union gathers 1 to 4. difference keeps only 1, the value in a but not in b. intersection keeps 2, 3, 4, the values in both — 4 is in both because a gained it. symmetric difference keeps only 1, the value in exactly one set. Each result is sorted before printing, because a set promises no order.

Note

Reach for a HashSet when the question is "have I seen this before?"

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

use std::collections::HashSet;
fn main() {
    let mut a: HashSet<i32> = vec![1, 2, 3].into_iter().collect();
    let b: HashSet<i32> = vec![2, 3, 4].into_iter().collect();
    println!("add 4 = {} add 4 again = {}", a.insert(4), a.insert(4));
    println!("has 4 = {} len = {}", a.contains(&4), a.len());
    let mut union: Vec<i32> = a.union(&b).copied().collect();
    union.sort();
    println!("union = {:?}", union);
    let mut diff: Vec<i32> = a.difference(&b).copied().collect();
    diff.sort();
    println!("difference = {:?}", diff);
    let mut both: Vec<i32> = a.intersection(&b).copied().collect();
    both.sort();
    println!("intersection = {:?}", both);
    let mut either: Vec<i32> = a.symmetric_difference(&b).copied().collect();
    either.sort();
    println!("symmetric difference = {:?}", either);
}

Exercise

What does a.difference(&b) give?

Every value in either set Values in a but not in b Values in both sets Values in exactly one set