Standard Collections

HashSet<T>

HashSet<T, S = RandomState> (std::collections::HashSet) is an unordered collection of unique values implemented as a thin zero-overhead wrapper around HashMap<T, (), S>, providing $O(1)$ average-case membership testing, insertion, removal, and mathematical set operations.

Memory Representation

Because the unit type () is a zero-sized type (ZST) occupying 0 bytes, HashMap<T, ()> stores only the control bytes and the elements T themselves without wasting a single byte on values. Every element T must implement Eq + Hash.

Core Membership and Set Algebra Operations

Operation Method / Operator Return Type Meaning
Insert unique item set.insert(x) bool Returns true if x was newly inserted, false if already present
Membership check set.contains(&q) bool $O(1)$ average check whether q is in set
Remove item set.remove(&q) bool Returns true if q was present and removed
Union ($A \cup B$) a.union(&b) or &a | &b Union<'_, T, S> / HashSet<T> Elements in a, b, or both
Intersection ($A \cap B$) a.intersection(&b) or &a & &b Intersection<'_, T, S> / HashSet<T> Elements present in both a and b
Difference ($A \setminus B$) a.difference(&b) or &a - &b Difference<'_, T, S> / HashSet<T> Elements in a that are not in b
Symmetric difference ($A \triangle B$) a.symmetric_difference(&b) or &a ^ &b SymmetricDifference<'_, T, S> / HashSet<T> Elements in exactly one of a or b
Subset / Disjoint a.is_subset(&b) / a.is_disjoint(&b) bool Tests $A \subseteq B$ or $A \cap B = \emptyset$ 
use std::collections::HashSet;

fn main() {
    let mut allowed = HashSet::from(["read", "write"]);

    println!("Insert 'execute': {}", allowed.insert("execute"));
    println!("Insert 'read':    {}", allowed.insert("read")); // Already present -> false

    let requested = HashSet::from(["read", "admin"]);

    // Lazy iterator over the intersection without allocating a new HashSet:
    let granted: Vec<&str> = allowed.intersection(&requested).copied().collect();
    let denied: Vec<&str> = requested.difference(&allowed).copied().collect();

    println!("Granted: {granted:?}");
    println!("Denied:  {denied:?}");
}

Insert 'execute': true
Insert 'read':    false
Granted: ["read"]
Denied:  ["admin"]