Hash Maps and Hash Sets

HashSet Operations

HashSet<T, S> provides $O(1)$ average-case insertion, removal, membership testing, and subset/superset/disjoint queries for unique elements implementing Eq + Hash.

Single-Element and Predicate Operations on HashSet<T>

Method Signature Return Type Behavior
set.insert(val) fn insert(&mut self, value: T) -> bool bool Inserts val if absent (true); if an equal element already exists, keeps the old element and returns false
set.replace(val) fn replace(&mut self, value: T) -> Option<T> Option<T> Inserts val, replacing and returning the existing equal element Some(old) if present
set.contains(&q) fn contains<Q>(&self, value: &Q) -> bool bool Returns true if the set contains an element equal to q
set.get(&q) fn get<Q>(&self, value: &Q) -> Option<&T> Option<&T> Returns a reference to the actual stored element &T matching q
set.remove(&q) fn remove<Q>(&mut self, value: &Q) -> bool bool Removes the matching element and returns true if it was present
set.take(&q) fn take<Q>(&mut self, value: &Q) -> Option<T> Option<T> Removes and returns ownership of the matching element Some(T)
set.retain(f) fn retain<F: FnMut(&T) -> bool>(&mut self, f: F) () Keeps only elements where f(&elem) returns true

Comparing insert() vs. replace(), and remove() vs. take()

When T is a custom struct whose Eq and Hash implementations compare only an ID field (or case-insensitive text), .insert(new_val) leaves the old value untouched if an equal item is already in the set, whereas .replace(new_val) swaps in the new item and returns the old one:

use std::collections::HashSet;

fn main() {
    let mut tags = HashSet::from([String::from("rust"), String::from("systems")]);

    // 1. `insert` returns `true` for a new element, `false` for a duplicate:
    println!("Insert 'async': {}", tags.insert(String::from("async")));
    println!("Insert 'rust':  {}", tags.insert(String::from("rust")));

    // 2. Querying with `&str` via `get` and `take` (recovering the owned `String`):
    println!("Get 'systems':  {:?}", tags.get("systems"));
    if let Some(owned_tag) = tags.take("systems") {
        println!("Taken owned String: '{owned_tag}'");
    }
    println!("Contains 'systems' after take: {}", tags.contains("systems"));
}

Insert 'async': true
Insert 'rust':  false
Get 'systems':  Some("systems")
Taken owned String: 'systems'
Contains 'systems' after take: false

Relational Set Predicates (is_disjoint, is_subset, is_superset)

Method Mathematical Relation Meaning
a.is_disjoint(&b) $A \cap B = \emptyset$ true if a and b share no elements in common
a.is_subset(&b) $A \subseteq B$ true if every element of a is also in b (short-circuits to false in $O(1)$ if a.len() > b.len())
a.is_superset(&b) $A \supseteq B$ Equivalent to b.is_subset(&a) 
use std::collections::HashSet;

fn main() {
    let read_write = HashSet::from(["read", "write"]);
    let all_perms = HashSet::from(["read", "write", "delete", "admin"]);
    let public_only = HashSet::from(["public"]);

    println!("read_write ⊆ all_perms:     {}", read_write.is_subset(&all_perms));
    println!("all_perms ⊇ read_write:     {}", all_perms.is_superset(&read_write));
    println!("read_write ∩ public = ∅:    {}", read_write.is_disjoint(&public_only));
}

read_write ⊆ all_perms:     true
all_perms ⊇ read_write:     true
read_write ∩ public = ∅:    true