Rust HashMap: Key-Value Collections

Key Insights

HashMap provides O(1) average-case lookups through hash-based indexing, making it ideal for frequent key-based access patterns where insertion order doesn’t matter
The entry() API is the most idiomatic way to handle insert-or-update logic, eliminating redundant lookups and preventing common bugs
HashMap takes ownership of keys and values by default—use reference types or Clone strategically to avoid unnecessary copying or lifetime complexity

Introduction to HashMap

HashMap is Rust’s primary associative array implementation, storing key-value pairs with average O(1) lookup time. Unlike Vec, which requires O(n) scanning to find elements, HashMap uses hashing to directly compute storage locations.

Choose HashMap when you need fast lookups by arbitrary keys. Use Vec when you access elements by index or need ordered iteration. Consider BTreeMap when you need sorted keys or deterministic iteration order.

use std::collections::HashMap;
use std::time::Instant;

fn main() {
    // HashMap: O(1) average lookup
    let mut map = HashMap::new();
    for i in 0..100_000 {
        map.insert(i, format!("value_{}", i));
    }
    
    let start = Instant::now();
    let _ = map.get(&99_999);
    println!("HashMap lookup: {:?}", start.elapsed());
    
    // Vec: O(n) linear search
    let vec: Vec<(i32, String)> = (0..100_000)
        .map(|i| (i, format!("value_{}", i)))
        .collect();
    
    let start = Instant::now();
    let _ = vec.iter().find(|(k, _)| *k == 99_999);
    println!("Vec lookup: {:?}", start.elapsed());
}

The performance difference becomes dramatic as collections grow. HashMap maintains consistent lookup times regardless of size.

Creating and Populating HashMaps

The most straightforward approach uses new() for an empty HashMap, then populates it with insert():

use std::collections::HashMap;

let mut scores = HashMap::new();
scores.insert("Alice", 95);
scores.insert("Bob", 87);
scores.insert("Carol", 92);

For better performance with known sizes, pre-allocate capacity:

// Avoids reallocation during growth
let mut scores = HashMap::with_capacity(1000);
for i in 0..1000 {
    scores.insert(i, i * 2);
}

The collect() method provides elegant HashMap construction from iterators:

let teams = vec![
    ("Red", vec!["Alice", "Bob"]),
    ("Blue", vec!["Carol", "Dave"]),
];

let team_map: HashMap<_, _> = teams.into_iter().collect();

// From tuples
let scores: HashMap<_, _> = vec![
    ("Alice", 95),
    ("Bob", 87),
    ("Carol", 92),
].into_iter().collect();

The turbofish syntax HashMap<_, _> lets type inference determine key and value types.

Accessing and Modifying Values

HashMap’s get() method returns Option<&V>, enforcing safe access:

let mut scores = HashMap::new();
scores.insert("Alice", 95);

match scores.get("Alice") {
    Some(score) => println!("Alice scored {}", score),
    None => println!("No score found"),
}

// Idiomatic with if-let
if let Some(score) = scores.get("Bob") {
    println!("Bob scored {}", score);
} else {
    println!("Bob not found");
}

The entry() API is HashMap’s killer feature, eliminating double-lookups:

let mut scores = HashMap::new();

// Bad: lookups twice
if !scores.contains_key("Alice") {
    scores.insert("Alice", 0);
}
scores.insert("Alice", scores.get("Alice").unwrap() + 10);

// Good: single lookup with entry()
scores.entry("Alice").or_insert(0);
*scores.entry("Alice").or_insert(0) += 10;

// Even better: modify existing or insert default
let score = scores.entry("Bob").or_insert(0);
*score += 5;

Use get_mut() for in-place modifications:

let mut scores = HashMap::new();
scores.insert("Alice", 95);

if let Some(score) = scores.get_mut("Alice") {
    *score += 5;  // Directly modify the value
}

Iteration and Traversal

HashMap provides three iteration modes: borrowed, mutable, and consuming.

let mut scores = HashMap::new();
scores.insert("Alice", 95);
scores.insert("Bob", 87);
scores.insert("Carol", 92);

// Immutable iteration
for (name, score) in &scores {
    println!("{}: {}", name, score);
}

// Still can use scores here
println!("Map size: {}", scores.len());

// Mutable iteration
for (name, score) in &mut scores {
    *score += 5;  // Curve all scores
}

// Consuming iteration (takes ownership)
for (name, score) in scores {
    println!("{} final: {}", name, score);
}
// scores is no longer accessible

Iterate over just keys or values:

let scores: HashMap<&str, i32> = [
    ("Alice", 95),
    ("Bob", 87),
].iter().cloned().collect();

// Keys only
for name in scores.keys() {
    println!("Player: {}", name);
}

// Values only
for score in scores.values() {
    println!("Score: {}", score);
}

// Mutable values
let mut scores = scores;
for score in scores.values_mut() {
    *score += 10;
}

Ownership and Borrowing with HashMaps

HashMap takes ownership of keys and values implementing Copy or requires explicit cloning:

let mut map = HashMap::new();

let key = String::from("color");
let value = String::from("blue");

map.insert(key, value);
// key and value are moved, no longer accessible

// This won't compile:
// println!("{}", key);

// For Copy types, no issue
let mut numbers = HashMap::new();
let x = 42;
numbers.insert(x, 100);
println!("x is still {}", x);  // Works fine

Using &str as keys requires lifetime management:

// String keys: owned, no lifetime issues
let mut owned: HashMap<String, i32> = HashMap::new();
owned.insert(String::from("key"), 42);

// &str keys: need matching lifetimes
fn create_map<'a>(keys: &'a [&'a str]) -> HashMap<&'a str, i32> {
    let mut map = HashMap::new();
    for key in keys {
        map.insert(*key, 0);
    }
    map
}

let keys = vec!["a", "b", "c"];
let map = create_map(&keys);

For values that are references, lifetimes must be explicit:

struct Cache<'a> {
    data: HashMap<String, &'a str>,
}

impl<'a> Cache<'a> {
    fn new() -> Self {
        Cache {
            data: HashMap::new(),
        }
    }
    
    fn insert(&mut self, key: String, value: &'a str) {
        self.data.insert(key, value);
    }
}

Common Patterns and Best Practices

Word frequency counting demonstrates HashMap’s power:

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

let text = "the quick brown fox jumps over the lazy dog the fox";
let freq = word_frequency(text);

for (word, count) in freq {
    println!("{}: {}", word, count);
}

Grouping data by category:

#[derive(Debug)]
struct Item {
    category: String,
    name: String,
}

fn group_by_category(items: Vec<Item>) -> HashMap<String, Vec<String>> {
    let mut groups = HashMap::new();
    
    for item in items {
        groups
            .entry(item.category)
            .or_insert_with(Vec::new)
            .push(item.name);
    }
    
    groups
}

let items = vec![
    Item { category: "fruit".to_string(), name: "apple".to_string() },
    Item { category: "fruit".to_string(), name: "banana".to_string() },
    Item { category: "veggie".to_string(), name: "carrot".to_string() },
];

let grouped = group_by_category(items);

Default value patterns with or_insert():

let mut cache = HashMap::new();

// Initialize with default if missing
let value = cache.entry("key").or_insert(42);
*value += 1;

// Compute default lazily
let expensive_default = cache
    .entry("computed")
    .or_insert_with(|| {
        // Only runs if key doesn't exist
        expensive_computation()
    });

fn expensive_computation() -> i32 {
    // Simulate expensive operation
    1000
}

Performance Considerations

HashMap uses a cryptographically secure hash function by default (SipHash), which prevents hash collision attacks but has overhead. For non-security-critical code, consider ahash or fxhash crates:

// Cargo.toml: ahash = "0.8"
use ahash::AHashMap;

let mut map = AHashMap::new();
map.insert("key", "value");

Capacity management affects performance:

// Bad: multiple reallocations
let mut map = HashMap::new();
for i in 0..10_000 {
    map.insert(i, i);
}

// Good: single allocation
let mut map = HashMap::with_capacity(10_000);
for i in 0..10_000 {
    map.insert(i, i);
}

Choose BTreeMap when you need sorted keys or deterministic iteration:

use std::collections::BTreeMap;

// HashMap: random iteration order
let mut hash = HashMap::new();
hash.insert(3, "three");
hash.insert(1, "one");
hash.insert(2, "two");

// BTreeMap: sorted iteration
let mut btree = BTreeMap::new();
btree.insert(3, "three");
btree.insert(1, "one");
btree.insert(2, "two");

for (k, v) in btree {
    println!("{}: {}", k, v);  // Prints in order: 1, 2, 3
}

For custom types as keys, implement Hash and Eq:

use std::hash::{Hash, Hasher};

#[derive(Debug, PartialEq, Eq)]
struct Point {
    x: i32,
    y: i32,
}

impl Hash for Point {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.x.hash(state);
        self.y.hash(state);
    }
}

let mut points = HashMap::new();
points.insert(Point { x: 0, y: 0 }, "origin");

HashMap is Rust’s workhorse for key-value storage. Master the entry() API, understand ownership semantics, and choose appropriate capacity for optimal performance. When order matters, reach for BTreeMap. When speed is critical and security isn’t, consider alternative hashers.