Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

Rust Collections: Vec, HashMap, BTreeMap, and the Entry API

Vec for sequences, HashMap for keyed lookup, BTreeMap for order. Where the Entry API removes a lookup, and why index removal is O(n).

~4 min readRust
#Rust#Collections#Data Structures
3D illustration of contiguous Vec buffers, hash-bucketed HashMap tables and ordered BTreeMap nodes side by side

Quick Summary

The standard library gives three workhorses. Vec<T> is a growable contiguous array: O(1) push and index, amortized doubling on growth, cache-friendly iteration. HashMap<K, V> is a hash table: O(1) average lookup, no ordering, and it requires K: Hash + Eq. BTreeMap<K, V> is a balanced B-tree: O(log n) lookup, keys always sorted, and it only needs Ord.

The Entry API is the part that separates idiomatic Rust from a port of another language's map code. map.entry(key).or_insert(default) performs one lookup and hands back a mutable reference to the value, so you do not hash the key twice and you do not play games with contains_key followed by insert. and_modify and or_insert_with extend the same idea to update-or-create.

Two decisions cover most cases. Choose Vec unless you need keyed lookup; choose BTreeMap when you need ordered iteration or range queries (or a deterministic serialization order); choose HashMap for everything else. And size Vec with with_capacity and maps with with_capacity when the final size is known — rehashing and reallocation are the two easiest performance wins in Rust code.

Basic Syntax & Signature

rust
use std::collections::{BTreeMap, HashMap, VecDeque}; fn main() { // Vec: push, index, iterate, reserve. let mut v: Vec<u32> = Vec::with_capacity(4); v.push(3); v.extend([1, 2]); v.sort_unstable(); assert_eq!(v, [1, 2, 3]); assert_eq!(v.get(9), None); // safe lookup // v[9] would panic: index out of bounds // HashMap: insert, get, entry. let mut scores: HashMap<&str, u32> = HashMap::new(); scores.insert("ada", 10); scores.insert("bob", 7); // Entry API: single lookup, mutable access. let entry = scores.entry("ada").or_insert(0); *entry += 5; assert_eq!(scores["ada"], 15); // Increment a counter, creating on first sight. for word in ["a", "b", "a"].iter() { *scores.entry(word).or_insert_with(|| 0) += 1; } // BTreeMap: sorted keys, range queries. let mut tree: BTreeMap<u64, &str> = BTreeMap::new(); tree.insert(30, "thirty"); tree.insert(10, "ten"); tree.insert(20, "twenty"); let ordered: Vec<_> = tree.keys().copied().collect(); assert_eq!(ordered, [10, 20, 30]); for (k, v) in tree.range(15..=30) { println!("{k}: {v}"); } // VecDeque: O(1) push/pop at both ends. let mut q: VecDeque<u8> = VecDeque::new(); q.push_back(1); q.push_front(0); assert_eq!(q.pop_front(), Some(0)); }

The signatures worth memorizing:

rust
// Vec fn with_capacity(n: usize) -> Vec<T>; fn push(&mut self, value: T); fn pop(&mut self) -> Option<T>; fn get(&self, index: usize) -> Option<&T>; fn get_mut(&mut self, index: usize) -> Option<&mut T>; fn retain<F: FnMut(&T) -> bool>(&mut self, f: F); fn drain<R: RangeBounds<usize>>(&mut self, range: R) -> Drain<'_, T>; fn split_off(&mut self, at: usize) -> Vec<T>; fn binary_search(&self, x: &T) -> Result<usize, usize> where T: Ord; // HashMap fn entry(&mut self, key: K) -> Entry<'_, K, V>; fn or_insert(self, default: V) -> &'a mut V; fn or_insert_with<F: FnOnce() -> V>(self, f: F) -> &'a mut V; fn and_modify<F: FnOnce(&mut V)>(self, f: F) -> Self; fn or_default(self) -> &'a mut V where V: Default; // BTreeMap fn range<T: ?Sized + Ord, R: RangeBounds<T>>(&self, range: R) -> Range<'_, K, V> where K: Borrow<T> + Ord; fn first_key_value(&self) -> Option<(&K, &V)>; fn pop_first(&mut self) -> Option<(K, V)>;

Key Comparison Table

ContainerBacking structureLookupInsertOrderedKey boundBest for
Vec<T>Contiguous heap bufferO(1) index, O(n) searchO(1) amortizedInsertion order—Sequences, iteration-heavy code
HashMap<K, V>SwissTable (open addressing)O(1) averageO(1) averageNoHash + EqFast keyed lookup, counters
BTreeMap<K, V>B-tree, node size 6–11O(log n)O(log n)Sorted by keyOrdRanges, ordered output, reproducibility
BTreeSet<T> / HashSet<T>Same as above, keys onlyO(log n) / O(1)O(log n) / O(1)Sorted / NoOrd / Hash + EqMembership tests, dedupe
VecDeque<T>Ring bufferO(1) at endsO(1) at endsInsertion order—Queues, sliding windows
BinaryHeap<T>Binary heap on a VecO(1) peekO(log n)Max-firstOrdPriority queues, top-k

The memory difference matters at scale: HashMap trades load factor headroom for speed (roughly 1–2 bytes of control metadata per slot plus unused capacity), BTreeMap packs keys tightly in nodes but pays log n comparisons. A 10-million-entry integer map is often better as a sorted Vec<(u32, T)> with binary_search, which the standard library makes easy and which avoids hashing entirely.

Practical Edge Cases & Deep Dives

1. entry to avoid double hashing and borrow errors

rust
use std::collections::HashMap; #[derive(Debug, Default)] struct Stats { hits: u64, misses: u64 } fn record(map: &mut HashMap<String, Stats>, key: &str, hit: bool) { // One lookup. The `and_modify` branch runs only when the key exists. map.entry(key.to_string()) .and_modify(|s| if hit { s.hits += 1 } else { s.misses += 1 }) .or_insert_with(|| if hit { Stats { hits: 1, misses: 0 } } else { Stats { hits: 0, misses: 1 } }); } fn main() { let mut m = HashMap::new(); record(&mut m, "a", true); record(&mut m, "a", false); assert_eq!(m["a"].hits, 1); assert_eq!(m["a"].misses, 1); }

The naive version — if let Some(v) = map.get_mut(k) { ... } else { map.insert(...) } — does not compile in the borrow checker: the mutable borrow from get_mut lives across the else branch in older borrow-checker formulations, and even where NLL accepts it, the key is hashed twice and the key is moved into insert while still borrowed for the lookup. entry solves both problems at once.

2. Word frequency with a deterministic order

rust
use std::collections::{BTreeMap, HashMap}; fn top_words(text: &str, limit: usize) -> Vec<(String, usize)> { let mut counts: HashMap<&str, usize> = HashMap::new(); for word in text.split_whitespace() { *counts.entry(word).or_insert(0) += 1; } // HashMap iteration order varies between runs; collect into a Vec and // sort with an explicit tie-breaker for reproducibility. let mut ranked: Vec<(String, usize)> = counts.into_iter().map(|(w, c)| (w.to_string(), c)).collect(); ranked.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0))); ranked.truncate(limit); ranked } // Or keep the map itself ordered, at the cost of log-n inserts. fn counts_sorted(text: &str) -> BTreeMap<String, usize> { let mut m = BTreeMap::new(); for w in text.split_whitespace() { *m.entry(w.to_string()).or_insert(0) += 1; } m } fn main() { let text = "b a b c a b"; assert_eq!(top_words(text, 2), vec![("b".into(), 3), ("a".into(), 2)]); assert_eq!(counts_sorted(text).keys().cloned().collect::<Vec<_>>(), vec!["a".to_string(), "b".into(), "c".into()]); }

Note the lifetime: HashMap<&str, usize> borrows from text, so it cannot outlive it. When the map escapes the function, keys must be owned (String), which is exactly the clone cost the lifetime tie avoids.

3. retain, drain, and the O(n) removal trap

rust
fn main() { let mut v = vec![1, 2, 3, 4, 5, 6]; // O(n): keeps order, drops the rest in place. v.retain(|x| x % 2 == 0); assert_eq!(v, [2, 4, 6]); // `remove(i)` is O(n) because it shifts the tail; for bulk removal, // `retain` or `swap_remove` (O(1), unordered) are the alternatives. let mut w = vec!['a', 'b', 'c']; assert_eq!(w.swap_remove(0), 'a'); // ['c', 'b'] — order changed assert_eq!(w.remove(0), 'c'); // ['b'] — order kept // Drain a range and reuse the allocation. let mut buf: Vec<u8> = (0..8).collect(); let head: Vec<u8> = buf.drain(..3).collect(); assert_eq!(head, [0, 1, 2]); assert_eq!(buf, [3, 4, 5, 6, 7]); assert!(buf.capacity() >= 8); // allocation retained // Indexing after mutation of length is the classic panic source. buf.clear(); assert_eq!(buf.get(0), None); // buf[0] -> panic: index out of bounds: the len is 0 but the index is 0 }

A Vec::remove inside a loop is the single most common accidental O(n²) in Rust review. retain or a reverse loop with swap_remove are the two replacements; drain is for extracting a contiguous block without reallocating.

4. BTreeMap ranges, ordering, and struct keys

rust
use std::collections::BTreeMap; #[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone)] struct Version { major: u8, minor: u8, patch: u8 } fn main() { let mut releases: BTreeMap<Version, &str> = BTreeMap::new(); releases.insert(Version { major: 1, minor: 10, patch: 0 }, "1.10.0"); releases.insert(Version { major: 1, minor: 2, patch: 0 }, "1.2.0"); releases.insert(Version { major: 2, minor: 0, patch: 0 }, "2.0.0"); // Iteration follows field order of the derived Ord: 1.2.0 < 1.10.0 < 2.0.0 let names: Vec<&str> = releases.values().copied().collect(); assert_eq!(names, ["1.2.0", "1.10.0", "2.0.0"]); let in_range: Vec<&&str> = releases .range(Version { major: 1, minor: 0, patch: 0 }..Version { major: 2, minor: 0, patch: 0 }) .map(|(_, name)| name) .collect(); assert_eq!(in_range, [&"1.2.0", &"1.10.0"]); assert_eq!(releases.pop_first(), Some((Version { major: 1, minor: 2, patch: 0 }, "1.2.0"))); }

Deriving Ord on a struct compares fields in declaration order, which is normally what you want for composite keys. A subtle bug: deriving Ord for a struct whose logical sort is not declaration order (say a struct with a HashMap field, or one where the ID should sort after the timestamp) silently produces the wrong ordering everywhere, because BTreeMap trusts it completely.

5. Custom hashers and the Hash contract

rust
use std::collections::HashMap; use std::hash::{BuildHasherDefault, Hasher}; // A tiny FNV-1a hasher: faster than SipHash for small integer keys, // and NOT HashDoS resistant. Use only for trusted or internal data. #[derive(Default)] struct Fnv(u64); impl Hasher for Fnv { fn finish(&self) -> u64 { self.0 } fn write(&mut self, bytes: &[u8]) { let mut h = if self.0 == 0 { 0xcbf29ce484222325 } else { self.0 }; for b in bytes { h ^= *b as u64; h = h.wrapping_mul(0x100000001b3); } self.0 = h; } } fn main() { // Do not hold the DefaultHasher, the map's default SipHash key, across // `HashMap::new()` calls expecting a stable iteration order: iteration // order is unspecified and changes per process. let mut m: HashMap<u32, &str, BuildHasherDefault<Fnv>> = HashMap::default(); m.insert(1, "one"); assert_eq!(m.get(&1), Some(&"one")); // The Hash/Eq contract: if a == b then hash(a) == hash(b). // Implementing Hash by hand and deriving PartialEq, or vice versa, // produces a map that cannot find keys that are present. }

If a type implements PartialEq in a way that ignores a field, Hash must ignore that field too. Violating this doesn't fail to compile; it produces None for keys that are visibly in the map, which is a genuinely hard bug to trace back.

Common Compilation/Runtime Mistakes

Error / symptomCauseFix
panicked at index out of boundsv[i] past len, or a stale index after remove/clearUse get/get_mut, or re-check len after mutation
E0502: cannot borrow as mutable because it is also borrowed as immutableHolding m.get(&k) while calling m.insertRestructure with entry, or clone the borrowed value
E0599: no method named 'entry' foundContainer is BTreeMap and method name typo, or a custom map without the APIBTreeMap does have entry; check the import and receiver type
E0277: the trait bound 'K: Hash' is not satisfiedKey type lacks Hash/EqDerive both, or use BTreeMap with Ord
Key inserted but get returns NoneHand-written Hash inconsistent with Eq, or a float key with NaNDerive both, or wrap floats in an ordered newtype
E0277: 'T: Ord' not satisfied on sortSorting a Vec<f64>sort_by(f64::total_cmp)
Iteration order differs between runsHashMap order is unspecified and per-process randomizedUse BTreeMap, or sort before use
Memory keeps climbing with a long-lived HashMapKeys never removed after useremove, retain, or drain periodically
E0382: use of moved value after into_iterConsuming the collection then using it againIterate by reference, or clone deliberately
swap_remove corrupts output orderUnordered O(1) removalUse remove when order must hold

A last note on HashMap::new() versus HashMap::default(): they are the same thing for the standard hasher, and both are fine. What is not fine is storing a &HashMap inside a struct that also mutates it through another path — the borrow checker will reject it, and the fix is almost always to move the map into the owning struct's methods rather than to reach for RefCell.

Try matching browser tools

All tools

Small utilities that fit Rust work — they run entirely in this browser tab, so nothing you paste leaves your device.

All Rust guides

More in Rust

All Rust guides

The guides filed next to this one in Rust, in library order.