18.4 The HashMap<K, V> Type

A HashMap<K, V> stores unique keys associated with values, providing average O(1) insertion and lookup. It’s similar to std::unordered_map in C++ or a classic C-style hash table, but with ownership rules that prevent leaks and dangling pointers.

use std::collections::HashMap;

18.4.1 Characteristics of HashMap<K, V>

  • Each unique key maps to exactly one value.
  • Keys must implement Hash and Eq.
  • The data is stored in an unordered manner, so iteration order is not guaranteed.
  • The table automatically resizes as it grows.

18.4.2 Creating and Inserting

let mut scores: HashMap<String, i32> = HashMap::new();
scores.insert("Alice".to_string(), 10);
scores.insert("Bob".to_string(), 20);

// With an initial capacity
let mut map = HashMap::with_capacity(20);
map.insert("Eve".to_string(), 99);

// From two vectors with `.collect()`
let names = vec!["Carol", "Dave"];
let points = vec![12, 34];
let map2: HashMap<_, _> = names.into_iter().zip(points.into_iter()).collect();

18.4.3 Ownership and Lifetimes

  • Copied values: If a type (e.g., i32) implements Copy, it is copied when inserted.
  • Moved values: For owned data (e.g., String), the hash map takes ownership. You can clone if you need to retain the original.

18.4.4 Common Operations

// Lookup
if let Some(&score) = scores.get("Alice") {
    println!("Alice's score: {}", score);
}

// Remove
scores.remove("Bob");

// Iteration
for (key, value) in &scores {
    println!("{} -> {}", key, value);
}

// Using `entry`
scores.entry("Carol".to_string()).or_insert(0);

18.4.5 Resizing and Collisions

When hashing leads to collisions (same hash result for different keys), Rust stores colliding entries in “buckets.” If collisions increase, the map resizes and rehashes to maintain efficiency.

18.4.6 Summary: HashMap vs. C

In C, you might manually implement a hash table or use a library. Rust’s HashMap internally handles collisions, resizing, and memory management. By leveraging ownership, it prevents errors like freeing memory prematurely or referencing invalidated entries. You get an average O(1) complexity for lookups and inserts, with safe, automatic memory handling.