18.3 The HashMap<K, V> Type

A HashMap<K, V> stores unique keys mapped to values, offering average O(1) lookups and insertions. Keys and values must each be homogeneous: all keys share the same type K, and all values share the same type V. Unlike Vec and String, using a hash map requires importing it:

use std::collections::HashMap;

Because HashMap is generic over K and V, you can store many different combinations of types, as long as they implement required traits.

18.3.1 Characteristics of HashMap<K, V>

  • Key-Value Pairs: Each key maps to exactly one value.
  • Hashing: A hash function turns keys into indices in an internal table.
  • Dynamic Resizing: The hash map expands as needed.
  • Unordered: There's no guaranteed order of keys or iteration.

Keys must implement Hash and Eq. The default implementation uses a secure hash function to minimize collisions.

18.3.2 Creating a HashMap

  • Empty HashMap:

    #![allow(unused)]
fn main() {
use std::collections::HashMap;

let mut map: HashMap<String, i32> = HashMap::new();
}

  • With an Initial Capacity:

    #![allow(unused)]
fn main() {
use std::collections::HashMap;
let mut map: HashMap<String, i32> = HashMap::with_capacity(20);
}

    This reserves space for at least 20 entries before resizing, similar to Vec::with_capacity().

  • From Iterators:

    #![allow(unused)]
fn main() {
use std::collections::HashMap;
let names = vec!["Alice", "Bob"];
let scores = vec![10, 20];
let map: HashMap<_, _> = names.into_iter().zip(scores.into_iter()).collect();
}

18.3.3 Inserting Data and Ownership

When inserting data into a hash map:

  • If the key or value implements the Copy trait (like i32), it will be copied into the map.
  • If the key or value is owned data (like String), it will be moved into the map, and the map becomes its owner.

For example:

map.insert("Charlie".to_string(), 25); // The String is moved into the map
map.insert("Dave".to_string(), 42);   // Another owned String moved in

18.3.4 Common Operations

  • Insert:

    map.insert("Eve".to_string(), 30);

  • Lookup:

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

  • Remove:

    map.remove("Charlie");

  • Iteration:

    for (key, value) in &map {
    println!("{}: {}", key, value);
}

  • Using entry to Insert or Modify:

    map.entry("Dave".to_string()).or_insert(0);

18.3.5 Advantages and Limitations

Advantages:

  • Average O(1) performance for lookups and insertions.
  • Flexible key types.

Limitations:

  • Memory overhead from hashing.
  • Unordered storage.

18.3.6 Hash Collisions and Resizing

If multiple keys hash to the same bucket (a collision), HashMap handles it internally. When it becomes too full, it resizes and rehashes entries to maintain performance.

18.3.7 Summary

HashMap<K, V> is ideal when you need to associate arbitrary keys with values quickly. It requires use std::collections::HashMap, is generic over both key and value types, and moves ownership of owned values into the map. It provides a powerful and flexible alternative to keyed lookups that don’t map naturally to numeric indices.