HashSet

A HashSet<T> is an unordered collection of unique elements, implemented internally as a HashMap<T, ()>. It provides average $O(1)$ time complexity for insertions, removals, and lookups by utilizing a hash table to map elements to memory buckets.

Trait Requirements

To store a type T in a HashSet, the type must implement two core traits:

• std::cmp::Eq: Provides strict equivalence relations. This is required to resolve hash collisions when two distinct elements yield the same hash code.
• std::hash::Hash: Allows the type to be fed into a hashing algorithm to compute a deterministic u64 hash value.

Initialization

A HashSet can be instantiated empty, with a pre-allocated capacity to avoid reallocation overhead, or collected from an iterator.

use std::collections::HashSet;

// Empty initialization
let mut empty_set: HashSet<i32> = HashSet::new();

// Initialization with pre-allocated capacity
let mut cap_set: HashSet<i32> = HashSet::with_capacity(10);

// Initialization from an iterator
let iter_set: HashSet<i32> = vec![1, 2, 3].into_iter().collect();

// Initialization from an array (Rust 1.56+)
let array_set: HashSet<i32> = HashSet::from([1, 2, 3]);

Core Operations

The primary API methods handle state mutation and containment checks. Because a set guarantees uniqueness, insertion and removal methods return a bool indicating whether the operation mutated the set.

let mut set = HashSet::new();

// insert() returns true if the element was not already present
let is_new = set.insert("Alpha"); // true
let is_new_again = set.insert("Alpha"); // false

// contains() checks for the existence of an element by reference
let has_alpha = set.contains("Alpha"); // true

// remove() returns true if the element was present and successfully removed
let was_removed = set.remove("Alpha"); // true

Algebraic Set Operations

HashSet provides methods for mathematical set operations. These methods return iterators over references to the elements, meaning they do not consume the original sets.

let set_a = HashSet::from([1, 2, 3]);
let set_b = HashSet::from([2, 3, 4]);

// Intersection: Elements present in both sets -> [2, 3]
let intersection: HashSet<_> = set_a.intersection(&set_b).copied().collect();

// Union: Elements present in either set -> [1, 2, 3, 4]
let union: HashSet<_> = set_a.union(&set_b).copied().collect();

// Difference: Elements in set_a but not in set_b -> [1]
let difference: HashSet<_> = set_a.difference(&set_b).copied().collect();

// Symmetric Difference: Elements in one set or the other, but not both -> [1, 4]
let sym_diff: HashSet<_> = set_a.symmetric_difference(&set_b).copied().collect();

Hashing Algorithm and Performance

By default, HashSet uses SipHash 1-3. This is a cryptographically resistant hashing algorithm designed to protect against Hash Denial-of-Service (HashDoS) attacks.

While secure, SipHash is not the most performant algorithm for small keys (like integers). The underlying hasher can be swapped by using HashSet::with_hasher and providing a custom BuildHasher implementation (e.g., FxHasher or AHash).

use std::collections::HashSet;
use std::hash::BuildHasherDefault;
// Assuming a third-party hasher like `rustc_hash::FxHasher` is in scope
// use rustc_hash::FxHasher;

// Type alias for a HashSet using a custom, non-cryptographic hasher
// type FxHashSet<T> = HashSet<T, BuildHasherDefault<FxHasher>>;

// let mut fast_set: FxHashSet<i32> = HashSet::default();

Memory and Iteration

• Memory Layout: Elements are stored in a contiguous heap allocation. The capacity doubles when the load factor exceeds the internal threshold.
• Iteration Order: The order in which elements are yielded during iteration is arbitrary and non-deterministic. It will change across different program executions due to the randomized state of the default SipHash algorithm.

Master Rust with Deep Grasping Methodology!

Learn More