Vec, HashMap & Friends

Rust's standard library provides a small set of collections that cover the vast majority of use cases. Unlike languages with dozens of collection classes, Rust gives you a handful of well-designed, well-optimized types. Choose the right one and it will serve you well. Choose wrong and you will pay for it in performance or ergonomics.

Vec: The Workhorse

Vec<T> is a growable, heap-allocated array. It is the most commonly used collection in Rust and the default choice when you need an ordered sequence.

fn main() {
    // Creating vectors
    let mut numbers = Vec::new();
    numbers.push(1);
    numbers.push(2);
    numbers.push(3);

    let names = vec!["Alice", "Bob", "Charlie"]; // vec! macro

    let zeros = vec![0u8; 100]; // 100 zeros

    // Accessing elements
    println!("First: {}", numbers[0]);          // panics if out of bounds
    println!("Safe: {:?}", numbers.get(10));     // returns None

    // Iterating
    for name in &names {
        println!("Hello, {}", name);
    }

    // Modifying
    numbers.push(4);
    numbers.retain(|&x| x > 1);  // remove elements that don't match
    println!("After retain: {:?}", numbers);

    println!("Zeros length: {}", zeros.len());
}

First: 1
Safe: None
Hello, Alice
Hello, Bob
Hello, Charlie
After retain: [2, 3, 4]
Zeros length: 100

Key Vec operations and their costs:

When you know the size in advance, use Vec::with_capacity to avoid reallocations:

fn collect_even_numbers(limit: usize) -> Vec<usize> {
    let mut result = Vec::with_capacity(limit / 2);
    for i in 0..limit {
        if i % 2 == 0 {
            result.push(i);
        }
    }
    result
}

fn main() {
    let evens = collect_even_numbers(10);
    println!("{:?}", evens);
}

[0, 2, 4, 6, 8]

HashMap<K, V>: Key-Value Storage

HashMap provides O(1) average-case lookups by key. Use it when you need to associate values with unique keys.

use std::collections::HashMap;

fn word_count(text: &str) -> HashMap<String, usize> {
    let mut counts = HashMap::new();
    for word in text.split_whitespace() {
        let word = word.to_lowercase();
        *counts.entry(word).or_insert(0) += 1;
    }
    counts
}

fn main() {
    let mut scores: HashMap<String, Vec<u32>> = HashMap::new();

    scores.entry("Alice".to_string()).or_default().push(95);
    scores.entry("Alice".to_string()).or_default().push(87);
    scores.entry("Bob".to_string()).or_default().push(72);

    for (name, grades) in &scores {
        let avg: f64 = grades.iter().sum::<u32>() as f64 / grades.len() as f64;
        println!("{}: {:?} (avg: {:.1})", name, grades, avg);
    }

    println!();

    let text = "the cat sat on the mat the cat";
    let counts = word_count(text);
    let mut sorted: Vec<_> = counts.iter().collect();
    sorted.sort_by(|a, b| b.1.cmp(a.1));
    for (word, count) in sorted {
        println!("{}: {}", word, count);
    }
}

Alice: [95, 87] (avg: 91.0)
Bob: [72] (avg: 72.0)

the: 3
cat: 2
sat: 1
on: 1
mat: 1

The entry API is the idiomatic way to handle "insert if missing, update if present." It avoids double lookups.

HashSet: Unique Values

HashSet is a HashMap without values. Use it when you need to track unique elements or perform set operations.

use std::collections::HashSet;

fn main() {
    let mut seen = HashSet::new();

    let items = vec!["apple", "banana", "apple", "cherry", "banana", "date"];
    let unique: Vec<_> = items.into_iter().filter(|item| seen.insert(*item)).collect();
    println!("Unique (order preserved): {:?}", unique);

    // Set operations
    let backend: HashSet<&str> = ["rust", "go", "python", "java"].into();
    let frontend: HashSet<&str> = ["javascript", "typescript", "rust", "python"].into();

    let both: HashSet<_> = backend.intersection(&frontend).collect();
    let only_backend: HashSet<_> = backend.difference(&frontend).collect();
    let all: HashSet<_> = backend.union(&frontend).collect();

    println!("Both: {:?}", both);
    println!("Backend only: {:?}", only_backend);
    println!("All: {} languages", all.len());
}

Unique (order preserved): ["apple", "banana", "cherry", "date"]
Both: {"python", "rust"}
Backend only: {"go", "java"}
All: 6 languages

BTreeMap<K, V>: Sorted Keys

When you need keys in sorted order, BTreeMap provides O(log n) operations with ordered iteration:

use std::collections::BTreeMap;

fn main() {
    let mut events = BTreeMap::new();
    events.insert("2024-03-15", "Deploy v2.1");
    events.insert("2024-01-10", "Project kickoff");
    events.insert("2024-02-28", "Beta release");
    events.insert("2024-04-01", "GA release");

    // Iteration is always in key order
    println!("Timeline:");
    for (date, event) in &events {
        println!("  {}: {}", date, event);
    }

    // Range queries
    println!("\nQ1 events:");
    for (date, event) in events.range("2024-01-01"..="2024-03-31") {
        println!("  {}: {}", date, event);
    }
}

Timeline:
  2024-01-10: Project kickoff
  2024-02-28: Beta release
  2024-03-15: Deploy v2.1
  2024-04-01: GA release

Q1 events:
  2024-01-10: Project kickoff
  2024-02-28: Beta release
  2024-03-15: Deploy v2.1

Use BTreeMap when you need range queries or sorted output. Use HashMap when you just need fast lookups.

VecDeque: Double-Ended Queue

VecDeque supports efficient push and pop from both ends. Use it for queues, sliding windows, or when you need both FIFO and LIFO behavior.

use std::collections::VecDeque;

fn main() {
    let mut queue: VecDeque<String> = VecDeque::new();

    // Use as a FIFO queue
    queue.push_back("first".to_string());
    queue.push_back("second".to_string());
    queue.push_back("third".to_string());

    while let Some(item) = queue.pop_front() {
        println!("Processing: {}", item);
    }

    // Sliding window
    let data = [1, 5, 3, 8, 2, 9, 4, 7, 6];
    let window_size = 3;
    let mut window: VecDeque<i32> = VecDeque::with_capacity(window_size);

    println!("\nSliding window max (size {}):", window_size);
    for &val in &data {
        window.push_back(val);
        if window.len() > window_size {
            window.pop_front();
        }
        if window.len() == window_size {
            let max = window.iter().max().unwrap();
            println!("  {:?} -> max: {}", window, max);
        }
    }
}

Processing: first
Processing: second
Processing: third

Sliding window max (size 3):
  [1, 5, 3] -> max: 5
  [5, 3, 8] -> max: 8
  [3, 8, 2] -> max: 8
  [8, 2, 9] -> max: 9
  [2, 9, 4] -> max: 9
  [9, 4, 7] -> max: 9
  [4, 7, 6] -> max: 7

Choosing the Right Collection

When in doubt, start with Vec. It is the fastest collection for small to medium sizes due to cache locality. Switch to HashMap or BTreeMap only when you need key-based lookup.

Common Pitfalls

• Using HashMap for small collections. For fewer than ~20 elements, a Vec with linear search is often faster than a HashMap due to cache effects. Profile before optimizing.
• Forgetting that HashMap iteration order is non-deterministic. If you need deterministic order for tests or output, use BTreeMap or sort the entries.
• Not using entry for insert-or-update patterns. Writing if map.contains_key(&k) { ... } else { map.insert(k, v); } does two lookups. entry does one.
• Growing a Vec one element at a time without pre-allocating. If you know the size, use Vec::with_capacity. Each reallocation copies the entire buffer.
• Using Vec::remove(0) as a queue. This is O(n) because it shifts all elements. Use VecDeque for O(1) front removal.
• Not deriving Hash and Eq for custom types used as HashMap keys. The compiler will remind you, but design your key types with this in mind from the start.

Key Takeaways

• Vec<T> is the default collection. Start here unless you have a specific reason not to.
• HashMap<K, V> provides O(1) lookups. Use the entry API for insert-or-update patterns.
• HashSet<T> is for unique elements and set operations.
• BTreeMap<K, V> gives sorted iteration and range queries at the cost of O(log n) operations.
• VecDeque<T> is the right choice for queues and double-ended access.
• Choose based on your access pattern, not your instinct from other languages. Profile when it matters.