HashMaps - Rust for C-Programmers

18.4 The `HashMap<K, V>` Type

HashMap<K, V> is Rust’s primary implementation of a hash map (also known as a hash table, dictionary, or associative array). It stores mappings from unique keys of type K to associated values of type V. It provides efficient average-case time complexity for insertion, retrieval, and removal operations, typically O(1).

To use HashMap, you first need to bring it into scope:

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

18.4.1 Key Characteristics

Unordered: The iteration order of elements in a HashMap is arbitrary and depends on the internal hashing and layout. You should not rely on any specific order. The order might even change between different program runs.
Key Requirements: The key type K must implement the Eq (equality comparison) and Hash (hashing) traits. Most built-in types that can be meaningfully compared for equality, like integers, booleans, String, and tuples composed of hashable types, satisfy these requirements. Floating-point types (f32, f64) do not implement Hash by default because NaN != NaN and other precision issues make consistent hashing difficult. To use floats as keys, you typically need to wrap them in a custom struct that defines appropriate Hash and Eq implementations (e.g., by handling NaN explicitly or comparing based on bit patterns).
Hashing Algorithm: By default, HashMap uses SipHash 1-3, a cryptographically secure hashing algorithm designed to be resistant to Hash Denial-of-Service (HashDoS) attacks. These attacks involve an adversary crafting keys that deliberately cause many hash collisions, degrading the map’s performance to O(n). While secure, SipHash is slightly slower than simpler, non-cryptographic hashers. For performance-critical scenarios where HashDoS is not a concern (e.g., keys are not derived from external input), you can switch to a faster hasher using crates like fnv or ahash.
Ownership: HashMap takes ownership of its keys and values. When you insert an owned type like a String key or a Vec<T> value, that specific instance is moved into the map. If you insert types that implement the Copy trait (like i32), their values are copied into the map.

18.4.2 Creating and Populating a HashMap

#![allow(unused)]
fn main() {
// Create an empty HashMap
let mut scores: HashMap<String, i32> = HashMap::new();

// Insert key-value pairs using .insert()
// Note: .to_string() creates an owned String from the &str literal
scores.insert("Alice".to_string(), 95);
scores.insert(String::from("Bob"), 88); // String::from also works

// Create with initial capacity estimate
let mut map_cap = HashMap::with_capacity(50);

// Create from an iterator of tuples (K, V)
let teams = vec![String::from("Blue"), String::from("Red")];
let initial_scores = vec![10, 50];
// zip combines the two iterators into an iterator of pairs
// collect consumes the iterator and creates the HashMap
let team_scores: HashMap<String, i32> =
    teams.into_iter().zip(initial_scores.into_iter()).collect();
}

18.4.3 Accessing Values

#![allow(unused)]
fn main() {
use std::collections::HashMap;
let mut scores: HashMap<String, i32> = HashMap::new();
scores.insert(String::from("Alice"), 95);
scores.insert(String::from("Bob"), 88);

// Using .get(&key) for safe access (returns Option<&V>)
// Note: .get() takes a reference to the key type.
let alice_score: Option<&i32> = scores.get("Alice"); // &str can be used if K=String
match alice_score {
    Some(score_ref) => println!("Alice's score: {}", score_ref),
    None => println!("Alice not found."),
}

// Using indexing map[key] - Panics if key not found!
// Only use when absolutely sure the key exists.
// let bob_score = scores["Bob"]; // Returns i32 by copying if V is Copy, else panics.
// let alice_ref = &scores["Alice"]; // Returns &i32

// Checking for key existence
if scores.contains_key("Bob") {
    println!("Bob is in the map.");
}
}

18.4.4 Updating and Removing Values

Overwriting with insert: If you insert a key that already exists, the old value is overwritten, and insert returns Some(old_value). If the key was new, it returns None.

#![allow(unused)]
fn main() {
use std::collections::HashMap;
let mut scores: HashMap<String, i32> = HashMap::new();
scores.insert(String::from("Alice"), 95);
let old_alice = scores.insert("Alice".to_string(), 100); // Update Alice's score
assert_eq!(old_alice, Some(95));
}

Conditional Insertion/Update with the entry API: The entry method is powerful for handling cases where you might need to insert a value only if the key doesn’t exist, or update an existing value.

#![allow(unused)]
fn main() {
use std::collections::HashMap;
let mut word_counts: HashMap<String, u32> = HashMap::new();
let text = "hello world hello";

for word in text.split_whitespace() {
    // entry(key) returns an Entry enum (Occupied or Vacant)
    // or_insert(default_value) gets a mutable ref to the existing value
    // or inserts the default and returns a mutable ref to the new value.
    let count: &mut u32 = word_counts.entry(word.to_string()).or_insert(0);
    *count += 1; // Dereference the mutable reference to increment the count
}
// word_counts is now {"hello": 2, "world": 1} (order may vary)
println!("{:?}", word_counts);
}

The entry API has other useful methods like or_default() (uses Default::default() if vacant) and and_modify() (updates if occupied).

Removing with remove: remove(&key) removes a key-value pair if the key exists, returning Some(value) (the owned value). If the key doesn’t exist, it returns None.

#![allow(unused)]
fn main() {
use std::collections::HashMap;
let mut scores: HashMap<String, i32> = HashMap::new();
scores.insert(String::from("Alice"), 95);
if let Some(score) = scores.remove("Alice") {
    println!("Removed Alice with score: {}", score); // score is the owned i32
}
}

18.4.5 Iteration

You can iterate over keys, values, or key-value pairs. Remember that the iteration order is not guaranteed.

#![allow(unused)]
fn main() {
use std::collections::HashMap;
let scores: HashMap<String, i32> = HashMap::from([
    ("Alice".to_string(), 95), ("Bob".to_string(), 88)
]);

// Iterate over key-value pairs (yields immutable references: (&K, &V))
println!("Scores:");
for (name, score) in &scores { // or scores.iter()
    println!("- {}: {}", name, score);
}

// Iterate over keys only (yields immutable references: &K)
println!("\nNames:");
for name in scores.keys() {
    println!("- {}", name);
}

// Iterate over values only (yields immutable references: &V)
println!("\nValues:");
for score in scores.values() {
    println!("- {}", score);
}

// To get mutable references to values:
// for score in scores.values_mut() { *score += 1; }
// for (key, value) in scores.iter_mut() { *value += 1; }
}

18.4.6 Internal Details: Hashing, Collisions, and Resizing

Internally, HashMap typically uses an array (often a Vec) of buckets. When inserting a key-value pair:

The key is hashed to produce an integer.
This hash is used to calculate an index into the bucket array.
If the bucket is empty, the key-value pair is stored there.
If the bucket already contains elements (due to hash collisions, where different keys hash to the same index), the map uses a collision resolution strategy. A common strategy is separate chaining, where each bucket stores a small list (e.g., a linked list or Vec) of the key-value pairs that collided into that bucket. The map then checks the keys in that list to find a match or the correct place for insertion.

To maintain efficient average O(1) lookups, the HashMap monitors its load factor (number of elements / number of buckets). When the load factor exceeds a certain threshold, the map allocates a larger array of buckets (resizing) and rehashes all existing elements, redistributing them into the new, larger table. This resizing operation takes O(n) time but happens infrequently enough that the average insertion time remains O(1).

18.4.7 Summary: `HashMap` vs. C Hash Tables

Implementing hash tables manually in C requires significant effort: choosing or implementing a suitable hash function, designing an effective collision resolution strategy (like chaining or open addressing), writing the logic for resizing the table, and managing memory for the table structure, keys, and values. Using a third-party C library can help, but integration and ensuring type safety and memory safety still rely heavily on the programmer.

Rust’s HashMap<K, V> provides:

A ready-to-use, performant, and robust implementation.
Automatic memory management for keys, values, and the internal table structure, preventing leaks.
Compile-time type safety enforced by generics (K, V).
A secure default hashing algorithm (SipHash 1-3) resistant to HashDoS attacks.
Integration with Rust’s ownership and borrowing system, preventing dangling pointers to keys or values.
Average O(1) performance for insertion, lookup, and removal, comparable to well-tuned C implementations but with built-in safety guarantees.