HashSet<T> and BTreeSet<T>

A set is a collection that remembers which values you have seen, with the guarantee that each value appears at most once. If you insert the same value twice, the set ignores the second insertion. There is no "value" attached to each entry—only the key matters.

Rust offers two set types: HashSet<T> and BTreeSet<T>. They serve the same fundamental purpose but differ in how they organise elements internally, what they require from the type T, and the performance characteristics of their operations.

How the Two Set Types Differ

The fundamental difference lies in the contract used to determine uniqueness and order.

• HashSet<T> requires T: Eq + Hash. It places elements into buckets based on their hash and uses equality for collision resolution. Iteration order is arbitrary and may change between runs or even after insertions. Average-case lookup, insertion, and removal are O(1).
• BTreeSet<T> requires T: Ord. It stores elements in a balanced tree (a B-tree) that keeps them sorted by the Ord implementation. Iteration always visits elements in ascending order. All fundamental operations are O(log n).

This trade-off means the choice between them is rarely about "which is better" and more about what your data needs to support.

Core Operations

The API surface of both sets is largely identical. The following examples show the common operations using both types side by side. Choose the tab that matches the set you intend to use.

use std::collections::HashSet;
fn main() {
    // Creating an empty set
    let mut numbers = HashSet::new();
    // Inserting elements – returns true if the value was new
    assert!(numbers.insert(42));
    assert!(!numbers.insert(42)); // duplicate, ignored
    // Checking membership
    if numbers.contains(&42) {
        println!("42 is in the set");
    }
    // Removing an element – returns true if it was present
    let was_present = numbers.remove(&42);
    assert!(was_present);
    // Pre-allocating capacity when you know the size ahead of time
    let mut pre_sized: HashSet<i32> = HashSet::with_capacity(1_000);
    // Constructing from an array
    let colors = HashSet::from(["red", "green", "blue"]);
}

The insert method returns a bool that tells you whether the value was actually new to the set. This is often useful when you need to track first-seen occurrences without separate lookups.

Set Iteration

Iterating over a set follows the same borrow rules as any collection, but there is an important restriction: neither HashSet nor BTreeSet provides an iter_mut() method. The reason is safety: mutating an element in place could change its hash or ordering, breaking the set’s internal invariants. You can only obtain immutable references (iter()) or take ownership of elements (into_iter()).

Immutable iteration

Both sets provide an iter() method that yields &T. The order, however, is where the two differ.

use std::collections::HashSet;
let numbers: HashSet<_> = [3, 1, 4, 1, 5].into_iter().collect();
// Output may appear in any order, for example: 5, 3, 1, 4
for n in numbers.iter() {
    println!("{}", n);
}

With a BTreeSet, the same code will always print the numbers in ascending order: 1, 3, 4, 5.

Consuming iteration

When you are done with the set and want to move the values out, use into_iter(). After this, the set is consumed and can no longer be used.

use std::collections::BTreeSet;
let set: BTreeSet<_> = ["gamma", "alpha", "beta"].into_iter().collect();
let collected: Vec<_> = set.into_iter().collect();
assert_eq!(collected, vec!["alpha", "beta", "gamma"]);

When Equal Values Are Different

The idea that two values are "equal" depends on which trait the set uses. HashSet decides equality through the Eq trait and hashing through Hash. BTreeSet decides uniqueness through Ord, specifically when cmp returns Ordering::Equal.

For custom types, you must ensure these traits are consistent. The standard derive macros (#[derive(Eq, PartialEq, Hash, Ord, PartialOrd)]) guarantee this as long as all fields participate in the derivation uniformly. If you implement them manually, the following rule must hold for HashSet:

k1 == k2 → hash(k1) == hash(k2)

And for BTreeSet, the Ord implementation must form a total order consistent with Eq: a == b must imply a.cmp(&b) == Ordering::Equal.

The following example derives all required traits consistently. This is the safe, recommended path for most types.

use std::collections::{HashSet, BTreeSet};
#[derive(Debug, Hash, Eq, PartialEq, Ord, PartialOrd)]
struct User {
    id: u64,
    name: String,
}
let mut hash_users = HashSet::new();
hash_users.insert(User { id: 1, name: "Alice".into() });
hash_users.insert(User { id: 1, name: "Alice".into() }); // ignored
let mut tree_users = BTreeSet::new();
tree_users.insert(User { id: 1, name: "Alice".into() });
tree_users.insert(User { id: 1, name: "Alice".into() }); // ignored

Because Eq and Ord are derived on all fields, a User is considered duplicate only if both fields match. If you wanted uniqueness based solely on id, you'd need to write manual trait implementations that compare and hash only the id field—and you'd have to do so carefully to keep Eq and Ord aligned.

Whole-Set Operations

Both HashSet and BTreeSet provide the standard mathematical set operations. Each operation returns a lazy iterator that borrows the original sets; you typically call .cloned() or .copied() and then .collect() to obtain a new owned set.

use std::collections::HashSet;
let a: HashSet<_> = [1, 2, 3, 4, 5].into_iter().collect();
let b: HashSet<_> = [3, 4, 5, 6, 7].into_iter().collect();
// Union: elements present in either set
let union: HashSet<_> = a.union(&b).copied().collect();
// {1, 2, 3, 4, 5, 6, 7} (order arbitrary)
// Intersection: elements present in both sets
let intersection: HashSet<_> = a.intersection(&b).copied().collect();
// {3, 4, 5}
// Difference: elements in `a` but not in `b`
let difference: HashSet<_> = a.difference(&b).copied().collect();
// {1, 2}
// Symmetric difference: elements in one but not both
let sym_diff: HashSet<_> = a.symmetric_difference(&b).copied().collect();
// {1, 2, 6, 7}

These methods exist identically on BTreeSet as well. With BTreeSet, the resulting iterators will produce values in sorted order, and the collected set will also be sorted.

The library also provides predicate-based checks that avoid building new sets:

assert!(a.is_disjoint(&b) == false);                // no common elements?
assert!(a.is_subset(&b) == false);                  // is a ⊆ b ?
assert!(a.is_superset(&b) == false);                // is a ⊇ b ?

Performance Considerations

The O(1) vs O(log n) trade-off is only part of the story. Here are a few practical implications:

• Iteration speed: Iterating a HashSet visits elements in essentially random memory order, which can be slower than iterating a BTreeSet due to poor cache locality when the set is large. A BTreeSet iterates in-order, but pointer chasing between tree nodes still incurs overhead. For small sets, HashSet often iterates faster because the elements sit in a contiguous buffer.
• Memory overhead: HashSet allocates a hash table with empty slots to keep the load factor low, which can consume more memory than the theoretical size of the elements. BTreeSet allocates nodes individually, with each node storing a few elements plus child pointers. The per-element overhead tends to be lower, but the allocation pattern is more fragmented.
• Worst-case hashing: If an adversary can control the keys inserted into a HashSet and the hasher is predictable, they can craft collisions that degrade performance to O(n). Rust's default hasher uses a random seed per instance to make this impractical. BTreeSet does not have this vulnerability.

Common Mistakes and Pitfalls

Summary

HashSet<T> and BTreeSet<T> are two views of the same abstract set concept, differentiated by the contract they impose on T and the performance profile they offer. Pick HashSet when you want fast average-case lookups and don't care about element order. Pick BTreeSet when you need sorted iteration, range queries, or consistent logarithmic behaviour regardless of key distribution. The operations—insertion, membership, removal, and whole-set algebra—are deliberately uniform across both types, so switching between them later usually requires only a type change and recompilation.