Rust - Hash Maps (HashMap)

Overview

Estimated time: 45–65 minutes

Master Rust's HashMap<K, V> and BTreeMap<K, V> for efficient key-value storage. Learn creation, manipulation, iteration patterns, and the powerful entry API for complex operations.

Learning Objectives

• Create and populate hash maps using different methods
• Access, insert, and remove key-value pairs safely
• Use the entry API for advanced insertion patterns
• Understand HashMap vs BTreeMap trade-offs
• Apply hash maps to solve real-world problems

Prerequisites

• Rust - Ownership Basics
• Rust - Enums (for Option)
• Rust - Loops

Creating Hash Maps

Basic Creation

use std::collections::HashMap;

fn main() {
    // Empty HashMap
    let mut scores: HashMap<String, i32> = HashMap::new();
    println!("Empty map: {:?}", scores);
    
    // Insert some values
    scores.insert("Alice".to_string(), 95);
    scores.insert("Bob".to_string(), 87);
    scores.insert("Carol".to_string(), 92);
    
    println!("Scores: {:?}", scores);
}

Expected output:

Empty map: {}
Scores: {"Alice": 95, "Carol": 92, "Bob": 87}

Creating from Iterators

use std::collections::HashMap;

fn main() {
    // From vector of tuples
    let data = vec![
        ("apple", 5),
        ("banana", 3),
        ("orange", 8),
    ];
    
    let fruit_count: HashMap<&str, i32> = data.into_iter().collect();
    println!("Fruit count: {:?}", fruit_count);
    
    // From two vectors
    let keys = vec!["red", "green", "blue"];
    let values = vec![255, 128, 64];
    
    let colors: HashMap<&str, i32> = keys
        .into_iter()
        .zip(values.into_iter())
        .collect();
    
    println!("Colors: {:?}", colors);
}

Expected output:

Fruit count: {"apple": 5, "orange": 8, "banana": 3}
Colors: {"red": 255, "green": 128, "blue": 64}

Accessing Values

Get Method and Index Access

use std::collections::HashMap;

fn main() {
    let mut book_ratings = HashMap::new();
    book_ratings.insert("1984", 9);
    book_ratings.insert("To Kill a Mockingbird", 10);
    book_ratings.insert("The Catcher in the Rye", 7);
    
    // Safe access with get()
    match book_ratings.get("1984") {
        Some(rating) => println!("1984 rating: {}", rating),
        None => println!("1984 not found"),
    }
    
    // Using get with unwrap_or
    let rating = book_ratings.get("Unknown Book").unwrap_or(&0);
    println!("Unknown book rating (default): {}", rating);
    
    // Index access (will panic if key doesn't exist)
    println!("To Kill a Mockingbird: {}", book_ratings["To Kill a Mockingbird"]);
    
    // Check if key exists
    if book_ratings.contains_key("1984") {
        println!("We have a rating for 1984");
    }
    
    // Get all keys and values
    println!("All books: {:?}", book_ratings.keys().collect::<Vec<_>>());
    println!("All ratings: {:?}", book_ratings.values().collect::<Vec<_>>());
}

Expected output:

1984 rating: 9
Unknown book rating (default): 0
To Kill a Mockingbird: 10
We have a rating for 1984
All books: ["The Catcher in the Rye", "To Kill a Mockingbird", "1984"]
All ratings: [7, 10, 9]

Modifying Hash Maps

Insert and Update

use std::collections::HashMap;

fn main() {
    let mut inventory = HashMap::new();
    
    // Insert new items
    inventory.insert("apples", 50);
    inventory.insert("bananas", 30);
    inventory.insert("oranges", 25);
    
    println!("Initial inventory: {:?}", inventory);
    
    // Update existing value
    inventory.insert("apples", 45); // Overwrites previous value
    println!("After selling apples: {:?}", inventory);
    
    // Insert only if key doesn't exist
    inventory.entry("pears").or_insert(20);
    inventory.entry("apples").or_insert(100); // Won't change existing value
    
    println!("After conditional inserts: {:?}", inventory);
    
    // Remove items
    if let Some(removed) = inventory.remove("bananas") {
        println!("Removed {} bananas", removed);
    }
    
    println!("Final inventory: {:?}", inventory);
}

Expected output:

Initial inventory: {"apples": 50, "oranges": 25, "bananas": 30}
After selling apples: {"apples": 45, "oranges": 25, "bananas": 30}
After conditional inserts: {"apples": 45, "oranges": 25, "bananas": 30, "pears": 20}
Removed 30 bananas
Final inventory: {"apples": 45, "oranges": 25, "pears": 20}

Entry API - Advanced Operations

Or Insert and Or Insert With

use std::collections::HashMap;

fn main() {
    let mut word_count = HashMap::new();
    let text = "hello world hello rust world";
    
    // Count words using entry API
    for word in text.split_whitespace() {
        let count = word_count.entry(word).or_insert(0);
        *count += 1;
    }
    
    println!("Word count: {:?}", word_count);
    
    // Using or_insert_with for expensive operations
    let mut cache = HashMap::new();
    
    // This closure only runs if the key doesn't exist
    let value = cache.entry("expensive_calculation")
        .or_insert_with(|| {
            println!("Performing expensive calculation...");
            42 // Some expensive result
        });
    
    println!("Cached value: {}", value);
    
    // Second access won't run the closure
    let value2 = cache.entry("expensive_calculation")
        .or_insert_with(|| {
            println!("This won't print");
            999
        });
    
    println!("Cached value (second access): {}", value2);
}

Expected output:

Word count: {"hello": 2, "world": 2, "rust": 1}
Performing expensive calculation...
Cached value: 42
Cached value (second access): 42

Entry API for Complex Updates

use std::collections::HashMap;

fn main() {
    let mut student_grades: HashMap<String, Vec<i32>> = HashMap::new();
    
    // Add grades using entry API
    let grades = vec![
        ("Alice", 95),
        ("Bob", 87),
        ("Alice", 92),
        ("Carol", 89),
        ("Bob", 91),
        ("Alice", 88),
    ];
    
    for (name, grade) in grades {
        student_grades
            .entry(name.to_string())
            .or_insert_with(Vec::new)
            .push(grade);
    }
    
    println!("All grades: {:?}", student_grades);
    
    // Calculate averages
    for (name, grades) in &student_grades {
        let average: f64 = grades.iter().sum::<i32>() as f64 / grades.len() as f64;
        println!("{}: {:.1} average", name, average);
    }
    
    // Modify existing entry
    if let Some(alice_grades) = student_grades.get_mut("Alice") {
        alice_grades.push(97); // Add another grade
    }
    
    println!("Alice's updated grades: {:?}", 
        student_grades.get("Alice").unwrap());
}

Expected output:

All grades: {"Alice": [95, 92, 88], "Carol": [89], "Bob": [87, 91]}
Alice: 91.7 average
Carol: 89.0 average
Bob: 89.0 average
Alice's updated grades: [95, 92, 88, 97]

Iteration Patterns

Different Ways to Iterate

use std::collections::HashMap;

fn main() {
    let mut temperatures = HashMap::new();
    temperatures.insert("New York", 75);
    temperatures.insert("London", 62);
    temperatures.insert("Tokyo", 78);
    temperatures.insert("Sydney", 68);
    
    // Iterate over key-value pairs
    println!("City temperatures:");
    for (city, temp) in &temperatures {
        println!("  {}: {}°F", city, temp);
    }
    
    // Iterate over keys only
    println!("\nCities:");
    for city in temperatures.keys() {
        println!("  {}", city);
    }
    
    // Iterate over values only
    println!("\nTemperatures:");
    for temp in temperatures.values() {
        println!("  {}°F", temp);
    }
    
    // Mutable iteration over values
    println!("\nConverting to Celsius:");
    for (city, temp) in temperatures.iter_mut() {
        *temp = (*temp - 32) * 5 / 9; // Convert F to C
        println!("  {}: {}°C", city, temp);
    }
    
    // Consuming iteration
    let owned_temps: Vec<(String, i32)> = temperatures
        .into_iter()
        .map(|(city, temp)| (city.to_uppercase(), temp))
        .collect();
    
    println!("\nOwned temperatures: {:?}", owned_temps);
    // temperatures is no longer accessible here
}

Expected output:

City temperatures:
  New York: 75°F
  Tokyo: 78°F
  Sydney: 68°F
  London: 62°F

Cities:
  New York
  Tokyo
  Sydney
  London

Temperatures:
  75°F
  78°F
  68°F
  62°F

Converting to Celsius:
  New York: 23°C
  Tokyo: 25°C
  Sydney: 20°C
  London: 16°C

Owned temperatures: [("NEW YORK", 23), ("TOKYO", 25), ("SYDNEY", 20), ("LONDON", 16)]

HashMap vs BTreeMap

Comparing Both Types

use std::collections::{HashMap, BTreeMap};

fn main() {
    // HashMap - unordered, O(1) average access
    let mut hash_map = HashMap::new();
    hash_map.insert(3, "three");
    hash_map.insert(1, "one");
    hash_map.insert(2, "two");
    
    println!("HashMap (random order):");
    for (key, value) in &hash_map {
        println!("  {}: {}", key, value);
    }
    
    // BTreeMap - ordered, O(log n) access
    let mut btree_map = BTreeMap::new();
    btree_map.insert(3, "three");
    btree_map.insert(1, "one");
    btree_map.insert(2, "two");
    
    println!("\nBTreeMap (sorted order):");
    for (key, value) in &btree_map {
        println!("  {}: {}", key, value);
    }
    
    // BTreeMap supports range queries
    println!("\nBTreeMap range 1..=2:");
    for (key, value) in btree_map.range(1..=2) {
        println!("  {}: {}", key, value);
    }
}

Expected output:

HashMap (random order):
  2: two
  3: three
  1: one

BTreeMap (sorted order):
  1: one
  2: two
  3: three

BTreeMap range 1..=2:
  1: one
  2: two

Practical Examples

Contact Manager

use std::collections::HashMap;

#[derive(Debug, Clone)]
struct Contact {
    name: String,
    email: String,
    phone: String,
}

fn main() {
    let mut contacts: HashMap<String, Contact> = HashMap::new();
    
    // Add contacts (using name as key)
    let alice = Contact {
        name: "Alice Johnson".to_string(),
        email: "[email protected]".to_string(),
        phone: "555-0123".to_string(),
    };
    
    let bob = Contact {
        name: "Bob Smith".to_string(),
        email: "[email protected]".to_string(),
        phone: "555-0456".to_string(),
    };
    
    contacts.insert(alice.name.clone(), alice);
    contacts.insert(bob.name.clone(), bob);
    
    // Look up contact
    if let Some(contact) = contacts.get("Alice Johnson") {
        println!("Found contact: {:?}", contact);
    }
    
    // Update contact
    contacts.entry("Alice Johnson".to_string())
        .and_modify(|contact| contact.phone = "555-9999".to_string());
    
    // List all contacts
    println!("\nAll contacts:");
    for contact in contacts.values() {
        println!("  {} - {} - {}", contact.name, contact.email, contact.phone);
    }
    
    // Remove contact
    if let Some(removed) = contacts.remove("Bob Smith") {
        println!("\nRemoved: {}", removed.name);
    }
    
    println!("Remaining contacts: {}", contacts.len());
}

Expected output:

Found contact: Contact { name: "Alice Johnson", email: "[email protected]", phone: "555-0123" }

All contacts:
  Alice Johnson - [email protected] - 555-9999
  Bob Smith - [email protected] - 555-0456

Removed: Bob Smith
Remaining contacts: 1

Frequency Counter

use std::collections::HashMap;

fn main() {
    let text = "the quick brown fox jumps over the lazy dog the fox is quick";
    
    // Count word frequencies
    let mut word_freq: HashMap<&str, usize> = HashMap::new();
    
    for word in text.split_whitespace() {
        *word_freq.entry(word).or_insert(0) += 1;
    }
    
    // Convert to vector and sort by frequency
    let mut freq_vec: Vec<(&str, usize)> = word_freq.iter()
        .map(|(&word, &count)| (word, count))
        .collect();
    
    freq_vec.sort_by(|a, b| b.1.cmp(&a.1)); // Sort by count descending
    
    println!("Word frequencies (most common first):");
    for (word, count) in freq_vec {
        println!("  '{}': {} times", word, count);
    }
    
    // Find most common word
    if let Some((&most_common, &max_count)) = word_freq.iter()
        .max_by_key(|(_, &count)| count) {
        println!("\nMost common word: '{}' appears {} times", 
            most_common, max_count);
    }
    
    // Count unique words
    println!("Total unique words: {}", word_freq.len());
}

Expected output:

Word frequencies (most common first):
  'the': 3 times
  'fox': 2 times
  'quick': 2 times
  'brown': 1 times
  'jumps': 1 times
  'over': 1 times
  'lazy': 1 times
  'dog': 1 times
  'is': 1 times

Most common word: 'the' appears 3 times
Total unique words: 9

Common Pitfalls

Ownership and Borrowing

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    let key = String::from("name");
    let value = String::from("Alice");
    
    // This moves both key and value into the map
    map.insert(key, value);
    
    // These would not compile - key and value are moved
    // println!("Key: {}", key);
    // println!("Value: {}", value);
    
    // Safe approach - clone if needed
    let key2 = String::from("age");
    let value2 = String::from("25");
    
    map.insert(key2.clone(), value2.clone());
    println!("Still have access: {} = {}", key2, value2);
    
    // Or use references for lookup
    if let Some(name) = map.get("name") {
        println!("Found name: {}", name);
    }
}

Hash vs Equality

use std::collections::HashMap;

// Custom type that implements Hash and Eq
#[derive(Hash, Eq, PartialEq, Debug)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut point_map = HashMap::new();
    
    let p1 = Point { x: 1, y: 2 };
    let p2 = Point { x: 1, y: 2 }; // Same values as p1
    
    point_map.insert(p1, "origin area");
    
    // p2 is equal to p1, so this will overwrite
    point_map.insert(p2, "updated");
    
    println!("Point map: {:?}", point_map);
    println!("Size: {}", point_map.len()); // Still 1 entry
}

Performance Considerations

Capacity and Pre-allocation

use std::collections::HashMap;

fn main() {
    // Pre-allocate for known size
    let mut efficient_map = HashMap::with_capacity(1000);
    
    // This won't trigger reallocations until we exceed capacity
    for i in 0..500 {
        efficient_map.insert(i, i * 2);
    }
    
    println!("Efficient map size: {}", efficient_map.len());
    
    // Reserve additional capacity
    efficient_map.reserve(500);
    
    for i in 500..1000 {
        efficient_map.insert(i, i * 2);
    }
    
    println!("Final size: {}", efficient_map.len());
}

Checks for Understanding

Question 1: Entry API

What's the difference between map.insert(key, value) and map.entry(key).or_insert(value)?

Question 2: When to Use BTreeMap

When would you choose BTreeMap over HashMap?

Question 3: Memory Usage

Why might pre-allocating capacity with HashMap::with_capacity(n) improve performance?