Rust HashSet & BTreeMap

A HashSet is a collection of unique values. Put the same value in twice and it is only stored once. Think of a guest list at a door: the bouncer only cares whether your name is on the list, not how many times it was written.

You already know Vec and HashMap. This page adds the other collections you’ll reach for most often: HashSet, the sorted BTreeMap and BTreeSet, and VecDeque for queues. At the end there’s a table to help you pick the right one.

Creating a HashSet

HashSet lives in std::collections, so you need a use line. The insert method returns a bool: true if the value was new, false if it was already there.

use std::collections::HashSet;

fn main() {
    let mut tags = HashSet::new();

    println!("{}", tags.insert("rust"));
    println!("{}", tags.insert("web"));
    println!("{}", tags.insert("rust")); // already there

    println!("{} unique tags", tags.len());
}

Output:

true
true
false
2 unique tags

▶ Try it Yourself

That bool is more useful than it looks. It answers “have I seen this before?” in the same step as adding it, so you don’t need a separate check.

Checking and removing values

contains tells you if a value is in the set. remove takes it out and, like insert, returns a bool telling you whether anything was actually removed.

use std::collections::HashSet;

fn main() {
    let mut online: HashSet<&str> = HashSet::from(["ana", "ben", "chen"]);

    println!("is ben online? {}", online.contains("ben"));

    println!("removed ben: {}", online.remove("ben"));
    println!("removed ben again: {}", online.remove("ben"));

    println!("is ben online? {}", online.contains("ben"));
    println!("{} people online", online.len());
}

Output:

is ben online? true
removed ben: true
removed ben again: false
is ben online? false
2 people online

▶ Try it Yourself

Why use a set instead of a Vec here? Checking contains on a Vec looks at every item, one by one. A HashSet jumps straight to the answer, no matter how big it gets. With a million users, that difference is huge.

Caution

A HashSet has no fixed order. If you print it with {:?} or loop over it, the order can change from one run to the next. When you need a stable order for printing, copy the values into a Vec and sort it, or use a BTreeSet (covered below).

Removing duplicates from a Vec

A very common job: you have a list with repeats and want each value once. There are two good ways, depending on whether you care about the original order.

use std::collections::HashSet;

fn main() {
    let visits = vec![3, 1, 3, 2, 1, 5, 2];

    // Way 1: collect into a set, then sort for a stable order
    let unique: HashSet<i32> = visits.iter().copied().collect();
    let mut sorted: Vec<i32> = unique.into_iter().collect();
    sorted.sort();
    println!("sorted unique: {:?}", sorted);

    // Way 2: keep the first time each value appears, in original order
    let mut seen = HashSet::new();
    let mut in_order = visits.clone();
    in_order.retain(|x| seen.insert(*x));
    println!("in order:      {:?}", in_order);
}

Output:

sorted unique: [1, 2, 3, 5]
in order:      [3, 1, 2, 5]

▶ Try it Yourself

Way 2 uses the bool from insert. retain keeps an item only when the closure returns true, and insert returns true only the first time it sees a value.

Set math: union, intersection, difference

Sets can be combined like the circles in a Venn diagram. Each method returns an iterator, so we collect the results into a Vec and sort them before printing to get the same output every time.

use std::collections::HashSet;

fn main() {
    let alice: HashSet<&str> = HashSet::from(["rust", "python", "go"]);
    let bob: HashSet<&str> = HashSet::from(["go", "java", "rust"]);

    let mut both: Vec<_> = alice.intersection(&bob).collect();
    both.sort();
    println!("both know:      {:?}", both);

    let mut either: Vec<_> = alice.union(&bob).collect();
    either.sort();
    println!("either knows:   {:?}", either);

    let mut only_alice: Vec<_> = alice.difference(&bob).collect();
    only_alice.sort();
    println!("only alice:     {:?}", only_alice);

    let mut only_one: Vec<_> = alice.symmetric_difference(&bob).collect();
    only_one.sort();
    println!("only one knows: {:?}", only_one);
}

Output:

both know:      ["go", "rust"]
either knows:   ["go", "java", "python", "rust"]
only alice:     ["python"]
only one knows: ["java", "python"]

▶ Try it Yourself

difference is one-way: alice.difference(&bob) is “what Alice knows that Bob doesn’t”. Swap them and you get Bob’s list instead. symmetric_difference is both sides at once: everything that only one of them knows.

BTreeMap and BTreeSet: always sorted

BTreeMap works just like HashMap, and BTreeSet works just like HashSet. The difference: they keep their keys sorted. When you loop over them, you get the keys in order, every time.

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

fn main() {
    let text = "the cat sat on the mat the end";

    let mut counts: BTreeMap<&str, u32> = BTreeMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    for (word, count) in &counts {
        println!("{word}: {count}");
    }

    let scores: BTreeSet<u32> = BTreeSet::from([72, 95, 58, 88]);
    println!("lowest: {:?}", scores.first());
    println!("highest: {:?}", scores.last());
    println!("all: {:?}", scores);
}

Output:

cat: 1
end: 1
mat: 1
on: 1
sat: 1
the: 3
lowest: Some(58)
highest: Some(95)
all: {58, 72, 88, 95}

▶ Try it Yourself

The entry API is the same one you met on the HashMap page. Because the map is a BTreeMap, the words come out in alphabetical order with no extra sorting step.

Which should you choose?

• Pick HashMap / HashSet by default. Lookups are usually faster.
• Pick BTreeMap / BTreeSet when you need the data in order: printing a sorted report, finding the smallest or largest key, or getting a range of keys.

VecDeque: a queue

A VecDeque (say “vec deck”) is a list you can add to and remove from at both ends quickly. That makes it the natural choice for a queue: first in, first out, like people waiting in line.

use std::collections::VecDeque;

fn main() {
    let mut line: VecDeque<&str> = VecDeque::new();
    line.push_back("ana");
    line.push_back("ben");
    line.push_back("chen");

    while let Some(person) = line.pop_front() {
        println!("serving {person}, {} still waiting", line.len());
    }
}

Output:

serving ana, 2 still waiting
serving ben, 1 still waiting
serving chen, 0 still waiting

▶ Try it Yourself

You could use Vec::remove(0) for this, but that shifts every other item over by one. pop_front on a VecDeque doesn’t, so it stays fast even with a long line.

Which collection should I use?

Collection	Use it when you need…	Example
Vec<T>	An ordered list, accessed by position	Lines of a file, a list of scores
HashMap<K, V>	Fast lookup of a value by key	Username → user profile
HashSet<T>	Unique values and fast “is it in here?” checks	Visited pages, banned words
BTreeMap<K, V>	Key → value, with keys kept sorted	A word count printed alphabetically
VecDeque<T>	Adding/removing at both ends	A queue of tasks or messages

When in doubt, start with a Vec. Switch when you notice you’re searching it over and over (use a set or map) or removing from the front a lot (use a VecDeque).

Common mistakes

Putting your own struct in a HashSet without the right derives. A HashSet needs to hash its values and compare them for equality. Your struct doesn’t do that automatically:

use std::collections::HashSet;

struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
}

error[E0277]: the trait bound `Point: Eq` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Eq` is not implemented for `Point`

error[E0277]: the trait bound `Point: Hash` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Hash` is not implemented for `Point`

The fix is one line above the struct: #[derive(PartialEq, Eq, Hash)]. For a BTreeSet you’d also need PartialOrd and Ord, so it knows how to sort. See Common Traits for what each of these means.

use std::collections::HashSet;

#[derive(PartialEq, Eq, Hash)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
    visited.insert(Point { x: 1, y: 0 });
    visited.insert(Point { x: 0, y: 0 }); // duplicate, ignored
    println!("visited {} squares", visited.len());
}

Output:

visited 2 squares

▶ Try it Yourself

Going further

Need a queue (first in, first out) or “always give me the biggest next”? VecDeque & BinaryHeap covers the two collections built for that.

Practice

1. The first repeat

Given the words ["red", "blue", "green", "blue", "red"], print the first word that shows up a second time. Hint: insert returns false when the value is already in the set, and break stops the loop.

Show solution

use std::collections::HashSet;

fn main() {
    let words = ["red", "blue", "green", "blue", "red"];
    let mut seen = HashSet::new();

    for word in words {
        if !seen.insert(word) {
            println!("First repeat: {word}");
            break;
        }
    }
}

Output:

First repeat: blue

▶ Try it Yourself

!seen.insert(word) reads as “inserting failed”, which means “I’ve seen this one before”. "blue" is the first word to repeat. "red" repeats too, but later.

2. Letters in order

Count how many times each letter appears in "mississippi", and print the counts in alphabetical order. Hint: use a BTreeMap with the same entry(...).or_insert(0) trick from the BTreeMap section, and loop over word.chars().

Show solution

use std::collections::BTreeMap;

fn main() {
    let word = "mississippi";
    let mut counts = BTreeMap::new();

    for letter in word.chars() {
        *counts.entry(letter).or_insert(0) += 1;
    }

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

Output:

i: 4
m: 1
p: 2
s: 4

▶ Try it Yourself

With a HashMap, these four lines could come out in any order. The BTreeMap keeps its keys sorted, so i, m, p, s print alphabetically every time.

Recap

• HashSet stores unique values. insert and remove return a bool telling you if anything changed.
• contains on a set is fast, even for huge sets. On a Vec it checks every item.
• union, intersection, difference, and symmetric_difference do set math. Sort the results before printing.
• BTreeMap and BTreeSet keep keys sorted; use them when order matters.
• VecDeque is the go-to queue: push_back to join, pop_front to leave.

Quick check

Quick check

1. What does set.insert(x) return if x is already in the set?

true An error false The old value

2. You want a word count printed in alphabetical order without sorting it yourself. Which map fits best?

HashMap BTreeMap Vec VecDeque

3. Why might printing a HashSet with {:?} give different output on different runs?

A HashSet has no fixed order {:?} is random Sets lose values over time It only happens in debug mode

4. Which collection is best for a first-in, first-out queue?

HashSet BTreeSet HashMap VecDeque

Score: 0 / 4

Read more

• std::collections overview — standard library docs: a longer guide to choosing a collection, with the speed of each operation.
• HashSet — Rust by Example: a runnable example of union, intersection and difference.
• HashSet — standard library docs: every set method, including is_subset and retain.
• BTreeMap — standard library docs: sorted maps, including range for getting a slice of keys.
• VecDeque — standard library docs: all the queue methods, like push_front, pop_back and front.