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).

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
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:
// 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
| Container | Backing structure | Lookup | Insert | Ordered | Key bound | Best for |
|---|---|---|---|---|---|---|
Vec<T> | Contiguous heap buffer | O(1) index, O(n) search | O(1) amortized | Insertion order | — | Sequences, iteration-heavy code |
HashMap<K, V> | SwissTable (open addressing) | O(1) average | O(1) average | No | Hash + Eq | Fast keyed lookup, counters |
BTreeMap<K, V> | B-tree, node size 6–11 | O(log n) | O(log n) | Sorted by key | Ord | Ranges, ordered output, reproducibility |
BTreeSet<T> / HashSet<T> | Same as above, keys only | O(log n) / O(1) | O(log n) / O(1) | Sorted / No | Ord / Hash + Eq | Membership tests, dedupe |
VecDeque<T> | Ring buffer | O(1) at ends | O(1) at ends | Insertion order | — | Queues, sliding windows |
BinaryHeap<T> | Binary heap on a Vec | O(1) peek | O(log n) | Max-first | Ord | Priority 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
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
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
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
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
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 / symptom | Cause | Fix |
|---|---|---|
panicked at index out of bounds | v[i] past len, or a stale index after remove/clear | Use get/get_mut, or re-check len after mutation |
E0502: cannot borrow as mutable because it is also borrowed as immutable | Holding m.get(&k) while calling m.insert | Restructure with entry, or clone the borrowed value |
E0599: no method named 'entry' found | Container is BTreeMap and method name typo, or a custom map without the API | BTreeMap does have entry; check the import and receiver type |
E0277: the trait bound 'K: Hash' is not satisfied | Key type lacks Hash/Eq | Derive both, or use BTreeMap with Ord |
Key inserted but get returns None | Hand-written Hash inconsistent with Eq, or a float key with NaN | Derive both, or wrap floats in an ordered newtype |
E0277: 'T: Ord' not satisfied on sort | Sorting a Vec<f64> | sort_by(f64::total_cmp) |
| Iteration order differs between runs | HashMap order is unspecified and per-process randomized | Use BTreeMap, or sort before use |
Memory keeps climbing with a long-lived HashMap | Keys never removed after use | remove, retain, or drain periodically |
E0382: use of moved value after into_iter | Consuming the collection then using it again | Iterate by reference, or clone deliberately |
swap_remove corrupts output order | Unordered O(1) removal | Use 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 toolsSmall utilities that fit Rust work — they run entirely in this browser tab, so nothing you paste leaves your device.
Related Rust guides
All Rust guidesRust Unsafe: Raw Pointers, FFI Bindings, and Soundness Invariants
What unsafe actually unlocks, the five soundness contracts behind raw pointers, and the FFI rules for repr(C), CString and unwinding.
Rust Pin and Unpin: Memory Pinning, Self-Referential Structs, and Futures
Why a future must not move after polling starts, what Unpin opts out of, and how Box::pin, pin! and map_unchecked_mut express that guarantee.
Rust Arrays and Slices: Fixed Arrays, &[T] Fat Pointers, and DSTs
An array carries its length in its type; a slice carries it in the pointer. The split_at_mut, chunks and TryFrom patterns that follow from that.
Rust Macros: macro_rules! Patterns, Hygiene, and Procedural Macros
Matcher fragments, repetition, hygiene and the proc-macro crate. How to read a macro_rules! error and when a derive macro is the right tool.
More in Rust
All Rust guidesThe guides filed next to this one in Rust, in library order.