Chapter 18: Common Collection Types

In C programming, managing groups of data elements whose size is unknown at compile time typically requires manual memory management using functions like malloc, realloc, and free. While flexible, this approach is notoriously prone to errors, including memory leaks, double frees, use-after-free bugs, and buffer overflows, which can lead to crashes or security vulnerabilities.

Rust provides built-in collection types to handle dynamic data safely and efficiently. These are data structures capable of storing multiple values. Unlike fixed-size arrays or tuples, standard collections such as Vec<T>, String, and HashMap<K, V> store their data on the heap and can grow or shrink as needed during program execution. They abstract away the complexities of manual memory management, leveraging Rust’s ownership and borrowing system to guarantee memory safety without sacrificing performance.

This chapter introduces the most frequently used collection types in Rust. We will explore their characteristics, compare them with C idioms and fixed-size Rust types, and demonstrate how they facilitate dynamic data management safely.

18.1 Overview of Collections and Comparison with C

For developers coming from C, the most significant advantage of Rust’s collections is their automatic resource management. Instead of manually orchestrating malloc, realloc, and free, and meticulously tracking allocation sizes and capacities, you utilize Rust’s standard library types that handle these details internally.

Rust’s collections offer safety and convenience through:

Automated Memory Management: Allocation and deallocation are handled automatically via Rust’s ownership system. When a collection variable goes out of scope, its destructor is called, freeing the associated heap memory and preventing leaks.
Type Safety: Collections are generic (e.g., Vec<T>), ensuring they hold elements of only one specific type T at compile time. This prevents type confusion errors common in C when using void* or untagged unions without careful management.
Compile-Time Safety Checks: Rust’s ownership and borrowing rules prevent common C errors like dangling pointers or data races when accessing collection elements, catching potential issues before runtime.

While providing these safety guarantees, Rust collections are designed for performance. Techniques like amortized constant-time appending to Vec<T> mean performance is often comparable to well-written C code using dynamic arrays, but with a substantially lower risk of memory-related bugs.

The primary collection types we will cover are:

Vec<T>: A growable, contiguous array, often called a vector. Analogous to C++’s std::vector or a manually managed dynamic array in C.
String: A growable, heap-allocated string guaranteed to contain valid UTF-8 encoded text. Conceptually similar to Vec<u8> but specialized for Unicode text.
HashMap<K, V>: A hash map for storing key-value pairs, offering fast average-case lookups. Similar to C++’s std::unordered_map or hash table implementations found in various C libraries.

Rust also provides specialized collections like BTreeMap, HashSet, BTreeSet, and VecDeque for specific requirements such as sorted data or double-ended queue operations. All standard collections adhere to Rust’s ownership rules, ensuring predictable and safe memory management.

18.2 The `Vec<T>` Vector Type

Vec<T>, commonly referred to as a “vector,” is Rust’s primary dynamic array type. The Vec<T> struct itself is a small object on the stack containing a pointer to its heap-allocated data, a length, and a capacity. This contiguous heap-based layout allows for efficient indexing (O(1) complexity) and iteration. A Vec<T> automatically manages its underlying buffer, resizing it as necessary when elements are added.

18.2.1 Creating a Vector

Vectors can be created in several ways:

Empty Vector with Vec::new():
```
#![allow(unused)]
fn main() {
let mut v: Vec<i32> = Vec::new();
v.push(1);
}
```
Vec::new() creates an empty vector on the stack and does not allocate any memory on the heap until the first element is pushed. Type annotation is often needed if the vector is initially empty and its type cannot be inferred from later usage.

Using the vec! Macro: A convenient shorthand for creating vectors with initial elements.

#![allow(unused)]
fn main() {
let v_empty: Vec<i32> = vec![];      // Creates an empty vector
let v_nums = vec![1, 2, 3];          // Infers Vec<i32>
let v_zeros = vec![0; 5];            // Creates vec![0, 0, 0, 0, 0]
}

From Iterators using collect(): Many iterators can be gathered into a vector.

#![allow(unused)]
fn main() {
// Creates vec![1, 2, 3, 4, 5]
let v_range: Vec<i32> = (1..=5).collect();
}

Converting from Slices or Arrays:

#![allow(unused)]
fn main() {
let slice: &[i32] = &[10, 20, 30];
// Creates an owned Vec<T> by cloning elements from the slice
let v_from_slice: Vec<i32> = slice.to_vec();
// Vec::from(slice) is equivalent to slice.to_vec()
let v_also_from_slice: Vec<i32> = Vec::from(slice);

let array: [i32; 3] = [4, 5, 6];
// For arrays [T; N] where T implements Copy, Vec::from(array) copies elements.
// This creates a Vec<T> from the array by copying.
let v_from_array: Vec<i32> = Vec::from(array);
// If T is not Copy, use iterators: `array.into_iter().collect()`
}

Pre-allocating Capacity with Vec::with_capacity(): If you have an estimate of the number of elements, pre-allocating can improve performance by reducing the frequency of reallocations.

#![allow(unused)]
fn main() {
// Allocate space for at least 10 elements upfront
let mut v_cap = Vec::with_capacity(10);
for i in 0..10 {
    v_cap.push(i); // No reallocations occur in this loop
}
// Pushing the 11th element might trigger a reallocation
v_cap.push(10);
}

18.2.2 Internal Structure and Memory Management

A Vec<T> internally consists of three components, typically stored on the stack:

A pointer to the heap-allocated buffer where the elements are stored contiguously.
length: The number of elements currently stored in the vector.
capacity: The total number of elements the allocated buffer can hold before needing to resize.

The invariant length <= capacity always holds. When adding an element (push) while length == capacity, the vector usually allocates a new, larger buffer (often doubling the capacity), copies the existing elements to the new buffer, frees the old buffer, and then adds the new element. This strategy results in an amortized O(1) time complexity for appending elements.

Removing elements decreases length but does not automatically shrink the capacity. You can call v.shrink_to_fit() to request that the vector release unused capacity, although the allocator might not always free the memory immediately.

When a Vec<T> goes out of scope, its destructor runs automatically. This destructor drops (cleans up) all elements contained within the vector and then frees the heap-allocated buffer, ensuring no memory leaks occur.

18.2.3 Common Methods and Operations

push(element: T): Appends an element to the end. Amortized O(1).
pop() -> Option<T>: Removes and returns the last element as an Option<T>. Returns Some(T) if the vector was not empty, or None if it was empty. O(1).
insert(index: usize, element: T): Inserts an element at index, shifting elements at index and higher indices one position towards higher indices. O(n). Panics if index > len.
remove(index: usize) -> T: Removes and returns the element at index, shifting elements at indices higher than index one position towards lower indices. O(n). Panics if index >= len.
get(index: usize) -> Option<&T>: Returns an immutable reference (&T) to the element at index wrapped in Some, or None if the index is out of bounds. Performs bounds checking. O(1).
get_mut(index: usize) -> Option<&mut T>: Returns a mutable reference (&mut T). Performs bounds checking. O(1).
Indexing (v[index]) : Provides direct access using square brackets, returning &T or &mut T. Panics the current thread if index is out of bounds. Use this only when certain the index is valid. O(1).
len() -> usize: Returns the current number of elements (length). O(1).
is_empty() -> bool: Checks if the vector contains zero elements (length == 0). O(1).
clear(): Removes all elements, setting length to 0 but retaining the allocated capacity. O(n) because it must drop each element.

18.2.4 Accessing Elements Safely

Rust offers two primary ways to access vector elements, prioritizing safety:

Indexing ([]): Provides direct access (&T or &mut T) but panics the current thread if the index is out of bounds. If the panicked thread is the main thread (and the panic is not caught), the program typically terminates. Use indexing when the index is guaranteed to be valid (e.g., within a loop 0..v.len()).
```
#![allow(unused)]
fn main() {
let v = vec![10, 20, 30];
let first: &i32 = &v[0]; // Ok, borrows the first element
// let fourth = v[3]; // This would panic the current thread at runtime
}
```

.get() method: Returns an Option<&T> (or Option<&mut T> for .get_mut()). This is the idiomatic way to handle potentially invalid indices without causing a panic.

#![allow(unused)]
fn main() {
let v = vec![10, 20, 30];
if let Some(second) = v.get(1) {
    println!("Second element: {}", second);
} else {
    // This branch is unreachable in this specific example
    println!("Index 1 is out of bounds.");
}

match v.get(3) {
    Some(_) => unreachable!(), // Should not happen -- index 3 on a 3-element vec
    None => println!("Index 3 is safely handled as out of bounds."),
}
}

Using .get() is generally preferred when the validity of an index isn’t absolutely certain at compile time or when a panic is unacceptable.

18.2.5 Iterating Over Vectors

Vectors support several common iteration patterns:

Immutable iteration (&v or v.iter()): Borrows the vector immutably, yielding immutable references (&T) to each element.

#![allow(unused)]
fn main() {
let v = vec![1, 2, 3];
for item in &v { // or v.iter()
    println!("{}", item);
}
// v is still usable here
}

Mutable iteration (&mut v or v.iter_mut()): Borrows the vector mutably, yielding mutable references (&mut T) allowing modification of elements.

#![allow(unused)]
fn main() {
let mut v = vec![10, 20, 30];
for item in &mut v { // or v.iter_mut()
    *item += 5; // Dereference to modify the value
}
// v is now vec![15, 25, 35]
}

Consuming iteration (v or v.into_iter()): Takes ownership of the vector and yields owned elements (T). The vector itself cannot be used after the iteration begins.

#![allow(unused)]
fn main() {
let v = vec![100, 200, 300];
for item in v { // v is moved here, equivalent to v.into_iter()
    println!("{}", item);
}
// Compile error: cannot use v anymore here, as it was moved
// println!("{:?}", v);
}

18.2.6 Storing Elements of Different Types

A Vec<T> requires all its elements to be of the exact same type T. If you need to store items of different types within a single collection, common approaches in Rust include:

Enums: Define an enum where each variant can hold one of the possible types. This is the most common and often most efficient method when the set of types is known at compile time.

enum DataItem {
    Integer(i32),
    Float(f64),
    Text(String),
}

fn main() {
let mut data_vec: Vec<DataItem> = Vec::new();
data_vec.push(DataItem::Integer(42));
data_vec.push(DataItem::Float(3.14));
data_vec.push(DataItem::Text("Hello".to_string()));

for item in &data_vec {
    match item {
        DataItem::Integer(i) => println!("Got an integer: {}", i),
        DataItem::Float(f) => println!("Got a float: {}", f),
        DataItem::Text(s) => println!("Got text: {}", s),
    }
}
}

Trait Objects: Use Box<dyn Trait> if the elements share a common behavior defined by a trait. This involves dynamic dispatch (runtime lookup of method calls) and requires heap allocation for each element via Box. It’s more flexible if the exact types aren’t known upfront but incurs runtime overhead.
```
// Example concept:
// trait Displayable { fn display(&self); }
// // ... implementations for different concrete types ...
//
// let mut items: Vec<Box<dyn Displayable>> = Vec::new();
// items.push(Box::new(MyType1 { /* ... */ }));
// items.push(Box::new(MyType2 { /* ... */ }));
// for item in &items { item.display(); } // Dynamic dispatch
```
Generally, prefer enums when the set of types is fixed and known.

18.2.7 Summary: `Vec<T>` vs. Manual C Dynamic Arrays

Compared to manually managing dynamic arrays in C using malloc/realloc/free:

Vec<T> provides automatic memory management, preventing leaks and double frees.
It guarantees memory safety, eliminating buffer overflows via bounds checking (panic or Option return).
It offers convenient, built-in methods for common operations (push, pop, insert, etc.).
Appending elements has amortized O(1) complexity, similar to optimized C implementations.
It gives control over allocation strategy via with_capacity and shrink_to_fit.

Vec<T> is the idiomatic, safe, and efficient way to handle growable sequences of homogeneous data in Rust.

18.3 The `String` Type

Rust’s String type represents a growable, mutable, owned sequence of UTF-8 encoded text. Like Vec<T>, the String struct itself is a small object on the stack, containing a pointer to its heap-allocated text data, a length, and a capacity. This design ensures that only the text data is stored on the heap, with the stack-based struct managing the heap-allocated memory. A call to String::new() does not allocate memory on the heap; it creates an empty String struct on the stack. The heap allocation happens only when data is first added to the string. This automatic and lazy memory management is a key advantage over manual C-style string handling.

18.3.1 Understanding `String` vs. `&str`

This distinction is fundamental in Rust and often a point of confusion for newcomers:

String: An owned, heap-allocated buffer containing UTF-8 text. It owns the data it holds. It is mutable (can be modified, e.g., by appending text) and responsible for freeing its memory when it goes out of scope. Think of it like a Vec<u8> specialized for UTF-8.
&str (string slice): A borrowed, immutable view into a sequence of UTF-8 bytes. It consists of a pointer to the data and a length. It does not own the data it points to. It can refer to part of a String, an entire String, or a string literal embedded in the program’s binary.
- String literals: Expressions like "hello" in your code have the type &'static str. The 'static lifetime means the reference is valid for the entire duration of the program, because the underlying string data ("hello") is embedded directly into the program’s binary data segment and thus lives forever.
- The str type: You might wonder about str without the &. str itself is the primitive sequence type, but it’s an unsized type (Dynamically Sized Type or DST) because its length isn’t known at compile time. Because variables and function arguments must have a known size, Rust requires that we always interact with str via pointers like &str (a “fat pointer” containing address and length) or Box<str> (an owned pointer). &str is the ubiquitous borrowed form.

You can get an immutable &str slice from a String easily (e.g., &my_string[..], or often implicitly via deref coercion), but converting a &str to an owned String usually involves allocating memory and copying the data (e.g., using .to_string() or String::from()).

18.3.2 `String` vs. `Vec<u8>`

While a String is internally backed by a buffer of bytes (like Vec<u8>), its primary difference is the UTF-8 guarantee. String methods ensure that the byte sequence remains valid UTF-8. If you need to handle arbitrary binary data, raw byte streams, or text in an encoding other than UTF-8, you should use Vec<u8> instead. Attempting to create a String from invalid UTF-8 byte sequences will result in an error or panic.

18.3.3 Creating and Modifying Strings

#![allow(unused)]
fn main() {
// Create an empty String
let mut s1 = String::new();

// Create from a string literal (&str)
let s2 = String::from("initial content");
let s3 = "initial content".to_string(); // Equivalent, often preferred style

// Appending content
let mut s = String::from("foo");
s.push_str("bar"); // Appends a &str slice. s is now "foobar"
s.push('!');       // Appends a single char. s is now "foobar!"
}

Appending uses similar reallocation strategies as Vec for amortized O(1) performance.

18.3.4 Concatenation

There are several ways to combine strings:

Using the + operator (via the add trait method): This operation consumes ownership of the left-hand String and requires a borrowed &str on the right.

#![allow(unused)]
fn main() {
let s1 = String::from("Hello, ");
let s2 = String::from("world!");
// s1 is moved here and can no longer be used directly.
// &s2 works because String derefs to &str.
let s3 = s1 + &s2;
println!("{}", s3); // Prints "Hello, world!"
// println!("{}", s1); // Compile Error: value used after move
}

Because + moves the left operand, chaining multiple additions can be inefficient and verbose (s1 + &s2 + &s3 + ...).

Using the format! macro: This is generally the most flexible and readable approach, especially for combining multiple pieces or non-string data. It does not take ownership of its arguments (it borrows them via references) and returns a newly allocated, owned String.

#![allow(unused)]
fn main() {
let name = "Rustacean";
let level = 99;
let s1 = String::from("Status: ");
let greeting = format!("{}{}! Your level is {}.", s1, name, level);
println!("{}", greeting); // Prints "Status: Rustacean! Your level is 99."
// s1, name, and level are still usable here because format! borrowed them.
println!("{} still exists.", s1);
}

18.3.5 UTF-8, Characters, and Indexing

Because String guarantees UTF-8, where characters can span multiple bytes (1 to 4), direct indexing by byte position (s[i]) to get a char is disallowed. This is a safety feature: a byte index might fall in the middle of a multi-byte character, leading to an invalid character boundary.

Instead, Rust provides methods to work with strings correctly:

Iterating over Unicode scalar values (char):

#![allow(unused)]
fn main() {
let hello = String::from("Здравствуйте"); // Russian "Hello" (multi-byte chars)
for c in hello.chars() {
    print!("'{}' ", c); // Prints 'З' 'д' 'р' 'а' 'в' 'с' 'т' 'в' 'у' 'й' 'т' 'е'
}
println!("\nNumber of chars: {}", hello.chars().count()); // 12 chars
}

Iterating over raw bytes (u8):

#![allow(unused)]
fn main() {
let hello = String::from("Здравствуйте");
for b in hello.bytes() {
    print!("{} ", b); // Prints the underlying UTF-8 bytes (2 bytes per char here)
}
println!("\nNumber of bytes: {}", hello.len()); // 24 bytes
}

Slicing (&s[start..end]): You can create &str slices using byte indices, but this will panic the current thread if the start or end indices do not fall exactly on UTF-8 character boundaries. Use with caution.

#![allow(unused)]
fn main() {
let s = String::from("hello");
let h = &s[0..1]; // Ok, slice is "h"

let multi_byte = String::from("नमस्ते"); // Hindi "Namaste", each char is 3 bytes
// The first char is at byte indices 0..3.
let first_char_slice = &multi_byte[0..3]; // Ok, slice is "न"
// let bad_slice = &multi_byte[0..1]; // PANIC! 1 is not on a character boundary
}

For operations sensitive to grapheme clusters (user-perceived characters, like ‘e’ + combining accent ‘´’), use external crates like unicode-segmentation.

18.3.6 Common `String` Methods

len() -> usize: Returns the length of the string in bytes (not characters). O(1).
is_empty() -> bool: Checks if the string has zero bytes. O(1).
contains(pattern: &str) -> bool: Checks if the string contains a given substring.
replace(from: &str, to: &str) -> String: Returns a new String with all occurrences of from replaced by to.
split(pattern) -> Split: Returns an iterator over &str slices separated by a pattern (char, &str, etc.).
trim() -> &str: Returns a &str slice with leading and trailing whitespace removed.
as_str() -> &str: Borrows the String as an immutable &str slice covering the entire string. Often done implicitly via deref coercion.

18.3.7 Summary: `String` vs. C Strings

Traditional C strings (char*, usually null-terminated) present several challenges that Rust’s String and &str system addresses:

Encoding Ambiguity: C strings lack inherent encoding information. They might be ASCII, Latin-1, UTF-8, or another encoding depending on context and platform. Rust’s String/&str guarantee UTF-8.
Length Calculation: Finding the length of a C string (strlen) requires scanning for the null terminator (\0), an O(n) operation. Rust’s String stores its byte length, making len() an O(1) operation. &str also includes the length as part of its fat pointer.
Memory Management: Manual allocation, resizing (malloc/realloc), and copying (strcpy/strcat) in C are common sources of buffer overflows and memory leaks. Rust’s String handles memory automatically and safely.
Mutability Risks: Modifying C strings in place requires careful buffer management to avoid overflows. String provides safe methods like push_str. &str is immutable, preventing accidental modification through slices.
Interior Null Bytes: C strings cannot contain null bytes (\0) as they signal termination. Rust Strings can contain \0 like any other valid UTF-8 character (though this is uncommon in text data).
Null Termination and FFI: Crucially, Rust Strings and &strs are not null-terminated. Passing a pointer from String::as_ptr() or a &str directly to a C function expecting a null-terminated const char* is unsafe and incorrect, as the C code might read past the end of the Rust string’s data. For safe interoperability when passing strings to C, Rust provides std::ffi::CString, which creates an owned, null-terminated byte sequence (checking for and prohibiting interior nulls). Interacting with C strings received from C typically uses std::ffi::CStr. (FFI details are covered elsewhere).

String and &str provide a robust, safe, and Unicode-aware system for handling text data, significantly improving upon the limitations and unsafety of traditional C strings, while offering specific mechanisms for safe C interoperability when needed.

18.4 The `HashMap<K, V>` Type

HashMap<K, V> is Rust’s primary implementation of a hash map (also known as a hash table, dictionary, or associative array). It stores mappings from unique keys of type K to associated values of type V. It provides efficient average-case time complexity for insertion, retrieval, and removal operations, typically O(1).

To use HashMap, you first need to bring it into scope:

#![allow(unused)]
fn main() {
use std::collections::HashMap;
}

18.4.1 Key Characteristics

Unordered: The iteration order of elements in a HashMap is arbitrary and depends on the internal hashing and layout. You should not rely on any specific order. The order might even change between different program runs.
Key Requirements: The key type K must implement the Eq (equality comparison) and Hash (hashing) traits. Most built-in types that can be meaningfully compared for equality, like integers, booleans, String, and tuples composed of hashable types, satisfy these requirements. Floating-point types (f32, f64) do not implement Hash by default because NaN != NaN and other precision issues make consistent hashing difficult. To use floats as keys, you typically need to wrap them in a custom struct that defines appropriate Hash and Eq implementations (e.g., by handling NaN explicitly or comparing based on bit patterns).
Hashing Algorithm: By default, HashMap uses SipHash 1-3, a cryptographically secure hashing algorithm designed to be resistant to Hash Denial-of-Service (HashDoS) attacks. These attacks involve an adversary crafting keys that deliberately cause many hash collisions, degrading the map’s performance to O(n). While secure, SipHash is slightly slower than simpler, non-cryptographic hashers. For performance-critical scenarios where HashDoS is not a concern (e.g., keys are not derived from external input), you can switch to a faster hasher using crates like fnv or ahash.
Ownership: HashMap takes ownership of its keys and values. When you insert an owned type like a String key or a Vec<T> value, that specific instance is moved into the map. If you insert types that implement the Copy trait (like i32), their values are copied into the map.

18.4.2 Creating and Populating a HashMap

#![allow(unused)]
fn main() {
use std::collections::HashMap; // Required import

// Create an empty HashMap
let mut scores: HashMap<String, i32> = HashMap::new();

// Insert key-value pairs using .insert()
// Note: .to_string() creates an owned String from the &str literal
scores.insert("Alice".to_string(), 95);
scores.insert(String::from("Bob"), 88); // String::from also works

// Create with initial capacity estimate
let mut map_cap: HashMap<u64, i32> = HashMap::with_capacity(50);

// Create from an iterator of tuples (K, V)
let teams = vec![String::from("Blue"), String::from("Red")];
let initial_scores = vec![10, 50];
// zip combines the two iterators into an iterator of pairs
// collect consumes the iterator and creates the HashMap
let team_scores: HashMap<String, i32> =
    teams.into_iter().zip(initial_scores.into_iter()).collect();
}

18.4.3 Accessing Values

#![allow(unused)]
fn main() {
use std::collections::HashMap;
let mut scores: HashMap<String, i32> = HashMap::new();
scores.insert(String::from("Alice"), 95);
scores.insert(String::from("Bob"), 88);

// Using .get(&key) for safe access (returns Option<&V>)
// Note: .get() takes a reference to the key type.
// If K is String, you can often pass &str due to borrowing rules.
let alice_score: Option<&i32> = scores.get("Alice");
match alice_score {
    Some(score_ref) => println!("Alice's score: {}", score_ref),
    None => println!("Alice not found."),
}

// Using indexing map[key] -> &V or &mut V
// Panics the current thread if the key is not found!
// Use only when absolutely sure the key exists.
// The Index trait implementation returns an immutable reference &V.
let alice_ref: &i32 = &scores["Alice"];
println!("Alice's score via index: {}", alice_ref);

// let charlie_ref = &scores["Charlie"]; // This would panic the current thread

// Checking for key existence
if scores.contains_key("Bob") {
    println!("Bob is in the map.");
}
}

Unlike Vec, HashMap indexing (map[key]) does not return the value directly even if V is Copy. It always returns a reference (&V for immutable indexing, &mut V for mutable indexing). Dereferencing this reference (*map[key]) will copy the value if V is Copy. The panic occurs if the key is absent, preventing access to non-existent data.

18.4.4 Updating and Removing Values

Overwriting with insert: If you insert a key that already exists, the old value is overwritten, and insert returns Some(old_value). If the key was new, it returns None.

#![allow(unused)]
fn main() {
use std::collections::HashMap;
let mut scores: HashMap<String, i32> = HashMap::new();
scores.insert(String::from("Alice"), 95);
let old_alice = scores.insert("Alice".to_string(), 100); // Update Alice's score
assert_eq!(old_alice, Some(95));
}

Conditional Insertion/Update with the entry API: The entry method is powerful for handling cases where you might need to insert a value only if the key doesn’t exist, or update an existing value.

#![allow(unused)]
fn main() {
use std::collections::HashMap;
let mut word_counts: HashMap<String, u32> = HashMap::new();
let text = "hello world hello";

for word in text.split_whitespace() {
    // entry(key) returns an Entry enum (Occupied or Vacant)
    // or_insert(default_value) gets a mutable ref to the existing value
    // or inserts the default and returns a mutable ref to the new value.
    let count: &mut u32 = word_counts.entry(word.to_string()).or_insert(0);
    *count += 1; // Dereference the mutable reference to increment the count
}
// word_counts is now {"hello": 2, "world": 1} (order may vary)
println!("{:?}", word_counts);
}

The entry API has other useful methods like or_default() (uses Default::default() if vacant) and and_modify() (runs a closure to update if occupied).

Removing with remove: remove(&key) removes a key-value pair if the key exists, returning Some(value) (the owned value). If the key doesn’t exist, it returns None.

#![allow(unused)]
fn main() {
use std::collections::HashMap;
let mut scores: HashMap<String, i32> = HashMap::new();
scores.insert(String::from("Alice"), 95);
if let Some(score) = scores.remove("Alice") {
    println!("Removed Alice with score: {}", score); // score is the owned i32
}
}

18.4.5 Iteration

You can iterate over keys, values, or key-value pairs. Remember that the iteration order is not guaranteed.

#![allow(unused)]
fn main() {
use std::collections::HashMap;
let scores: HashMap<String, i32> = HashMap::from([
     ("Alice".to_string(), 95), ("Bob".to_string(), 88)
]);

// Iterate over key-value pairs (yields immutable references: (&K, &V))
println!("Scores:");
for (name, score) in &scores { // or scores.iter()
    println!("- {}: {}", name, score);
}

// Iterate over keys only (yields immutable references: &K)
println!("\nNames:");
for name in scores.keys() {
    println!("- {}", name);
}

// Iterate over values only (yields immutable references: &V)
println!("\nValues:");
for score in scores.values() {
    println!("- {}", score);
}

// Iterate with mutable references to values:
// let mut mutable_scores = scores; // Need mutable binding
// for score in mutable_scores.values_mut() { *score += 1; }
// for (key, value) in mutable_scores.iter_mut() { *value += 1; }
}

18.4.6 Internal Details: Hashing, Collisions, and Resizing

Internally, HashMap typically uses an array (often a Vec) of buckets or slots. When inserting a key-value pair:

The key is hashed to produce an integer.
This hash is used to calculate an index (a bucket or slot) into the internal array.
If the calculated slot is empty, the key-value pair (or information pointing to them) is stored there.
If the calculated slot is already occupied by a different key (a hash collision, where multiple keys hash to the same initial slot index), the map must employ a collision resolution strategy. The two primary approaches are:
- Separate Chaining: Each slot in the array acts as the head of a secondary collection (like a linked list) that stores all the key-value pairs which hashed to that initial slot. Operations involve searching this secondary collection.
- Open Addressing: If the target slot is occupied, the map probes subsequent slots within the main array itself according to a defined sequence (e.g., linear probing, quadratic probing, double hashing) until an empty slot is found (for insertion), the key is found (for lookup), or it’s determined the key is absent.

Rust’s std::collections::HashMap uses a highly optimized implementation of open addressing (specifically, a variation of Robin Hood probing adapted from the hashbrown crate). This strategy tends to have better cache performance compared to separate chaining because elements are stored directly within the contiguous array, reducing pointer indirections.

To maintain efficient average O(1) lookups, the HashMap monitors its load factor (number of elements / number of slots). When the load factor exceeds a certain threshold (meaning the table is becoming too full, increasing collision probability), the map allocates a larger array of slots (resizing) and re-inserts all existing elements into the new, larger table using their hash values. This resizing operation takes O(n) time but happens infrequently enough that the average (amortized) insertion time remains O(1).

18.4.7 Summary: `HashMap` vs. C Hash Tables

Implementing hash tables manually in C requires significant effort: choosing or implementing a suitable hash function, designing an effective collision resolution strategy (like chaining or open addressing), writing the logic for resizing the table, and managing memory for the table structure, keys, and values. Using a third-party C library can help, but integration and ensuring type safety and memory safety still rely heavily on the programmer.

Rust’s HashMap<K, V> provides:

A ready-to-use, performant, and robust implementation.
Automatic memory management for keys, values, and the internal table structure, preventing leaks.
Compile-time type safety enforced by generics (K, V).
A secure default hashing algorithm (SipHash 1-3) resistant to HashDoS attacks.
Integration with Rust’s ownership and borrowing system, preventing dangling pointers to keys or values.
Average O(1) performance for insertion, lookup, and removal, comparable to well-tuned C implementations but with built-in safety guarantees.

18.5 Other Standard Collection Types

Beyond the three main types, Rust’s standard library (std::collections) offers several other useful collections:

BTreeMap<K, V>: A map implemented using a B-Tree. Unlike HashMap, BTreeMap stores keys in sorted order. Operations (insert, get, remove) have O(log n) time complexity. It’s useful when you need to iterate over key-value pairs in sorted key order or perform range queries. Keys must implement the Ord trait (total ordering) in addition to Eq.
HashSet<T> / BTreeSet<T>: Set collections that store unique elements T.
- HashSet<T> uses hashing (like HashMap) for average O(1) insertion, removal, and membership checking (contains). Elements must implement Eq and Hash. Order is arbitrary.
- BTreeSet<T> uses a B-Tree (like BTreeMap) for O(log n) operations and stores elements in sorted order. Elements must implement Ord and Eq. Both are useful for efficiently checking if an item exists in a collection, removing duplicates, or performing set operations (union, intersection, difference).
VecDeque<T>: A double-ended queue (deque) implemented using a growable ring buffer. It provides efficient amortized O(1) push and pop operations at both the front and the back of the queue. Accessing elements by index is possible but can be O(n) in the worst case if the element is far from the ends in the ring buffer layout. Useful for implementing FIFO queues, LIFO stacks (though Vec is often simpler for stacks), or algorithms needing efficient access to both ends.
LinkedList<T>: A classic doubly-linked list. It offers O(1) insertion and removal if you already have a cursor pointing to the node before or after the desired location. It also allows efficient splitting and merging of lists. However, accessing an element by index requires traversing the list (O(n)), and its node-based allocation pattern generally leads to poorer cache performance compared to Vec or VecDeque. In idiomatic Rust, LinkedList is used less frequently than Vec or VecDeque, reserved for specific algorithms where its unique properties are genuinely advantageous.
BinaryHeap<T>: A max-heap implementation (priority queue). It allows efficiently pushing elements (O(log n)) and popping (O(log n)) the largest element according to its Ord implementation. Useful for algorithms like Dijkstra’s or A*, or anytime you need quick access to the maximum item in a collection. Elements must implement Ord and Eq.

All these standard collections manage their memory automatically and uphold Rust’s safety guarantees through the ownership and borrowing system.

18.6 Performance Characteristics Summary

Choosing the right collection type often involves considering the time complexity of common operations. The table below summarizes typical complexities (average or amortized where applicable):

Collection	Access (Index/Key)	Insert (End/Any)	Remove (End/Any)	Iteration Order	Key Notes
`Vec<T>`	`O(1)` / N/A	`O(1)`* / `O(n)`	`O(1)` / `O(n)`	Insertion	Contiguous memory, cache-friendly. *Amortized.
`String`	N/A (Byte Slice)	`O(1)`* / N/A	N/A	UTF-8 Bytes	`Vec<u8>` + UTF-8 guarantee. Append is `O(1)`*.
`HashMap<K, V>`	`O(1)`**	`O(1)`**	`O(1)`**	Arbitrary	Requires `Hash`+`Eq` keys. **Average case.
`BTreeMap<K, V>`	`O(log n)`	`O(log n)`	`O(log n)`	Sorted by Key	Requires `Ord`+`Eq` keys. Slower than `HashMap`.
`HashSet<T>`	`O(1)`** (contains)	`O(1)`**	`O(1)`**	Arbitrary	Unique elements, hashed. **Average case.
`BTreeSet<T>`	`O(log n)` (contains)	`O(log n)`	`O(log n)`	Sorted	Unique elements, ordered. Requires `Ord`+`Eq`.
`VecDeque<T>`	`O(1)` (ends) / `O(n)`	`O(1)`* (ends) / `O(n)`	`O(1)`* (ends) / `O(n)`	Insertion	Ring buffer. *Amortized `O(1)` at ends.
`LinkedList<T>`	`O(n)`	`O(1)`***	`O(1)`***	Insertion	Poor cache locality. ***Requires known node/cursor.
`BinaryHeap<T>`	`O(1)` (peek)	`O(log n)`	`O(log n)`	N/A	`O(log n)` push/pop. Useful for priority queues.

Notes: * Amortized O(1): The operation is very fast on average, but occasional calls might be slower (O(n)) due to internal resizing. ** Average case O(1): Assumes a good hash function and few collisions. Worst-case can be O(n). *** O(1) if you already have direct access (e.g., a cursor) to the node or its neighbor involved in the operation. Finding the node first is O(n).

18.7 Selecting the Appropriate Collection

Here’s a quick guide based on common needs:

Need a growable list of items accessed primarily by an integer index? -> Use Vec<T>. This is the most common general-purpose sequence collection.
Need to store and manipulate growable text data? -> Use String (owned) and work with &str (borrowed slices).
Need to associate unique keys with values for fast lookups, and order doesn’t matter? -> Use HashMap<K, V>. Requires keys to be hashable (Hash + Eq).
Need key-value storage where keys must be kept in sorted order, or you need to find items within a range of keys? -> Use BTreeMap<K, V>. Requires keys to be orderable (Ord + Eq). Slower than HashMap for individual lookups.
Need to store unique items efficiently and quickly check if an item is present (order doesn’t matter)? -> Use HashSet<T>. Requires elements to be hashable (Hash + Eq).
Need to store unique items in sorted order? -> Use BTreeSet<T>. Requires elements to be orderable (Ord + Eq).
Need a queue (First-In, First-Out) or stack (Last-In, First-Out) with efficient additions/removals at both ends? -> Use VecDeque<T>.
Need a priority queue (always retrieving the largest/smallest item)? -> Use BinaryHeap<T>. Requires elements to be orderable (Ord + Eq).
Need efficient insertion/removal in the middle of a sequence at a known location, and don’t need fast random access by index? -> LinkedList<T> might be suitable, but carefully consider if Vec<T> (with O(n) insertion/removal) or VecDeque<T> might still be faster overall due to better cache performance, especially for moderate n. Benchmark if performance is critical.

When in doubt for sequences, start with Vec<T>. For key-value lookups, start with HashMap<K, V>. Choose other collections when their specific properties (ordering, double-ended access, uniqueness) are required.

18.8 Summary

Rust’s standard library provides a versatile suite of collection types, with Vec<T>, String, and HashMap<K, V> being the most commonly used. These types offer essential capabilities for managing dynamic data whose size isn’t known at compile time.

For C programmers, the paramount advantage is that Rust collections manage their own memory safely and automatically, governed by the ownership and borrowing system. This design fundamentally eliminates entire categories of memory management errors prevalent in C, such as memory leaks, use-after-free, double frees, and buffer overflows associated with manual malloc/realloc/free usage.

These collections provide not only safety but also efficiency, often matching the performance of carefully tuned C implementations while drastically reducing the risk of memory corruption bugs. By understanding the characteristics, performance trade-offs, and typical use cases of Rust’s collections, you can write more expressive, robust, and maintainable code that effectively handles dynamic data, liberating you from the considerable burden and risks of manual memory management in C.

Keyboard shortcuts

Rust for C-Programmers