Standard Collections

HashSet vs. BTreeSet

HashSet<T> (backed by HashMap<T, ()>) and BTreeSet<T> (backed by BTreeMap<T, ()>) both store unique elements and support mathematical set operations (union, intersection, difference, symmetric_difference), differing in ordering guarantees and element trait bounds.

Side-by-Side Comparison

Dimension HashSet<T> BTreeSet<T>
Required element trait bounds T: Eq + Hash T: Ord
.contains(&x) / .insert(x) / .remove(&x) $O(1)$ average $O(\log n)$
Iteration order Arbitrary / nondeterministic Sorted ascending (T: Ord)
.first() / .last() / .pop_first() / .pop_last() Not supported $O(\log n)$
Subrange queries (set.range(a..=b)) Not supported $O(\log n + k)$
Set algebra (a.intersection(&b)) $O(\min(|a|, |b|))$ hash probes $O(|a| + |b|)$ sorted merge
Implements Hash and Ord itself? No Yes (BTreeSet<BTreeSet<T>> is valid)

Deduplicating With vs. Without Sorted Order

use std::collections::{BTreeSet, HashSet};

fn main() {
    let inputs = [40, 10, 30, 20, 10, 40];

    // 1. Fast membership check where order does not matter:
    let hash_set: HashSet<i32> = inputs.into_iter().collect();
    println!("HashSet contains 30: {}", hash_set.contains(&30));

    // 2. Deduplication that also yields elements in sorted order:
    let btree_set: BTreeSet<i32> = inputs.into_iter().collect();
    let sorted_vec: Vec<i32> = btree_set.iter().copied().collect();
    println!("BTreeSet sorted:     {sorted_vec:?}");
}

HashSet contains 30: true
BTreeSet sorted:     [10, 20, 30, 40]

Comparing Set Algebra on HashSet vs. BTreeSet

Both types provide identical method signatures for .union(&other), .intersection(&other), .difference(&other), and .symmetric_difference(&other), but:

  • On BTreeSet<T>, the iterator returned by .union(&other) or .intersection(&other) yields its elements in sorted ascending order, merging the two sorted trees in a single linear pass.
  • On HashSet<T>, .intersection(&other) iterates over the smaller set and probes the larger set in $O(1)$ per element, which is significantly faster when one set is tiny (e.g., 5 elements) and the other set is huge (e.g., 1,000,000 elements).