Rust Data Structures:
Vec vs. HashMap vs. BTreeMap

Last updated: April 13, 2025

1. Introduction: Choosing the Right Collection

Rust's standard library (std::collections) provides several versatile and efficient collection types for storing groups of data. Among the most commonly used are:

• Vec<T>: A contiguous, growable array type (a vector).
• HashMap<K, V>: A map implemented using a hash table.
• BTreeMap<K, V>: A map implemented using a B-Tree.

Choosing the right collection for a specific task depends heavily on how you intend to access and modify the data. This guide compares these three fundamental collection types, focusing on their underlying structure, performance characteristics, and typical use cases.

Basic familiarity with Rust syntax is assumed. If needed, review our Getting Started with Rust guide.

2. Vec<T>: The Growable Vector

Vec<T>, pronounced 'vector', is Rust's dynamic array type. It stores multiple values of the same type T in a contiguous block of memory on the heap.

2.1 Characteristics

• Contiguous Memory: Elements are stored next to each other in memory, which can be beneficial for CPU cache performance.
• Growable: Can increase or decrease in size dynamically at runtime.
• Ordered: Maintains the insertion order of elements.
• Indexed Access: Elements can be accessed directly by their integer index (starting from 0).

2.2 Performance (Big O Notation)

• Access by Index (vec[i]): O(1) - Very fast.
• Adding to End (push): O(1) amortized - Usually very fast, but occasionally requires reallocating memory and copying elements (O(N)) if capacity is exceeded.
• Removing from End (pop): O(1) - Very fast.
• Inserting/Removing at Arbitrary Index: O(N) - Slow, as elements after the insertion/deletion point need to be shifted.
• Searching (linear scan): O(N) - Slow for unsorted data.

2.3 When to Use Vec

• When you need a list of items of the same type.
• When you frequently need to access elements by their position (index).
• When you mostly add or remove elements at the end of the list.
• When the order of elements matters.

2.4 Example

fn main() {
    // Create an empty vector that holds i32 values
    let mut numbers: Vec = Vec::new();

    // Add elements to the end
    numbers.push(10);
    numbers.push(20);
    numbers.push(30);

    // Access by index (panics if out of bounds)
    let first = numbers[0]; // first is 10
    println!("First element: {}", first);

    // Safe access using get() which returns an Option<&T>
    match numbers.get(1) {
        Some(second) => println!("Second element: {}", second), // second is 20
        None => println!("No second element."),
    }

    // Iterate over elements
    println!("Vector elements:");
    for num in &numbers { // Use immutable borrow for iteration
        println!("- {}", num);
    }

    // Remove the last element
    let last = numbers.pop(); // last is Some(30)
    println!("Popped element: {:?}", last);
    println!("Vector after pop: {:?}", numbers); // [10, 20]
}

3. HashMap<K, V>: The Hash Map

HashMap<K, V> stores key-value pairs. It uses a hashing function to determine where to place each key-value pair in memory, allowing for very fast average lookup times.

3.1 Characteristics

• Key-Value Store: Associates unique keys of type K with values of type V.
• Unordered: The order in which key-value pairs are stored or iterated over is not guaranteed and can change.
• Hashing: Keys must implement the Eq and Hash traits. Rust provides implementations for most standard types (integers, strings, etc.).
• Fast Lookups: Designed for quick retrieval of a value when you know its key.

3.2 Performance (Big O Notation)

• Insertion: O(1) average, O(N) worst case (due to hash collisions or resizing).
• Deletion: O(1) average, O(N) worst case.
• Lookup by Key: O(1) average, O(N) worst case.

The worst-case scenarios are rare with good hashing functions.

3.3 When to Use HashMap

• When you need to associate data (values) with unique identifiers (keys).
• When you need very fast lookups, insertions, and deletions based on a key.
• When the order of elements does not matter.
• Examples: Caching, frequency counting, storing user data by user ID.

3.4 Example

use std::collections::HashMap;

fn main() {
    // Create an empty HashMap
    let mut scores = HashMap::new();

    // Insert key-value pairs
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    // Overwrite a value
    scores.insert(String::from("Blue"), 25); // Overwrites the previous value for "Blue"

    // Use entry API to insert only if key doesn't exist
    scores.entry(String::from("Red")).or_insert(30);
    scores.entry(String::from("Blue")).or_insert(100); // Does nothing, "Blue" exists

    // Access value by key using get() (returns Option<&V>)
    let team_name = String::from("Blue");
    match scores.get(&team_name) { // Use a reference to the key for lookup
        Some(score) => println!("Score for {}: {}", team_name, score), // Score is 25
        None => println!("Team {} not found.", team_name),
    }

    // Iterate over key-value pairs (order is arbitrary)
    println!("All scores:");
    for (key, value) in &scores {
        println!("{}: {}", key, value);
    }

    // Remove a key-value pair
    scores.remove("Yellow");
    println!("Scores after removing Yellow: {:?}", scores);
}

4. BTreeMap<K, V>: The Ordered Map

BTreeMap<K, V> also stores key-value pairs, but it uses a B-Tree data structure internally. This keeps the keys sorted at all times.

4.1 Characteristics

• Key-Value Store: Associates unique keys of type K with values of type V.
• Ordered by Key: Keys are always stored and iterated over in sorted order.
• Requirements: Keys must implement the Ord trait (which implies Eq and PartialOrd).
• Logarithmic Performance: Operations are generally slower than HashMap's average case but offer better worst-case performance guarantees.

4.2 Performance (Big O Notation)

• Insertion: O(log N)
• Deletion: O(log N)
• Lookup by Key: O(log N)

Performance is more consistent than HashMap as it doesn't rely on hashing and avoids worst-case O(N) scenarios.

4.3 When to Use BTreeMap

• When you need a key-value map AND require the keys to be sorted.
• When you need to iterate over a range of keys.
• When you need predictable O(log N) performance for all operations (avoiding potential O(N) worst case of HashMap).
• When your keys don't implement Hash but do implement Ord.

4.4 Example

use std::collections::BTreeMap;

fn main() {
    // Create an empty BTreeMap
    let mut ordered_scores = BTreeMap::new();

    // Insert key-value pairs
    ordered_scores.insert(String::from("Red"), 30);
    ordered_scores.insert(String::from("Blue"), 10);
    ordered_scores.insert(String::from("Green"), 50);

    // Access value by key
    if let Some(score) = ordered_scores.get("Blue") {
        println!("Blue's score: {}", score); // 10
    }

    // Iterate over key-value pairs (GUARANTEED sorted by key)
    println!("All scores (sorted by key):");
    for (key, value) in &ordered_scores {
        println!("{}: {}", key, value); // Output: Blue: 10, Green: 50, Red: 30
    }

    // Range iteration (example requires nightly or specific features usually)
    // Basic BTreeMap iteration naturally yields sorted keys.
}

5. Comparison Summary Table

6. Conclusion

Rust's standard library offers powerful and efficient collections for common programming tasks. Choosing between Vec, HashMap, and BTreeMap depends primarily on how you need to store and access your data:

• Use Vec<T> for ordered sequences accessed primarily by index or appended/popped at the end.
• Use HashMap<K, V> for the fastest average-case key-based lookups when order doesn't matter.
• Use BTreeMap<K, V> when you need key-based lookups *and* require the keys to be stored and iterated in sorted order, or when predictable O(log N) performance is necessary.

Understanding the performance trade-offs associated with each data structure allows you to write more efficient and appropriate Rust code.

7. Additional Resources

Related Articles

• Getting Started with Rust
• Rust Ownership and Borrowing Explained

External Resources

• Standard Library Documentation: Vec<T>
• Standard Library Documentation: HashMap<K, V>
• Standard Library Documentation: BTreeMap<K, V>
• The Rust Book: Chapter 8 - Common Collections