Collections Deep Dive

Vec::push and HashMap::insert are usually the first methods anyone learns, and for a lot of code that's all you'll ever need. This tutorial covers the parts that come up once a collection is on a hot path or holding real data: avoiding reallocations, picking between HashMap and BTreeMap, the Entry API for lookup-then-modify, and when VecDeque or a plain Vec beats a HashSet.

Vec<T>: Capacity, Removal, and Filtering

A Vec separates length (how many elements it holds) from capacity (how many it can hold before reallocating). Pushing past capacity reallocates and copies everything, if you know roughly how many elements you'll end up with, reserve it upfront:

let mut ids = Vec::with_capacity(1000);
for i in 0..1000 {
    ids.push(i);  // no reallocation across this entire loop
}

Removing elements has two costs, depending on whether order matters. .remove(i) shifts every following element left, O(n). .swap_remove(i) moves the last element into the removed slot instead, O(1), but it doesn't preserve order.

let mut v = vec![1, 2, 3, 4, 5];
v.swap_remove(1);          // [1, 5, 3, 4] — O(1), order not preserved
v.remove(1);                // [1, 4, 3] — O(n), order preserved

Filtering in place vs rebuilding. .retain() keeps elements matching a predicate and drops the rest, in place, without allocating a new Vec:

let mut scores = vec![10, -3, 42, -1, 7];
scores.retain(|&x| x >= 0);  // [10, 42, 7]

This is cheaper than .into_iter().filter(...).collect() when you already own the Vec and just want to shrink it, no second allocation, no need to consume and rebuild.

HashMap vs BTreeMap: Speed vs Order

Both map keys to values. The difference is what you get back when you don't ask for a specific key.

HashMap<K, V> gives average O(1) lookup, insert, and removal, at the cost of an unspecified, effectively random iteration order. Two runs of the same program can (and by design, will) iterate a HashMap in different orders, Rust deliberately randomizes the hash seed per-process to prevent hash-flooding denial-of-service attacks.

use std::collections::HashMap;

let mut counts: HashMap<&str, u32> = HashMap::new();
counts.insert("rust", 5);
counts.insert("go", 3);
// iteration order of `counts` is not guaranteed to match insertion order

BTreeMap<K, V> keeps keys sorted, at O(log n) per operation instead of O(1). You reach for it specifically when you need ordered iteration or range queries, not as a default replacement for HashMap:

use std::collections::BTreeMap;

let mut scores: BTreeMap<u32, &str> = BTreeMap::new();
scores.insert(85, "Alice");
scores.insert(92, "Bob");
scores.insert(78, "Carol");

for (score, name) in &scores {
    println!("{score}: {name}");  // iterates in ascending key order
}

// range queries: every entry with a score of 80 or above
for (score, name) in scores.range(80..) {
    println!("{score}: {name}");
}

Default to HashMap. Reach for BTreeMap only when you specifically need sorted iteration or a range query, the kind of thing .range() gives you for free and a HashMap simply can't do.

The Entry API: One Lookup Instead of Two

The naive way to "increment a counter if present, otherwise insert it at 1" looks up the key twice:

// works, but checks the key twice
if map.contains_key(&word) {
    *map.get_mut(&word).unwrap() += 1;
} else {
    map.insert(word.clone(), 1);
}

.entry() does it in a single lookup, returning a handle you can act on regardless of whether the key was already there:

use std::collections::HashMap;

let text = "the quick brown fox jumps over the lazy fox";
let mut counts: HashMap<&str, u32> = HashMap::new();

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

println!("{:?}", counts.get("fox"));  // Some(2)

.or_insert(0) returns a &mut V, either to the existing value or to a freshly inserted 0, which the += 1 then mutates directly. .or_insert_with(...) takes a closure instead, useful when the default is expensive to construct and you don't want to build it on every call:

let group = groups.entry(key).or_insert_with(Vec::new);
group.push(item);

.and_modify() chains a mutation onto an existing entry without affecting the insert-if-missing behavior:

counts.entry(word)
    .and_modify(|c| *c += 1)
    .or_insert(1);

HashSet/BTreeSet: Membership and Deduplication

A set is a map with no values, just keys, used for "have I seen this?" checks and removing duplicates.

use std::collections::HashSet;

let mut seen = HashSet::new();
let mut unique = Vec::new();

for item in vec![3, 1, 4, 1, 5, 9, 2, 6, 5] {
    if seen.insert(item) {  // insert returns true if it was newly added
        unique.push(item);
    }
}

println!("{unique:?}");  // [3, 1, 4, 5, 9, 2, 6]

.insert() returning bool (newly inserted or not) is the detail that makes this pattern a single pass instead of a separate .contains() check followed by an .insert().

For small collections, a sorted Vec can beat a HashSet. Hashing has a fixed per-lookup cost; for a few dozen elements, a linear scan over a contiguous, cache-friendly Vec is often faster in practice than computing a hash and following a pointer into a hash table. HashSet wins once the collection is large enough that O(n) scanning actually costs more than the hashing overhead, there's no fixed threshold, profile if it matters.

VecDeque<T>: Fast at Both Ends

A Vec is fast to push and pop from the back, but popping from the front is O(n), every remaining element has to shift down. VecDeque (a ring buffer) makes both ends O(1):

use std::collections::VecDeque;

let mut queue: VecDeque<u32> = VecDeque::new();
queue.push_back(1);
queue.push_back(2);
queue.push_front(0);

while let Some(item) = queue.pop_front() {
    println!("{item}");  // 0, 1, 2
}

Reach for VecDeque for FIFO queues (breadth-first search, task queues) and sliding windows that drop from one end while adding to the other. If you only ever push and pop from the same end, a plain Vec is simpler and just as fast.

Choosing a Collection

Key Takeaways

• Vec::with_capacity avoids repeated reallocation when the final size is roughly known. .swap_remove() is O(1) but reorders; .remove() preserves order at O(n).
• .retain() filters a Vec in place without the extra allocation .filter().collect() would cost.
• HashMap is the default: average O(1), unordered, with a randomized iteration order by design. Reach for BTreeMap only when you need sorted iteration or .range() queries.
• .entry() turns a lookup-then-insert-or-update into a single lookup. .or_insert_with() defers building the default value; .and_modify() chains a mutation onto an existing entry.
• A HashSet's .insert() returns whether the value was new, making contains-then-insert a single call. For small collections, a sorted Vec can outperform a HashSet due to cache locality.
• VecDeque makes both push/pop ends O(1); use it for queues and sliding windows where a Vec would force an O(n) shift at the front.