Crust of Rust:

std::collections

This chapter provides an exhaustive deep dive into Rust's standard collection types (std::collections), examining their internal memory layouts, operational complexities, performance trade-offs, and practical selection criteria.

1. Why Do We Need This? (The Philosophy of std::collections)

The standard library collections (std::collections) encompass sequences, maps, sets, and miscellaneous data structures. Notably, this set of types has remained virtually untouched since Rust 1.0. This deliberate stability is driven by two main factors:

1. Sufficiency: The current collection types satisfy the vast majority of real-world computing requirements without bloating the standard library.
2. API Locking: Once a data structure enters the standard library, its API and core behaviors are permanently locked by Rust's backward compatibility guarantees. Breaking changes become impossible, and users inevitably come to rely on nuanced runtime characteristics and implementation details.

Consequently, modern performance-critical or specialized data structures (such as hashbrown, smallvec, or indexmap) are developed as external crates on crates.io. This allows them to iterate rapidly, explore novel memory optimizations, and make distinct trade-offs without encumbering the standard distribution.

2. Core Mental Model & Categorization

Rust collections are organized into three fundamental groups alongside a miscellaneous priority queue bucket:

3. Sequence Types: Vectors (Vec<T>)

The vector (Vec<T>) is the default and most heavily optimized sequence type in Rust.

Internal Memory Representation

At its core, a Vec<T> consists of three machine words on the stack:

• A pointer to a contiguous heap allocation.
• A Capacity (usize), tracking the total number of elements the allocation can hold without reallocating.
• A Length (usize), tracking the number of initialized, accessible elements.

Capacity vs. Length and Growth Strategy

• Capacity: The maximum number of elements the current heap buffer can store without triggering a reallocation.
• Length: The number of elements currently initialized and valid.

When length == capacity, attempting to push a new element forces a dynamic reallocation:

Performance Optimization: with_capacity

When the target size is known in advance, pre-allocating memory using Vec::with_capacity(n) avoids intermediate reallocations and copies, preventing latency spikes in performance-critical paths.

// Naive: Triggers log2(N) reallocations and multiple memory copies
let mut v1 = Vec::new();
for i in 0..1_000_000 {
    v1.push(i);
}

// Optimized: Allocates backing memory exactly once upfront
let mut v2 = Vec::with_capacity(1_000_000);
for i in 0..1_000_000 {
    v2.push(i);
}

Advanced Vector Operations

• swap_remove: Standard remove(index) shifts every subsequent element left via memcopy, incurring an $O(n)$ cost. swap_remove(index) replaces the target element with the last element and pops it in $O(1)$ time, sacrificing ordering for speed.
• set_len (Unsafe): Directly modifies the internal length counter. Useful in foreign function interfaces (FFI) when a C library writes into a vector's spare capacity buffer, but passing a length greater than capacity causes instant undefined behavior (buffer overflow).
• Vec::leak: Consumes the vector and surrenders ownership of its allocation, returning a mutable static slice (&'static mut [T]). Useful for long-lived configuration data initialized at runtime.

4. Alternative Sequences: SmallVec and VecDeque

Small Vector Optimization (smallvec)

Standard vectors always allocate their backing storage on the heap. For programs handling many tiny collections, heap allocation overhead and pointer indirection degrade CPU cache locality. The SmallVec crate introduces an inline array directly on the stack for sizes up to a compile-time threshold $N$, seamlessly migrating to the heap only if length exceeds $N$:

Double-Ended Queue (VecDeque<T>)

A VecDeque<T> is a double-ended queue backed by a growable contiguous ring buffer governed by two internal indices (head and tail).

• Advantages: Provides $O(1)$ amortized insertion and removal at both ends via push_front, push_back, pop_front, and pop_back.
• Trade-offs: Because the logical sequence can wrap around the physical array boundaries, a VecDeque cannot be dereferenced into a single contiguous slice (&[T]) without calling make_contiguous(), which incurs a memory rearrangement cost.

5. Linked Lists (LinkedList<T>)

A LinkedList<T> in Rust is implemented as a doubly linked list where every individual node resides in an isolated heap allocation holding forward and backward pointers.

Industry Reality & Debugging Mindset

The Rust standard documentation explicitly advises against using LinkedList in almost all production scenarios:

Note: Array-based containers like Vec and VecDeque drastically outperform LinkedList on modern hardware. Because nodes in a linked list are scattered across the heap, traversing them causes continuous CPU cache misses. Contiguous arrays leverage hardware prefetching and cache lines far more effectively.

Linked lists only yield an algorithmic advantage when splitting, splicing, or unlinking nodes at arbitrary positions in $O(1)$ time where a direct pointer or cursor is already held. In safe Rust, pointers are encapsulated, which limits this advantage unless using nightly Cursor APIs.

6. Maps and Sets: Hash vs. B-Tree Architecture

Rust provides two primary associative container paradigms: hash-based and tree-based. Conceptually, a HashSet<T> is simply a wrapper around a HashMap<T, ()> where values are zero-sized unit types.

7. Deep Dive: HashMap Internals & Collision Resistance

Probing Strategies and Swiss Table Architecture

The standard library HashMap delegates its core implementation to the hashbrown crate, based on Google's Swiss Table algorithm:

• Backing memory consists of a single allocation split into Control Bytes (metadata) and Slots (keys and values).
• When a key is inserted, its 64-bit hash is computed. The top 7 bits are stored in the control byte array (for fast SIMD-accelerated filtering), while the bottom bits determine the initial slot index.
• If collisions occur, probing scans subsequent slots in the table.

Denial of Service (Hash DoS) Resistance

To protect networked applications from algorithmic complexity attacks—where an adversary deliberately sends colliding keys to force $O(n)$ worst-case lookup degradation—Rust's default HashMap uses RandomState (a cryptographically secure hasher based on SipHash-1-3) with randomized per-instance keys.

pub struct HashMap<K, V, S = RandomState> {
    base: hashbrown::HashMap<K, V, S>,
}

Performance Tip: If your application does not process untrusted external inputs and requires maximum hashing throughput (e.g., in a compiler or game engine), you can swap RandomState for a faster non-cryptographic hasher such as FxHash or AHash by configuring the generic parameter S.

8. The Map Entry API

The Entry API is an idiomatic Rust design pattern that prevents double lookups by combining search, insertion, and mutation into a single hashing and traversal step.

Naive Lookup vs. Entry API

use std::collections::HashMap;

let mut scores: HashMap<String, u32> = HashMap::new();

// Naive: Performs 2 full hashing and lookup passes
if scores.contains_key("player_one") {
    let score = scores.get_mut("player_one").unwrap();
    *score += 10;
} else {
    scores.insert("player_one".to_string(), 10);
}

// Idiomatic Entry API: Hashes and locates bucket exactly once
scores.entry("player_one".to_string())
    .and_modify(|score| *score += 10)
    .or_insert(10);

9. Miscellaneous Collections: BinaryHeap<T>

A BinaryHeap<T> is a priority queue implemented as a binary heap stored in a flat Vec<T>.

Key Operational Characteristics

• Default Order: Max Heap (the highest element according to Ord is always at the root).
• Push: $O(1)$ amortized (appends to vector and sifts up).
• Peek: $O(1)$ (inspects index 0).
• Pop: $O(\log n)$ (swaps root with last element, pops, and sifts down).
• Duplicates: Fully supported (unlike BTreeSet or HashSet).

Constructing a Min-Heap

Because BinaryHeap defaults to a Max Heap, storing elements in reverse order requires wrapping values in std::cmp::Reverse:

use std::collections::BinaryHeap;
use std::cmp::Reverse;

let mut min_heap = BinaryHeap::new();

// Push items wrapped in Reverse
min_heap.push(Reverse(100));
min_heap.push(Reverse(25));
min_heap.push(Reverse(50));

// Pops the smallest item first: 25
if let Some(Reverse(smallest)) = min_heap.pop() {
    assert_eq!(smallest, 25);
}

Summary and Key Takeaways

• Vec<T> as the Default: The vector is the standard continuous-memory sequence type. Always use Vec::with_capacity when the final size is predictable to eliminate reallocation overhead.
• Ring Buffer with VecDeque<T>: Ideal for FIFO queues or double-ended operations ($O(1)$ at both ends), though it sacrifices direct slice dereferencing unless made contiguous.
• Cache Locality over LinkedList<T>: Linked lists scatter allocations across the heap, leading to cache misses. Array-backed structures almost always deliver higher throughput on modern CPU architectures.
• Hash vs. B-Tree Maps: Use HashMap for fast, amortized $O(1)$ lookups when key ordering does not matter; choose BTreeMap ($O(\log n)$) when keys must remain sorted or when performing range queries.
• Security-First Hashing: HashMap defaults to SipHash-1-3 via RandomState to prevent algorithmic Hash DoS attacks. You can substitute faster, non-cryptographic hashers when handling trusted internal data.
• Efficient Mutations via Entry API: Use map.entry(key) to consolidate inspection and mutation into a single bucket lookup pass.
• Priority Queues with BinaryHeap<T>: Provides max-heap operations backed by a vector; wrap elements in std::cmp::Reverse to invert it into a min-heap.
• Specialized Ecosystem Crates: Reach for crates like smallvec (stack-allocated small sequences) or indexmap (order-preserving hash maps) when standard library trade-offs do not match your workload requirements.