HashSets and BTreeMaps

A HashSet<T> stores a collection of unique values with very fast membership testing, while a BTreeMap<K, V> stores key-value pairs that stay sorted by key at all times. Both live in std::collections alongside HashMap and Vec, but each makes a different trade-off between speed and order. Understanding when to reach for which one — and how they actually organize data in memory — will save you from picking the wrong tool and from writing code that silently depends on an ordering guarantee that doesn’t exist.

Overview / How it works

A HashSet<T> is, under the hood, nothing more than a HashMap<T, ()> — a hash map where every value is paired with the unit type (), which takes up zero bytes. All the real work happens in the hashing. When you call set.insert(value), Rust runs value through a hash function to produce a number, then uses that number to pick a “bucket” in an internal array where the value is stored. Looking up a value later means hashing it again and jumping straight to that bucket, rather than scanning every element — this is why contains, insert, and remove run in average O(1) time regardless of how many elements are in the set. The trade-off is that there is no meaningful relationship between a value’s hash and its position, so iterating over a HashSet visits elements in an order that is unspecified and can change between runs of the same program. By default, Rust’s standard library uses SipHash, a hashing algorithm chosen to resist maliciously crafted inputs that could otherwise degrade performance — a deliberate security trade-off, not an oversight.

A BTreeMap<K, V> takes the opposite approach. Instead of hashing keys into buckets, it stores entries in a balanced tree structure (a B-Tree) where every node keeps its keys sorted, and every subtree’s keys fall within a known range relative to its parent. This means insert, get, and remove run in O(log n) time — slower than a hash map’s O(1) — but in exchange, iterating over a BTreeMap always visits entries in ascending key order, deterministically, every single time. For this ordering to make sense, the key type K must implement the Ord trait (so any two keys can be compared), just as HashSet‘s element type must implement Eq and Hash.

The mental model to carry forward: reach for HashSet when you only care about whether something is present and want the fastest possible checks; reach for BTreeMap when you need key-value storage that stays sorted, such as building a leaderboard, a sorted index, or a report that must print in a predictable order without a separate sort step.

Syntax

// HashSet<T> — T must implement Eq + Hash
let mut set: HashSet<T> = HashSet::new();
set.insert(value);              // bool: true if newly inserted
set.contains(&value);           // bool
set.remove(&value);             // bool: true if it was present
set.len();                      // usize
for item in &set { ... }        // iterate (order unspecified)

// BTreeMap<K, V> — K must implement Ord
let mut map: BTreeMap<K, V> = BTreeMap::new();
map.insert(key, value);          // Option<V>: previous value, if any
map.get(&key);                   // Option<&V>
map.entry(key).or_insert(default); // &mut V
map.remove(&key);                 // Option<V>
for (k, v) in &map { ... }        // iterate in ascending key order

• HashSet::new() / BTreeMap::new() create empty, growable collections.
• insert on a set returns true if the value was new, false if it was already present (and nothing changes). On a map, it returns Option<V> — the value that used to be at that key, if any.
• contains/get take a reference to the key or value you’re searching for, not an owned value.
• entry(key).or_insert(default) is the idiomatic way to “get or create” an entry in a map without a separate lookup.

Examples

Example 1: Basic HashSet operations.

use std::collections::HashSet;

fn main() {
    let mut numbers: HashSet<i32> = HashSet::new();

    numbers.insert(4);
    numbers.insert(8);
    numbers.insert(15);
    numbers.insert(8); // duplicate, silently ignored

    println!("Set has {} unique numbers", numbers.len());
    println!("Contains 15? {}", numbers.contains(&15));
    println!("Contains 42? {}", numbers.contains(&42));

    numbers.remove(&4);
    println!("After removing 4, len = {}", numbers.len());
}

Output:

Set has 3 unique numbers
Contains 15? true
Contains 42? false
After removing 4, len = 2

Inserting 8 twice has no effect the second time — a HashSet silently discards duplicates, which is exactly what makes it useful for deduplication. contains and remove both take a reference (&15, &4) because they only need to read the value to compute its hash, not take ownership of it.

Example 2: Set operations — union, intersection, difference.

use std::collections::HashSet;

fn main() {
    let a: HashSet<i32> = [1, 2, 3, 4].into_iter().collect();
    let b: HashSet<i32> = [3, 4, 5, 6].into_iter().collect();

    let mut intersection: Vec<&i32> = a.intersection(&b).collect();
    intersection.sort();
    println!("Intersection: {:?}", intersection);

    let mut union: Vec<&i32> = a.union(&b).collect();
    union.sort();
    println!("Union: {:?}", union);

    let mut difference: Vec<&i32> = a.difference(&b).collect();
    difference.sort();
    println!("Difference (a - b): {:?}", difference);
}

Output:

Intersection: [3, 4]
Union: [1, 2, 3, 4, 5, 6]
Difference (a - b): [1, 2]

This is where HashSet earns its name: it implements real mathematical set operations. intersection, union, and difference all return iterators of references, which is why the result is collected into Vec<&i32>. Because their internal iteration order isn’t guaranteed, the results are explicitly sorted before printing — relying on a HashSet’s natural order would make this program’s output unpredictable.

Example 3: BTreeMap with the entry API for word counting.

use std::collections::BTreeMap;

fn main() {
    let text = "the quick brown fox jumps over the lazy dog the fox runs";
    let mut word_counts: BTreeMap<&str, i32> = BTreeMap::new();

    for word in text.split_whitespace() {
        let count = word_counts.entry(word).or_insert(0);
        *count += 1;
    }

    for (word, count) in &word_counts {
        println!("{}: {}", word, count);
    }
}

Output:

brown: 1
dog: 1
fox: 2
jumps: 1
lazy: 1
over: 1
quick: 1
runs: 1
the: 3

entry(word) looks up word in the map; if it’s missing, or_insert(0) inserts it with the value 0 and returns a mutable reference to it either way, so *count += 1 always increments the right slot. Because the map is a BTreeMap, printing it with a simple for loop naturally comes out in alphabetical order — no separate sort was needed.

How it works step by step

Tracing Example 3: each string slice produced by split_whitespace borrows from text, so word_counts is a BTreeMap<&str, i32> whose keys are borrowed views into the original string — this is valid because text lives for the entire function. On the first occurrence of "the", entry("the") walks the tree, finds no matching key, inserts one with value 0, and returns &mut i32 pointing at it; the following += 1 makes it 1. On the second occurrence, entry("the") walks the tree again, finds the existing key this time, and returns a mutable reference to the same slot — no new insertion happens, and the count climbs to 2, then 3. When the final for loop runs, the B-Tree is traversed left-to-right, which is defined to visit keys in ascending order — that traversal is what produces the alphabetically sorted output, not any sorting step you wrote.

For the HashSet examples, each insert hashes the value with SipHash, uses the hash to pick a bucket, and checks that bucket for an existing equal value (using Eq) before adding it — this is why the element type must implement both Hash and Eq, and why two values that are == to each other must also produce the same hash, or the set will behave incorrectly.

Common Mistakes

Mistake 1: Assuming HashSet iteration has a predictable order. This code compiles and runs fine, but its output order is not guaranteed and can differ between runs or even between compiler versions:

use std::collections::HashSet;

fn main() {
    let mut set = HashSet::new();
    set.insert("banana");
    set.insert("apple");
    set.insert("cherry");

    for item in &set {
        println!("{}", item);
    }
}

If your program’s correctness (or its test assertions) depend on this printing apple, banana, cherry in that order, it will eventually break. Fix it by sorting explicitly when order matters, or by using a BTreeSet if you always want sorted iteration.

Mistake 2: Mutating a HashSet while iterating over it. This is a genuine borrow-checker violation, not just a bad idea:

use std::collections::HashSet;

fn main() {
    let mut set: HashSet<i32> = [1, 2, 3].into_iter().collect();

    for value in &set {
        set.insert(value * 10); // ERROR
    }

    println!("{:?}", set);
}

The for value in &set loop holds an immutable borrow of set for its entire duration, so calling set.insert(...) — which needs a mutable borrow — inside that loop is rejected at compile time: error[E0502]: cannot borrow \`set\` as mutable because it is also borrowed as immutable. This rule exists because inserting could resize the set’s internal storage while you’re mid-iteration, which would invalidate the iterator. The fix is to collect the values you want to add into a separate Vec first, then insert them after the loop ends:

use std::collections::HashSet;

fn main() {
    let mut set: HashSet<i32> = [1, 2, 3].into_iter().collect();

    let doubled: Vec<i32> = set.iter().map(|v| v * 10).collect();
    for value in doubled {
        set.insert(value);
    }

    let mut result: Vec<i32> = set.into_iter().collect();
    result.sort();
    println!("{:?}", result);
}

Output:

[1, 2, 3, 10, 20, 30]

The immutable borrow from set.iter() ends as soon as doubled is fully collected, so the later set.insert(value) calls are free to take a mutable borrow.

Mistake 3: Using insert instead of entry().or_insert() for counting. This compiles and produces output, but the logic is wrong:

use std::collections::BTreeMap;

fn main() {
    let words = ["a", "b", "a", "c", "b", "a"];
    let mut counts: BTreeMap<&str, i32> = BTreeMap::new();

    for word in words {
        counts.insert(word, 1); // BUG: overwrites the count every time
    }

    for (word, count) in &counts {
        println!("{}: {}", word, count);
    }
}

Output:

a: 1
b: 1
c: 1

Every call to insert(word, 1) unconditionally overwrites whatever value was already stored for that key, so no matter how many times "a" appears, the final count is always 1 — the real counts should be a: 3, b: 2, c: 1. This is exactly the bug Example 3’s entry(word).or_insert(0) pattern avoids: it only inserts a fresh 0 the first time a key appears, and returns a mutable reference to increment on every subsequent occurrence.

Best Practices

• Use HashSet for fast membership tests and deduplication when you don’t care about order; use BTreeMap (or BTreeSet) when you need results in sorted order without a manual sort step.
• Never write code that depends on a HashSet‘s or HashMap‘s iteration order — sort explicitly if order matters for output or comparison.
• Prefer map.entry(key).or_insert(default) over a manual “check with get, then insert” pattern — it’s both more idiomatic and avoids a second lookup.
• Pass &value to contains, get, and remove — these methods only need to read the key/value to compare it, not take ownership.
• Reach for set.intersection(), union(), difference(), and symmetric_difference() instead of hand-rolling loops that check membership — they’re clearer and just as fast.
• Remember that any type used as a HashSet element or HashMap/BTreeMap key must implement the right traits (Eq + Hash for hashed collections, Ord for BTreeMap/BTreeSet) — for custom structs, this usually means deriving them with #[derive(PartialEq, Eq, Hash)] or #[derive(PartialEq, Eq, PartialOrd, Ord)].

Practice Exercises

• Write a program that reads a hard-coded list of email addresses (some duplicated) into a HashSet<String> and prints how many unique addresses remain.
• Given two HashSet<i32> values representing two students’ completed course IDs, print the courses both students share (intersection) and the courses only the first student has completed (difference), each sorted before printing.
• Build a BTreeMap<String, i32> that counts how many times each letter (as a lowercase string) appears in a sentence, using entry().or_insert(0), and print the results — they should come out already sorted alphabetically. Expected output for the input "bad cab" (ignoring spaces) should show a: 2, b: 2, c: 1, d: 1.

Summary

• HashSet<T> stores unique values with average O(1) insert/contains/remove, implemented internally as a HashMap<T, ()>; its iteration order is unspecified.
• BTreeMap<K, V> stores key-value pairs in a balanced tree with O(log n) operations, and always iterates in ascending key order.
• HashSet element types need Eq + Hash; BTreeMap key types need Ord.
• HashSet supports real set algebra: union, intersection, difference, and symmetric_difference.
• The entry(key).or_insert(default) pattern is the idiomatic way to get-or-create a map entry, and avoids the classic bug of overwriting a counter with plain insert.
• You cannot mutate a hashed or tree collection while an iterator over it is still alive — the borrow checker enforces this at compile time to prevent invalidated iterators.