Rust HashSet and BTreeMap
last modified November 13, 2026
In this article we work with sets and ordered maps in Rust.
The std::collections module has two kinds of sets and maps.
The hashed collections, HashSet and
HashMap, find elements in constant time on average but keep
them in no particular order. The ordered collections,
BTreeSet and BTreeMap, are B-trees: lookups take
logarithmic time, but the elements are always sorted, which enables range
queries and gives reproducible output.
| Collection | Element requirement | Order | Lookup |
|---|---|---|---|
HashSet<T>, HashMap<K, V> | Eq + Hash | arbitrary | O(1) on average |
BTreeSet<T>, BTreeMap<K, V> | Ord | sorted | O(log n) |
A set stores unique values; a map stores values under unique keys.
HashMap has its own article, Rust
HashMap. The examples were tested with Rust 1.97 and the 2024 edition.
They are run as Cargo projects with cargo run -q.
HashSet basics
The first example inserts, looks up, and removes values in a
HashSet.
use std::collections::HashSet;
fn main() {
let mut langs = HashSet::new();
println!("{}", langs.insert("Rust"));
println!("{}", langs.insert("Go"));
println!("{}", langs.insert("Rust"));
langs.insert("Zig");
println!("size: {}", langs.len());
println!("contains Go: {}", langs.contains("Go"));
println!("contains C: {}", langs.contains("C"));
println!("removed Go: {}", langs.remove("Go"));
println!("removed Go: {}", langs.remove("Go"));
let mut sorted: Vec<_> = langs.iter().collect();
sorted.sort();
println!("{sorted:?}");
}
The element type, &str, is inferred from the first
insert.
println!("{}", langs.insert("Rust"));
println!("{}", langs.insert("Go"));
println!("{}", langs.insert("Rust"));
The insert method returns true if the value was
added and false if the set already contained it. The set
stays unchanged in the second case.
println!("removed Go: {}", langs.remove("Go"));
Similarly, remove tells us whether the value was present.
let mut sorted: Vec<_> = langs.iter().collect(); sorted.sort();
To print the elements in a predictable order, we collect them into a vector and sort it.
$ cargo run -q true true false size: 3 contains Go: true contains C: false removed Go: true removed Go: false ["Rust", "Zig"]
Iteration order
A HashSet does not remember the insertion order and the order
of iteration is not stable.
use std::collections::HashSet;
fn main() {
let colors = HashSet::from(["red", "green", "blue", "yellow", "black"]);
for c in &colors {
print!("{c} ");
}
println!();
}
We iterate over five colors.
for c in &colors {
print!("{c} ");
}
The standard hasher is seeded randomly for each program run to protect against denial-of-service attacks with crafted keys. As a result, the order changes between runs. Code must never depend on it.
$ cargo run -q red green yellow black blue $ cargo run -q red green blue yellow black $ cargo run -q yellow red blue black green
Removing duplicates
Sets are the usual tool for removing and detecting duplicate values.
use std::collections::HashSet;
fn main() {
let words = vec!["sky", "cup", "sky", "war", "cup", "ten", "sky"];
let unique: HashSet<_> = words.iter().copied().collect();
println!("{} unique of {}", unique.len(), words.len());
let mut seen = HashSet::new();
let mut ordered = words.clone();
ordered.retain(|w| seen.insert(*w));
println!("{ordered:?}");
let dups: HashSet<_> = {
let mut seen = HashSet::new();
words.iter().filter(|w| !seen.insert(**w)).copied().collect()
};
let mut dups: Vec<_> = dups.into_iter().collect();
dups.sort();
println!("duplicates: {dups:?}");
}
Collecting into a set keeps one copy of each value.
let unique: HashSet<_> = words.iter().copied().collect();
The result has no duplicates, but it has lost the original order.
let mut seen = HashSet::new(); let mut ordered = words.clone(); ordered.retain(|w| seen.insert(*w));
To keep the order of first occurrences, we filter the vector with
retain. The closure keeps a word only when
insert returns true, that is, the first time the
word is seen.
words.iter().filter(|w| !seen.insert(**w)).copied().collect()
The opposite condition selects every repeated occurrence. Collecting them into another set lists each duplicate once.
$ cargo run -q 4 unique of 7 ["sky", "cup", "war", "ten"] duplicates: ["cup", "sky"]
Set operations
Sets support the operations known from mathematics: union, intersection, difference, and symmetric difference.
use std::collections::HashSet;
fn sorted(set: &HashSet<i32>) -> Vec<i32> {
let mut v: Vec<_> = set.iter().copied().collect();
v.sort();
v
}
fn main() {
let a = HashSet::from([1, 2, 3, 4, 5]);
let b = HashSet::from([4, 5, 6, 7]);
let union: HashSet<i32> = a.union(&b).copied().collect();
let inter: HashSet<i32> = a.intersection(&b).copied().collect();
let diff: HashSet<i32> = a.difference(&b).copied().collect();
let sym: HashSet<i32> = a.symmetric_difference(&b).copied().collect();
println!("union: {:?}", sorted(&union));
println!("intersect: {:?}", sorted(&inter));
println!("a - b: {:?}", sorted(&diff));
println!("sym diff: {:?}", sorted(&sym));
println!("a | b: {:?}", sorted(&(&a | &b)));
println!("a & b: {:?}", sorted(&(&a & &b)));
println!("b - a: {:?}", sorted(&(&b - &a)));
println!("a ^ b: {:?}", sorted(&(&a ^ &b)));
println!("common count: {}", a.intersection(&b).count());
}
The methods return lazy iterators over references to the elements.
let union: HashSet<i32> = a.union(&b).copied().collect(); let inter: HashSet<i32> = a.intersection(&b).copied().collect();
We copy the integers and collect them into new sets. The
sorted helper turns a set into a sorted vector for
printing.
println!("a | b: {:?}", sorted(&(&a | &b)));
println!("a ^ b: {:?}", sorted(&(&a ^ &b)));
The operators |, &, -, and
^ are implemented for references to sets. They build a new
set directly and require the element type to be Clone.
println!("common count: {}", a.intersection(&b).count());
When we only need a count or a test, the iterator form avoids building a set at all.
$ cargo run -q union: [1, 2, 3, 4, 5, 6, 7] intersect: [4, 5] a - b: [1, 2, 3] sym diff: [1, 2, 3, 6, 7] a | b: [1, 2, 3, 4, 5, 6, 7] a & b: [4, 5] b - a: [6, 7] a ^ b: [1, 2, 3, 6, 7] common count: 2
Subsets and disjoint sets
The is_subset, is_superset, and
is_disjoint methods compare whole sets.
use std::collections::HashSet;
fn main() {
let required = HashSet::from(["read", "write"]);
let users = [
("anna", HashSet::from(["read", "write", "admin"])),
("boris", HashSet::from(["read"])),
("cyril", HashSet::from(["guest"])),
];
for (name, perms) in &users {
println!(
"{name:<6} has all required: {:<5} only required: {:<5} none: {}",
required.is_subset(perms),
perms.is_subset(&required),
perms.is_disjoint(&required)
);
}
let mut missing: Vec<_> = required.difference(&users[1].1).collect();
missing.sort();
println!("boris is missing {missing:?}");
}
We check user permissions against a required set.
required.is_subset(perms), perms.is_subset(&required), perms.is_disjoint(&required)
A user has all required permissions when the required set is a subset of the user's set. Two sets are disjoint when they have no element in common.
let mut missing: Vec<_> = required.difference(&users[1].1).collect();
The difference tells us which permissions are missing.
$ cargo run -q anna has all required: true only required: false none: false boris has all required: false only required: true none: false cyril has all required: false only required: false none: true boris is missing ["write"]
Custom types in a set
Our own types can be stored in a HashSet when they implement
Eq and Hash.
use std::collections::HashSet;
#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
struct Pos {
x: i32,
y: i32,
}
fn main() {
let moves = "RRUULDDDLR";
let mut pos = Pos { x: 0, y: 0 };
let mut visited = HashSet::from([pos]);
for m in moves.chars() {
match m {
'R' => pos.x += 1,
'L' => pos.x -= 1,
'U' => pos.y += 1,
'D' => pos.y -= 1,
_ => unreachable!(),
}
if !visited.insert(pos) {
println!("revisited {pos:?}");
}
}
println!("{} moves, {} distinct positions", moves.len(), visited.len());
}
We follow a path of moves on a grid and record the visited positions.
#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
struct Pos {
The derived implementations compare and hash all fields. Values that are equal must have equal hashes; deriving both traits guarantees this.
if !visited.insert(pos) {
println!("revisited {pos:?}");
}
A failed insert means the position was visited before. The
path has 11 positions including the start; two are repeated.
$ cargo run -q
revisited Pos { x: 1, y: 0 }
revisited Pos { x: 1, y: -1 }
10 moves, 9 distinct positions
BTreeSet
A BTreeSet keeps its elements sorted. It can return the
smallest and largest elements and iterate over a range.
use std::collections::BTreeSet;
fn main() {
let mut scores: BTreeSet<u32> = [72, 95, 41, 88, 95, 60, 77].into_iter().collect();
println!("{scores:?}");
println!("lowest {:?}, highest {:?}", scores.first(), scores.last());
let passing: Vec<_> = scores.range(60..).collect();
println!("60 and above: {passing:?}");
let below: Vec<_> = scores.range(..75).rev().take(2).collect();
println!("two below 75: {below:?}");
while let Some(top) = scores.pop_last() {
if top < 80 {
scores.insert(top);
break;
}
println!("award for {top}");
}
println!("left: {scores:?}");
}
We store exam scores; the duplicate 95 is kept only once.
println!("lowest {:?}, highest {:?}", scores.first(), scores.last());
The first and last methods return the minimum
and maximum in O(log n) time. They return None for an empty
set.
let passing: Vec<_> = scores.range(60..).collect(); let below: Vec<_> = scores.range(..75).rev().take(2).collect();
The range method accepts any range expression. The iterator
is double-ended, so rev walks down from the upper bound: here
it finds the two highest scores below 75.
while let Some(top) = scores.pop_last() {
The pop_last method removes and returns the largest element.
We hand out awards until we reach a score below 80, which we put back.
$ cargo run -q
{41, 60, 72, 77, 88, 95}
lowest Some(41), highest Some(95)
60 and above: [60, 72, 77, 88, 95]
two below 75: [72, 60]
award for 95
award for 88
left: {41, 60, 72, 77}
BTreeMap basics
A BTreeMap has the same core API as HashMap, but
iterates over its entries sorted by key.
use std::collections::BTreeMap;
fn main() {
let mut capitals = BTreeMap::new();
capitals.insert("Slovakia", "Bratislava");
capitals.insert("Austria", "Vienna");
capitals.insert("Hungary", "Budapest");
capitals.insert("Czechia", "Prague");
for (country, city) in &capitals {
println!("{country:<10} {city}");
}
println!("{:?}", capitals.get("Austria"));
println!("{:?}", capitals.get("Poland"));
let old = capitals.insert("Czechia", "Praha");
println!("replaced {old:?}");
println!("{capitals:?}");
}
The countries are inserted in random order and printed alphabetically.
println!("{:?}", capitals.get("Austria"));
The get method returns an Option with a
reference to the value.
let old = capitals.insert("Czechia", "Praha");
Inserting under an existing key replaces the value and returns the old one. The debug output of the whole map is sorted too, so it is the same in every run.
$ cargo run -q
Austria Vienna
Czechia Prague
Hungary Budapest
Slovakia Bratislava
Some("Vienna")
None
replaced Some("Prague")
{"Austria": "Vienna", "Czechia": "Praha", "Hungary": "Budapest", "Slovakia": "Bratislava"}
Counting and grouping
The entry API works with BTreeMap just as with
HashMap. The result comes out sorted without an extra step.
use std::collections::BTreeMap;
fn main() {
let text = "the sky is blue the sea is blue and the sun is bright";
let mut freq: BTreeMap<&str, u32> = BTreeMap::new();
for word in text.split_whitespace() {
*freq.entry(word).or_insert(0) += 1;
}
for (word, n) in &freq {
println!("{word:<7} {n}");
}
let mut by_len: BTreeMap<usize, Vec<&str>> = BTreeMap::new();
for word in freq.keys() {
by_len.entry(word.len()).or_default().push(word);
}
println!("{by_len:?}");
}
We count words and then group them by length.
*freq.entry(word).or_insert(0) += 1;
The entry method finds the slot for the key;
or_insert fills it with zero if it is empty and returns a
mutable reference to the count.
by_len.entry(word.len()).or_default().push(word);
The or_default method creates an empty vector for a new
length. Because we walk the keys of freq in order, the words
in each group are sorted as well.
$ cargo run -q
and 1
blue 2
bright 1
is 3
sea 1
sky 1
sun 1
the 3
{2: ["is"], 3: ["and", "sea", "sky", "sun", "the"], 4: ["blue"], 6: ["bright"]}
Range queries
The main advantage of an ordered map is efficient access to all keys within a range.
use std::collections::BTreeMap;
fn main() {
let readings = BTreeMap::from([
("2026-11-01", 8.5),
("2026-11-04", 6.0),
("2026-11-09", 3.5),
("2026-11-12", 4.0),
("2026-12-02", -1.5),
("2026-10-28", 11.0),
]);
for (day, t) in readings.range("2026-11-01".."2026-11-10") {
println!("{day}: {t:5.1} °C");
}
let nov: Vec<f64> = readings.range("2026-11".."2026-12").map(|(_, t)| *t).collect();
let avg = nov.iter().sum::<f64>() / nov.len() as f64;
println!("November: {} readings, average {avg:.2} °C", nov.len());
let latest_before = readings.range(.."2026-11-10").next_back();
println!("last reading before Nov 10: {latest_before:?}");
println!("first: {:?}", readings.first_key_value());
println!("last: {:?}", readings.last_key_value());
}
Temperature readings are stored under ISO dates. Strings in the
YYYY-MM-DD format sort chronologically.
for (day, t) in readings.range("2026-11-01".."2026-11-10") {
The range method finds the start in O(log n) time and then
walks the entries in order. A HashMap would have to examine
every entry.
readings.range("2026-11".."2026-12")
The bounds do not have to be existing keys. Every November date sorts
after "2026-11" and before "2026-12".
let latest_before = readings.range(.."2026-11-10").next_back();
Taking the last element of a range answers questions like "what was the most recent value before this date?".
$ cargo run -q
2026-11-01: 8.5 °C
2026-11-04: 6.0 °C
2026-11-09: 3.5 °C
November: 4 readings, average 5.50 °C
last reading before Nov 10: Some(("2026-11-09", 3.5))
first: Some(("2026-10-28", 11.0))
last: Some(("2026-12-02", -1.5))
Prefix search and bounds
Keys that share a prefix are stored next to each other, which makes prefix search cheap.
use std::collections::BTreeMap;
use std::ops::Bound::{Excluded, Included, Unbounded};
fn main() {
let words: BTreeMap<&str, u32> = [
("car", 12), ("card", 3), ("care", 7), ("cart", 2), ("cat", 20),
("dog", 15), ("carbon", 1), ("ca", 4),
]
.into_iter()
.collect();
let prefix = "car";
let matches: Vec<_> = words
.range(prefix..)
.take_while(|(w, _)| w.starts_with(prefix))
.collect();
println!("{matches:?}");
let after: Vec<_> = words.range::<str, _>((Excluded("car"), Included("cart"))).collect();
println!("{after:?}");
let all: Vec<_> = words.range::<str, _>((Unbounded, Excluded("car"))).map(|(w, _)| w).collect();
println!("{all:?}");
}
We look up all words that start with car.
words
.range(prefix..)
.take_while(|(w, _)| w.starts_with(prefix))
We start at the prefix and stop at the first key without it. The words
ca and cat are outside this run of keys.
words.range::<str, _>((Excluded("car"), Included("cart")))
For bounds that a range expression cannot express, such as an excluded
start, we pass a tuple of Bound values. With string keys, the
::<str, _> turbofish tells the compiler to compare by
str.
$ cargo run -q
[("car", 12), ("carbon", 1), ("card", 3), ("care", 7), ("cart", 2)]
[("carbon", 1), ("card", 3), ("care", 7), ("cart", 2)]
["ca"]
Custom ordered keys
Any type that implements Ord can be a key. The ordering of
the key type determines the order of the map.
use std::cmp::Reverse;
use std::collections::BTreeMap;
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Version {
major: u32,
minor: u32,
patch: u32,
}
impl Version {
fn new(major: u32, minor: u32, patch: u32) -> Self {
Version { major, minor, patch }
}
}
fn main() {
let mut releases = BTreeMap::new();
releases.insert(Version::new(1, 10, 0), "async closures");
releases.insert(Version::new(1, 9, 2), "security fix");
releases.insert(Version::new(2, 0, 0), "new edition");
releases.insert(Version::new(1, 9, 10), "bug fixes");
for (v, note) in &releases {
println!("{}.{}.{} {note}", v.major, v.minor, v.patch);
}
let mut by_score = BTreeMap::new();
for (name, score) in [("anna", 82), ("boris", 95), ("cyril", 70)] {
by_score.insert(Reverse(score), name);
}
let ranking: Vec<_> = by_score.iter().map(|(Reverse(s), n)| format!("{n} {s}")).collect();
println!("{ranking:?}");
}
Version numbers must be compared numerically, part by part.
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Version {
major: u32,
minor: u32,
patch: u32,
}
The derived Ord compares fields from top to bottom, which is
exactly the version ordering: 1.9.10 comes after 1.9.2, unlike in a string
comparison.
by_score.insert(Reverse(score), name);
The std::cmp::Reverse wrapper inverts the ordering, so the map
iterates from the highest score down. Note that equal scores would
overwrite each other; to allow ties, the key would also need the name.
$ cargo run -q 1.9.2 security fix 1.9.10 bug fixes 1.10.0 async closures 2.0.0 new edition ["boris 95", "anna 82", "cyril 70"]
Ordered processing and splitting
A map with priorities as keys can serve as a simple priority queue.
use std::collections::BTreeMap;
fn main() {
let mut tasks: BTreeMap<u32, Vec<&str>> = BTreeMap::new();
for (prio, task) in [(2, "write tests"), (1, "fix crash"), (3, "update docs"), (1, "deploy")] {
tasks.entry(prio).or_default().push(task);
}
while let Some((prio, list)) = tasks.pop_first() {
for t in list {
println!("priority {prio}: {t}");
}
}
println!("empty: {}", tasks.is_empty());
let mut map: BTreeMap<u32, char> = (1..=8).zip('a'..).collect();
let upper = map.split_off(&5);
println!("{map:?}\n{upper:?}");
map.retain(|k, _| k % 2 == 0);
println!("{map:?}");
}
Tasks with the same priority are collected in a vector.
while let Some((prio, list)) = tasks.pop_first() {
The pop_first method removes the entry with the smallest key,
so priority 1 is processed first. Within one priority, the tasks keep
their insertion order.
let upper = map.split_off(&5);
The split_off method moves all entries with keys greater than
or equal to the given key into a new map.
map.retain(|k, _| k % 2 == 0);
The retain method keeps only the entries for which the
closure returns true.
$ cargo run -q
priority 1: fix crash
priority 1: deploy
priority 2: write tests
priority 3: update docs
empty: true
{1: 'a', 2: 'b', 3: 'c', 4: 'd'}
{5: 'e', 6: 'f', 7: 'g', 8: 'h'}
{2: 'b', 4: 'd'}
Hashed or ordered?
The last example compares the speed of the two map types on a million keys.
use std::collections::{BTreeMap, HashMap};
use std::time::Instant;
fn main() {
let n = 1_000_000u64;
let keys: Vec<u64> = (0..n).map(|i| i.wrapping_mul(0x9E37_79B9_7F4A_7C15)).collect();
let t = Instant::now();
let mut hm = HashMap::new();
for &k in &keys {
hm.insert(k, k);
}
let found = keys.iter().filter(|k| hm.contains_key(k)).count();
println!("HashMap: {found} found in {:?}", t.elapsed());
let t = Instant::now();
let mut bm = BTreeMap::new();
for &k in &keys {
bm.insert(k, k);
}
let found = keys.iter().filter(|k| bm.contains_key(k)).count();
println!("BTreeMap: {found} found in {:?}", t.elapsed());
let t = Instant::now();
let mut sorted: Vec<_> = hm.keys().copied().collect();
sorted.sort_unstable();
println!("HashMap keys sorted afterwards in {:?}", t.elapsed());
let t = Instant::now();
let in_order: Vec<_> = bm.keys().copied().collect();
println!("BTreeMap keys in order in {:?}, same: {}", t.elapsed(), in_order == sorted);
}
The keys are spread over the whole u64 range by multiplying
with a large odd constant.
let found = keys.iter().filter(|k| hm.contains_key(k)).count();
We measure inserting all keys and looking each one up.
let mut sorted: Vec<_> = hm.keys().copied().collect(); sorted.sort_unstable();
Getting the keys in order requires a separate sort for a
HashMap; a BTreeMap yields them sorted.
The program runs in release mode on an Intel Core i5-1135G7. The
HashMap is about two and a half times faster for inserts and
lookups. Use it by default, and choose the B-tree collections when you
need sorted output, range queries, the smallest or largest key, or
reproducible iteration. The timings vary between runs.
$ cargo run -q --release HashMap: 1000000 found in 126.95501ms BTreeMap: 1000000 found in 329.633827ms HashMap keys sorted afterwards in 20.604485ms BTreeMap keys in order in 17.395608ms, same: true
Source
std::collections module documentation
std::collections::HashSet documentation
std::collections::BTreeMap documentation
In this article we have worked with HashSet,
BTreeSet, and BTreeMap in Rust. See also
Rust HashMap, Rust
vectors, and Rust collect.
Author
List all Rust tutorials.