c. Hash Maps (HashMap<K, V>)

What Is a Hash Map?

A HashMap<K, V> is a collection that stores key-value pairs, allowing you to look up a value by providing its key. The lookup uses a hashing function to determine where the data lives in memory, so you don’t need to know an index. Under the hood, Rust’s HashMap uses the hashbrown crate (a port of Google’s SwissTable), implementing open addressing with quadratic probing and SIMD-accelerated searches.

Think of a hash map as a locker room where each locker has a label, and you open a locker by its label, not its position in the row. You can store anything inside and retrieve it instantly as long as you know the label.

Hash maps are unordered. The iteration order is arbitrary and can change between runs. They provide amortized O(1) average time for insertions, lookups, and deletions, provided the hashing function distributes keys well and the table is sized appropriately.

Why Use a Hash Map?

When you need to associate one piece of data with another and retrieve it efficiently by the first piece, a hash map is the tool. Common scenarios include counting word frequencies, caching computed results by a unique key, storing configuration values, and building lookup tables that map IDs to objects. Vectors give you access by index, but hash maps let you access data by any comparable, hashable key.

The type is not in the prelude—you must import it with use std::collections::HashMap. This is intentional; hash maps are used less frequently than vectors or strings, and keeping them out of scope saves compile time and avoids name clashes.

Creating a Hash Map

The simplest way: HashMap::new() creates an empty map with zero capacity. It won’t allocate until the first insertion.

use std::collections::HashMap;
let mut scores: HashMap<String, i32> = HashMap::new();
scores.insert("Blue".to_string(), 10);
scores.insert("Yellow".to_string(), 50);

If you know how many entries you’ll insert, use with_capacity to pre-allocate. This avoids multiple reallocations as the map grows.

let mut map: HashMap<&str, u64> = HashMap::with_capacity(1000);

You can also construct a map from an array of tuples using HashMap::from:

let solar_distance = HashMap::from([
    ("Mercury", 0.4),
    ("Venus", 0.7),
    ("Earth", 1.0),
    ("Mars", 1.5),
]);

Or collect from an iterator of key-value pairs, which often comes from zipping two vectors:

let teams = vec!["Blue", "Yellow"];
let scores = vec![10, 50];
let team_scores: HashMap<_, _> = teams.into_iter().zip(scores.into_iter()).collect();

The type annotation HashMap<_, _> is required because collect can produce many collection types. Rust infers the concrete key and value types from the zipped iterator.

Inserting and Overwriting Values

The insert method takes ownership of the key and value. If the key already exists, the old value is replaced and returned as Some(old_value). If the key is new, it returns None.

let mut map = HashMap::new();
map.insert("key", 1);
let old = map.insert("key", 2);
assert_eq!(old, Some(1));

For types that implement Copy, like integers, the value is copied into the map. For owned types like String, the value is moved, and you can no longer use the original variable after insertion.

Accessing Values

The primary method is get, which takes a reference to the key and returns Option<&V>. This avoids panics when a key isn’t present.

let score = scores.get("Blue");
match score {
    Some(&value) => println!("Blue team has {value} points"),
    None => println!("Blue team not found"),
}

An important ergonomic detail: get accepts a reference to any type that the key can borrow from. Because String implements Borrow<str>, you can pass &str to a HashMap<String, V> and it will work as if you passed &String. This is why you see scores.get("Blue") with a string literal, not scores.get(&String::from("Blue")).

If you are absolutely certain a key exists, indexing with [] returns an immutable reference to the value. But it panics if the key is missing.

let blue_score = scores["Blue"]; // panics if "Blue" not present

To check membership without fetching the value, use contains_key:

if scores.contains_key("Green") {
    println!("Green team exists");
}

The Entry API

The entry method is the most idiomatic way to handle insert-or-update logic in a single lookup. It returns an Entry enum—Occupied if the key exists, Vacant if not—and provides methods to manipulate the value accordingly.

The simplest pattern is or_insert, which inserts a default value if the key is missing and returns a mutable reference to the value (either the existing one or the newly inserted default).

let mut word_counts: HashMap<String, u32> = HashMap::new();
for word in "hello world hello".split_whitespace() {
    let count = word_counts.entry(word.to_string()).or_insert(0);
    *count += 1;
}
// word_counts now contains {"hello": 2, "world": 1}

or_insert_with is useful when the default value is expensive to compute or has side effects; it accepts a closure that is called only on vacancy.

let val = map.entry(key).or_insert_with(|| expensive_computation());

The and_modify method lets you update an existing entry in place before possibly inserting a default:

player_stats.entry("mana")
    .and_modify(|mana| *mana += 200)
    .or_insert(100);

If "mana" already exists, and_modify adds 200 to it. If not, or_insert inserts 100.

Updating a Value Based on Its Old Value

The pattern shown in the word count example is the typical way: get a mutable reference via entry and dereference it to modify. The * operator turns the &mut u32 into a u32 so you can add to it.

let score = map.entry("player1").or_insert(0);
*score += bonus;

You can also use iter_mut to modify all values at once:

for (_, value) in map.iter_mut() {
    *value += 5;
}

Removing Entries

remove takes a reference to the key and returns Option<V>—the owned value if the key was present.

if let Some(old_score) = scores.remove("Red") {
    println!("Removed Red team with score {old_score}");
}

The map no longer owns that key or its value after removal. If you need the key back, you’ll have to restructure your code (perhaps using remove_entry in nightly Rust, which returns both key and value as a pair).

Iterating Over a Hash Map

Iteration yields references to key-value pairs in an arbitrary order.

for (team, score) in &scores {
    println!("{team}: {score}");
}

• iter() / &map gives (&K, &V).
• iter_mut() gives (&K, &mut V), allowing you to modify values.
• keys() and values() return iterators over just keys or values.
• into_iter() consumes the map, yielding owned (K, V) pairs.

Because the order is not guaranteed, never rely on it for reproducible output. If you need sorted order, use BTreeMap or collect the pairs into a Vec and sort them afterward.

Ownership and Hash Maps

When you insert a key and value that do not implement Copy, the map takes ownership of both. The original variables become invalid.

let key = String::from("name");
let value = String::from("Alice");
let mut map = HashMap::new();
map.insert(key, value);
// key and value can no longer be used here

Types that implement Copy, like i32 or bool, are copied, so the originals remain usable.

If you need to store references, you can insert borrowed data, but then the references must outlive the map. This often involves explicit lifetime annotations.

let data = "hello";
let mut map: HashMap<&str, i32> = HashMap::new();
map.insert(data, 42); // data is a &str with static lifetime, so it's fine

Custom Key Types

To use your own struct as a key, derive Hash, Eq, and PartialEq. The Eq trait requires PartialEq as a supertrait.

#[derive(Hash, Eq, PartialEq, Debug)]
struct PlayerId {
    server: String,
    id: u64,
}
let mut sessions: HashMap<PlayerId, String> = HashMap::new();
sessions.insert(PlayerId { server: "us-east".into(), id: 1001 }, "abc123".into());

The derived implementations ensure the critical contract: if k1 == k2, then hash(k1) == hash(k2). If you implement Hash and Eq manually, you must enforce this. Breaking the contract is a logic error.

Types that do not have a stable notion of equality, like f32 and f64, do not implement Hash because NaN != NaN makes a consistent hash impossible. If you must use floats as keys, wrap them in a newtype and define manual Hash and Eq that handle NaN explicitly, for example by treating all NaN values as equal and hashing their bit patterns.

Capacity and Performance

The map automatically grows when the load factor exceeds a threshold. Rehashing involves allocating a new, larger table and re-inserting all entries, which is an O(n) operation. If you know the approximate number of entries upfront, with_capacity can prevent these expensive reallocations.

let mut map: HashMap<&str, u32> = HashMap::with_capacity(100_000);

You can inspect the current capacity with capacity() and the number of entries with len(). Shrinking is possible with shrink_to_fit() and shrink_to(min_capacity).

Hashing Algorithm and Security

By default, HashMap uses the SipHash 1-3 algorithm with a random seed generated at runtime. SipHash is not the fastest hash function, but it provides strong protection against HashDoS attacks—where an attacker crafts keys that cause many collisions, degrading performance to O(n). The random seed ensures that an attacker cannot predict which keys will collide.

For performance-critical applications where HashDoS is not a concern (for example, the keys are generated internally and not from user input), you can switch to a faster hasher. The standard library provides BuildHasherDefault with DefaultHasher (which uses a non-cryptographic algorithm), and crates like fnv and ahash offer even faster alternatives.

use std::collections::HashMap;
use std::hash::BuildHasherDefault;
use std::collections::hash_map::DefaultHasher;
let mut map: HashMap<&str, i32, BuildHasherDefault<DefaultHasher>> =
    HashMap::default(); // uses DefaultHasher, no random seed

For const and static contexts where random seeding is impossible, you can either use a hasher that does not require a seed (like BuildHasherDefault<DefaultHasher>) or wrap a HashMap in LazyLock to retain random seeding at initialization.

Common Mistakes

• Forgetting to import HashMap. The compiler will suggest adding the import.
• Indexing a missing key with [] causes a panic. Use get for fallible access.
• Using f32 or f64 as keys directly—they don’t implement Hash.
• Assuming any order in iteration. The order is intentionally non-deterministic. If you need ordering, use BTreeMap.
• Inserting references and then dropping the owner, leaving a dangling reference.
• Modifying a key while it’s in the map via interior mutability—this corrupts the map.
• Using the wrong key type in get: while Borrow allows &str for String, it won’t save you if the map’s key type is i32 and you pass &i64. The type must match or be convertible via Borrow.

When to Use HashMap vs BTreeMap

• Choose HashMap for the average O(1) lookup, insertion, and deletion, and when you don’t care about order.
• Choose BTreeMap when you need keys in sorted order, efficient range queries (range()), or ordered iteration. BTreeMap operations are O(log n).

This document covers the basics; later sections in the collections chapter explore HashMap internals in greater depth, alternative hashing strategies, and other map types like BTreeMap and HashSet.

Summary

HashMap<K, V> gives you a fast, unordered key-value store with strong ownership semantics and safe default hashing. Its entry API eliminates redundant work and makes conditional insertion clear. The default SipHash algorithm balances security and performance, but you have the freedom to swap in a faster hasher when appropriate.