Collection Types

Vec is a contiguous array on the heap (O(1) random access, amortized O(1) tail insertion), HashMap uses SwissTable (cache-friendly open addressing), BTreeMap is sorted by key (Vec’s cache locality vs BTreeMap’s ordered traversal—you can’t have both). VecDeque is a ring buffer with O(1) insertion at both ends. Selection depends on access patterns: sequential traversal with Vec, key lookup with HashMap, range queries with BTreeMap.

Vec: Dynamic Array

let mut v = Vec::with_capacity(100);  // Pre-allocate — avoids realloc on push
v.push(42);

Internally (24 bytes on the stack for 64-bit): [ptr: 8B | len: 8B | cap: 8B], where ptr points to a [T; cap] array on the heap.

Growth strategy: When len == cap, the new capacity becomes max(old × 2, len + 1). This is the classic strategy for amortized O(1) pushes. Note: realloc may copy data to a new address—any references to elements in the old Vec become dangling after reallocation. This is why the borrow checker prohibits pushing while holding a reference to an element.

HashMap: Default SipHash, Optional FxHash

use std::collections::HashMap;
let mut map = HashMap::new();
map.insert("key", 42);

The standard library’s HashMap uses SipHash 1-3 by default. Why not a faster hash? SipHash is designed to be resistant to HashDoS attacks—where an attacker constructs many keys that produce the same hash, causing HashMap lookups to degrade to O(n) and amplifying CPU resource consumption. SipHash uses a random key (generated at each process startup), so attackers cannot predict hash results.

Trade-off: SipHash is 10-30% slower than FxHash. If your input is controlled (keys are not exposed externally), you can use rustc_hash::FxHashMap (the hash table used by rustc itself)—it is a fast hash based on integer arithmetic, but it is not resistant to HashDoS.

BTreeMap: Ordered Collection

B-tree structure: keys are stored in sorted order, with each node containing B keys. Lookup/insertion is O(log N). Advantages over HashMap:

• Range scan: map.range("a".."z") is O(log N + K), which HashMap cannot do (unordered)
• Predictable performance: No worst-case O(N) degradation (HashMap may degrade during collisions)
• Memory locality: B-tree nodes are contiguous (cache-friendly)

Use cases: Ordered traversal and key-range queries.

VecDeque: Optimized for Double-Ended Operations

Internally uses a ring buffer—both push_front and push_back are O(1) amortized. Suitable for FIFO queues and double-ended queues. Difference from Vec: Vec::remove(0) is O(n) (requires memmove for all elements), whereas VecDeque::pop_front is O(1) (only moves the ring buffer pointers).

Selection Guide

References

• Rust Book: Chapter 8
• hashbrown: Rust HashMap implementation (now part of std)
• smallvec: docs.rs/smallvec

Keywords: Vec, HashMap, BTreeMap, VecDeque, SipHash, FxHash, ring buffer, reallocation