Skip to content
rusthacks.dev
Rust

Rust Collections Compared Vec HashMap HashSet and BTreeMap

Choose between Vec, VecDeque, HashMap, HashSet, BTreeMap and BTreeSet by the operations you need, with complexity, ordering and memory notes.

8 min read
Summarize in AI
Flat illustration for the post “Rust Collections Compared Vec HashMap HashSet and BTreeMap”, composed around memory.

Choosing a collection is mostly a question of what you do with it: look things up by position, look them up by key, keep them in order, or add and remove at both ends. Rust's standard library has a handful of containers that answer those questions differently, and picking the wrong one costs far more than any micro-optimisation. This post runs a tour of the five you will use, measures the lookup and insert costs on 200,000 keys, and shows the errors that come with them. All programs ran on Rust 1.99, edition 2024, and the timing program was compiled with -O.

The five in one program

src/main.rsrust
use std::collections::{BTreeMap, HashMap, HashSet, VecDeque};

fn main() {
    // Vec: ordered, indexable, growable
    let mut v = vec![30, 10, 20];
    v.push(40);
    v.sort();
    println!("{v:?} first={} len={}", v[0], v.len());

    // HashMap: key -> value, O(1) average, no order
    let mut stock: HashMap<&str, u32> = HashMap::new();
    stock.insert("apples", 5);
    *stock.entry("apples").or_insert(0) += 3;
    *stock.entry("pears").or_insert(0) += 2;
    let mut keys: Vec<_> = stock.iter().collect();
    keys.sort();
    println!("{keys:?}");

    // HashSet: membership and de-duplication
    let seen: HashSet<i32> = [1, 2, 2, 3, 3, 3].into_iter().collect();
    println!("{} unique, contains 2: {}", seen.len(), seen.contains(&2));

    // BTreeMap: sorted by key, range queries
    let mut scores = BTreeMap::new();
    for (name, s) in [("zed", 40), ("amy", 90), ("bob", 70)] {
        scores.insert(name, s);
    }
    println!("{scores:?}");
    println!("{:?}", scores.range("b".."z").collect::<Vec<_>>());

    // VecDeque: fast at both ends
    let mut q: VecDeque<i32> = VecDeque::new();
    q.push_back(1);
    q.push_back(2);
    q.push_front(0);
    println!("{q:?} pop_front={:?}", q.pop_front());
}
Text
[10, 20, 30, 40] first=10 len=4
[("apples", 8), ("pears", 2)]
3 unique, contains 2: true
{"amy": 90, "bob": 70, "zed": 40}
[("bob", 70)]
[1, 2] pop_front=Some(0)

Vec<T> is a growable array. Elements sit next to each other in memory, you reach one by position, and appending is cheap. It is the default for a reason: almost everything else is a Vec underneath, and the CPU loves contiguous data.

HashMap<K, V> maps keys to values. The entry API is the idiom for counting and grouping: *stock.entry("apples").or_insert(0) += 3 inserts a zero if the key is missing and then adds. The program sorts the pairs before printing because the map has no order.

HashSet<T> is a map with no values, for membership tests and removing duplicates: six numbers became three unique ones.

BTreeMap<K, V> keeps its keys sorted. It prints in key order (amy, bob, zed) and supports range queries: range("b".."z") found bob without scanning the rest.

VecDeque<T> is a double-ended queue: pushing and popping at both ends is cheap, which a Vec cannot do at the front.

What the choice costs

The claim that a hash lookup beats a scan is easy to state and worth seeing with numbers. This program builds 200,000 entries in a Vec of pairs, a HashMap and a BTreeMap, then looks up 2,000 keys that are present, taking the best of five runs:

src/main.rsrust
use std::collections::{BTreeMap, HashMap};
use std::hint::black_box;
use std::time::Instant;

fn time<F: FnMut() -> u64>(label: &str, mut f: F) {
    let mut best = u128::MAX;
    let mut out = 0;
    for _ in 0..5 {
        let t = Instant::now();
        out = f();
        best = best.min(t.elapsed().as_micros());
    }
    println!("{label:<34} {:>8.2} ms  (checksum {out})", best as f64 / 1000.0);
}

fn main() {
    const N: u64 = 200_000;
    let keys: Vec<u64> = (0..N).map(|i| i.wrapping_mul(2_654_435_761) % 1_000_003).collect();

    let vec: Vec<(u64, u64)> = keys.iter().map(|&k| (k, k * 2)).collect();
    let hash: HashMap<u64, u64> = keys.iter().map(|&k| (k, k * 2)).collect();
    let btree: BTreeMap<u64, u64> = keys.iter().map(|&k| (k, k * 2)).collect();
    println!("{} distinct keys, {} lookups each\n", hash.len(), 2000);

    let probes: Vec<u64> = keys.iter().step_by(100).copied().collect(); // 2000 present keys

    time("Vec linear scan (find)", || {
        probes.iter().map(|p| vec.iter().find(|(k, _)| k == black_box(p)).unwrap().1).sum()
    });
    time("HashMap get", || probes.iter().map(|p| hash[black_box(p)]).sum());
    time("BTreeMap get", || probes.iter().map(|p| btree[black_box(p)]).sum());

    time("insert 200k into HashMap", || {
        let mut m = HashMap::new();
        for &k in &keys { m.insert(k, k); }
        m.len() as u64
    });
    time("insert 200k into BTreeMap", || {
        let mut m = BTreeMap::new();
        for &k in &keys { m.insert(k, k); }
        m.len() as u64
    });
    time("iterate HashMap (sum values)", || hash.values().sum());
    time("iterate BTreeMap (sum values)", || btree.values().sum());
}
Text
200000 distinct keys, 2000 lookups each

Vec linear scan (find)                83.20 ms  (checksum 1997105410)
HashMap get                            0.02 ms  (checksum 1997105410)
BTreeMap get                           0.16 ms  (checksum 1997105410)
insert 200k into HashMap               4.97 ms  (checksum 200000)
insert 200k into BTreeMap             18.16 ms  (checksum 200000)
iterate HashMap (sum values)           0.30 ms  (checksum 200001330688)
iterate BTreeMap (sum values)          0.18 ms  (checksum 200001330688)

Read the table in three parts.

Lookup. Scanning the Vec for 2,000 keys took 83.20 ms, about 41 microseconds per lookup, because each one walks, on average, half of 200,000 pairs. The HashMap did all 2,000 in 0.02 ms. The BTreeMap took 0.16 ms. Hashing is roughly 8 times faster than a tree at this size, and both are thousands of times faster than the scan. The checksum is identical on every line, which is how you know the three structures returned the same answers.

Building. Inserting 200,000 keys took 4.97 ms in the HashMap and 18.16 ms in the BTreeMap. A tree keeps everything sorted on every insert, and that work is the price of ordered access. If you build once and read many times, collect into a Vec, sort it and use binary_search; for lookups it matches a tree and it is cheaper to build.

Iteration. Summing all values took 0.30 ms in the hash map and 0.18 ms in the tree. Walking a BTreeMap visits its nodes in order and the nodes hold several keys each, so iteration is friendly to the cache; hash tables have empty slots to skip. This is the opposite of the lookup ranking, and it is a reminder that "faster" depends on the operation.

These are figures from one machine and one key distribution. Hash maps use SipHash by default, which resists attackers who craft colliding keys; for internal data you control, a faster hasher helps further, as shown in faster hashers for HashMap. Read benchmarking pitfalls before trusting any microbenchmark, including this one.

Ordering is not free, and sometimes it is absent

A HashMap makes no promise about iteration order, and the implementation randomises its hash seed per map. Run the same program three times:

src/main.rsrust
use std::collections::HashMap;

fn main() {
    let mut m = HashMap::new();
    for w in ["delta", "alpha", "charlie", "bravo"] {
        m.insert(w, w.len());
    }
    println!("{:?}", m);   // order is unspecified and changes between runs
}
Text
{"bravo": 5, "delta": 5, "alpha": 5, "charlie": 7}
{"alpha": 5, "delta": 5, "charlie": 7, "bravo": 5}
{"alpha": 5, "delta": 5, "bravo": 5, "charlie": 7}

The same four words came out in three different orders, so a test that compares the printed map, or code that assumes the first entry stays first, passes locally and flakes elsewhere. When you need the output in a stable order, sort the keys, collect into a Vec, or use a BTreeMap.

Keys must be hashable

A key type has to implement Eq and Hash for a HashMap, and Ord for a BTreeMap. Floating point numbers implement neither, because NaN != NaN:

src/main.rsrust
use std::collections::HashMap;

fn main() {
    let mut m: HashMap<f64, &str> = HashMap::new();
    m.insert(1.5, "one and a half");
    println!("{}", m.len());
}
Text
error[E0599]: the method `insert` exists for struct `HashMap<f64, &str>`, but its trait bounds were not satisfied
 --> src/main.rs:5:7
  |
5 |     m.insert(1.5, "one and a half");
  |       ^^^^^^
  |
  = note: the following trait bounds were not satisfied:
          `f64: Eq`
          `f64: Hash`

The message is E0599 rather than E0277 because the problem surfaces as a method that cannot be called: the bounds f64: Eq and f64: Hash are not satisfied. The usual solutions are to key by an integer (cents, or the bit pattern from to_bits), by a string, or to wrap the float in a type that defines equality the way you need, such as an OrderedFloat from a crate.

The borrow checker and vectors

The classic collection error is a reference held across a push:

src/main.rsrust
fn main() {
    let mut v = vec![1, 2, 3];
    let first = &v[0];
    v.push(4);
    println!("{first}");
}
Text
error[E0502]: cannot borrow `v` as mutable because it is also borrowed as immutable
 --> src/main.rs:4:5
  |
3 |     let first = &v[0];
  |                  - immutable borrow occurs here
4 |     v.push(4);
  |     ^^^^^^^^^ mutable borrow occurs here
5 |     println!("{first}");
  |                ----- immutable borrow later used here

first borrows an element of v. push may need to allocate a bigger buffer and move everything, which would leave first pointing at freed memory. Rust refuses the program rather than allow a dangling reference, which in C++ is undefined behaviour. The fixes are to finish using the reference before pushing, copy the value (let first = v[0];), or hold an index instead of a reference. Ownership covers the principle, and pre-sizing with Vec::with_capacity is a performance topic in reusing buffers and capacity.

A decision guide

You needUseWhy
A list in order, index by positionVec<T>contiguous, cheapest
Look up by key, order unimportantHashMap<K, V>about 0.02 ms for 2,000 lookups here
Count or group by keyHashMap with the entry APIone lookup per update
Unique items, membership testHashSet<T>a map without values
Keys in order, or rangesBTreeMap, BTreeSetsorted iteration, range
Queue, add at the frontVecDeque<T>O(1) at both ends
Few items (under about 20)still Vecscanning a tiny array beats hashing

The last row matters. For a handful of entries a linear scan has no overhead to amortise, and a Vec of pairs is smaller and faster than any map.

Habits

  • Reach for Vec first and measure before switching.
  • Never rely on HashMap order. Sort when you print or compare.
  • Choose BTreeMap for the ordering or range queries, not as a default "safe" map.
  • Use HashSet to deduplicate rather than contains on a Vec.
  • Let collect build the map from an iterator instead of inserting in a loop.

When none of these fit

For a priority queue use BinaryHeap. For an LRU cache, an ordered map with expiry or a concurrent map shared across threads, the standard library has no direct answer, and a crate such as indexmap (insertion order), dashmap or lru is the right tool. And if the data is large enough that it does not fit in memory, you want a database or a memory-mapped file, not a different std collection.

Share

Keep reading

Get new posts by email

We send one email when a new post is published. No spam.

Unsubscribe in one click. No spam, ever.