Rust Detailed Collections Overview

The Rust standard library ships with a carefully chosen family of collection types. In the previous chapter you met the three that appear in nearly every Rust program: Vec<T>, String, and HashMap<K,V>. Those are the front door. This section opens the rest of the house.

Every one of the collections covered here answers a specific need that the basics don’t cover—double‑ended queues, priority ordering, sorted map lookup, set arithmetic, and fine‑grained control over hashing. None of them are niche. They are the structures you reach for when Vec::push / Vec::pop at the back stops being enough, or when iteration order starts to matter, or when you need to guarantee uniqueness without hand‑rolling a loop.

Why Detailed Knowledge Matters

Choosing the right collection is one of the few architectural decisions that shows up in every function you write. A VecDeque can make a work queue behave smoothly instead of turning into a hidden bottleneck. Using BTreeMap for range queries removes entire classes of sorting bugs. Understanding how HashMap hashes your keys prevents denial‑of‑service surprises in production.

Rust’s ownership and borrowing rules interact with collections in ways that are not obvious the first time you encounter them. A LinkedList might appear perfect for inserting in the middle of a sequence, but its memory access patterns conflict with how modern CPUs fetch data—so a Vec often wins even when theory says it shouldn’t. The upcoming pages give you the mental models to make those trade‑offs without guesswork.

Quick Reference — What Each Collection Solves

Collection	Core Capability	When You’d Use It
Vec<T> (in‑depth)	Contiguous growable array	Default choice for sequences; you now learn capacity, slicing, and layout details
VecDeque<T>	Ring buffer — efficient push/pop at both ends	Building a work‑stealing queue, a sliding window, or any FIFO that needs front deletion
LinkedList<T>	Doubly‑linked list	Rare in idiomatic Rust; useful for splitting/merging large sequences without reallocation
BinaryHeap<T>	Max‑heap priority queue	Task scheduling, Dijkstra’s algorithm, retrieving the largest element in O(log n)
HashMap<K,V>	Fast key‑value lookup (average O(1))	Counting occurrences, caching, any “look up by name”
BTreeMap<K,V>	Sorted key‑value map (O(log n) lookup)	Range queries (“all events between timestamp A and B”), ordered traversal
HashSet<T>	Unordered unique set (based on HashMap)	Removing duplicates, membership tests, set operations (union, intersect)
BTreeSet<T>	Sorted unique set (based on BTreeMap)	Same as HashSet when you need elements in order or range queries
Hashing	Swappable hash algorithm powering the map/set types	Defending against HashDoS, tuning performance, using custom key types
Beyond std	Crates like smallvec, indexmap, dashmap	Embedding small arrays on the stack, preserving insertion order, concurrent access

A Guided Walk Through Each Topic

Vec<T> In‑Depth — The Workhorse Under a Microscope

You’ve pushed and popped, maybe sliced. The in‑depth treatment reveals how a vector’s pointer, length, and capacity work together, why Vec::with_capacity can erase whole allocations from a hot loop, and what it actually means when the compiler says “cannot borrow as mutable because it is also borrowed as immutable.” You’ll leave that page able to read and write unsafe‑adjacent vector patterns without fear.

VecDeque<T> — The Double‑Ended Queue

A VecDeque is laid out as a ring buffer: one contiguous allocation where the “start” of the queue can wrap around. That design makes push_front and pop_front as cheap as push_back and pop_back—amortized O(1). When you need a FIFO queue or a deque for graph traversal, VecDeque is almost always the right call.

LinkedList<T> — Know It, Then Probably Avoid It

Rust includes a fully‑safe doubly‑linked list in the standard library because some algorithms genuinely need O(1) splicing. But a LinkedList scatters its nodes across the heap, tanking cache locality. For most workloads, Vec or VecDeque will outperform it. The page explains exactly when the trade‑off flips in LinkedList’s favor.

BinaryHeap<T> — Priority Without the Sorting

A max‑heap keeps the largest element accessible in constant time and handles insertion/removal in O(log n). No full sort required. That’s the backbone of any priority‑based scheduler, from operating system task queues to game‑engine event systems. The docs walk through peek, pop, and how to flip the order with Reverse.

HashMap<K,V> and BTreeMap<K,V> — Two Maps, Two Philosophies

Hash maps answer “what value is associated with this key?” in average constant time. B‑tree maps answer the same question in logarithmic time, but they maintain keys in sorted order, making range queries efficient. The detailed pages dive into the Entry API, custom key types, and the real‑world performance gap between O(1) and O(log n) when constants matter.

HashSet<T> and BTreeSet<T> — Sets With and Without Order

A set is a map where you only care about the key’s presence. The hash‑based version runs the same lookup‑time story as HashMap; the tree‑based version gives you sorted iteration and range operations. This section covers deduplication patterns, set algebra (union, intersection, difference), and the insert return value that tells you whether the element was new.

Hashing — The Invisible Glue

Every HashMap and HashSet delegates to a hasher that converts keys into indices. Rust’s default hasher, SipHash‑1‑3, provides resistance against collision‑based denial‑of‑service attacks. You can swap it out for a faster (but less secure) hasher like FxHash when you control all the keys and need raw throughput. This page shows you how.

Beyond the Standard Collections

The standard library stops where the ecosystem begins. Crates like smallvec store a few elements on the stack before falling back to the heap. indexmap retains insertion order like a Python dict. dashmap provides concurrent access without the ceremony of Mutex<HashMap>. The final page surveys the most battle‑tested options so you know what’s available once std no longer fits.

How to Approach These Pages

Read them in order if you’re new. The sequence builds naturally—from the familiar Vec to ring buffers, then into linked nodes, heaps, maps, sets, and finally the hashing engine underneath everything. If you already have a specific problem, jump straight to the collection that matches it and use the quick reference table above as a compass.

Each sub‑page is written to be self‑contained. If you land on BinaryHeap from a search, you won’t need to have read VecDeque first. But reading the set together—VecDeque after Vec, HashSet after HashMap—will layer understanding in a way that makes the whole family feel coherent.

Summary

The collections in this chapter are not exotic. They solve real, recurring problems that emerge in everyday Rust code. The difference between a developer who reaches for Vec for everything and one who pulls out VecDeque for a sliding window or BTreeMap for ordered statistics is not cleverness—it’s comfort with the toolbelt. These pages exist to build that comfort, one data structure at a time.