HashMaps

A HashMap in Rust is a collection that stores data as key-value pairs, letting you look up a value almost instantly if you know its key instead of scanning a list item by item. It lives in the standard library at std::collections::HashMap and is the tool of choice whenever you need to associate one piece of data with another — usernames with scores, words with their counts, IDs with records. Because Rust has no built-in dictionary literal syntax, you build a HashMap by inserting entries one at a time, and the same ownership rules that govern every other value in Rust apply just as strictly to the keys and values stored inside it.

Overview: How HashMaps Work

Think of a HashMap as a wall of numbered lockers. When you insert a key-value pair, Rust runs the key through a hash function — code that turns the key into a number — and uses that number to decide which locker (technically a bucket) the value goes into. When you later look up the same key, Rust hashes it again, gets the same number, and jumps straight to that locker instead of checking every locker in the wall. This is why lookups, insertions, and removals are, on average, O(1) — constant time — regardless of how many entries the map holds, compared to O(n) for scanning a Vec looking for a match.

For this scheme to work, every key type must implement two traits: Eq (so Rust can tell when two keys are truly \”the same\” after a hash collision) and Hash (so Rust can compute that number in the first place). Most built-in types — integers, String, &str, bool, tuples of hashable types — already implement both, so you rarely think about this until you try to use a custom struct as a key, at which point you need to derive Hash, Eq, and PartialEq, usually with #[derive(Hash, Eq, PartialEq)], or you get a compile error.

Ownership works exactly the way it does everywhere else in Rust: inserting a String into a HashMap moves it into the map — the map now owns that string, and the variable you inserted from can no longer be used. Values behave the same way. This is the single most common source of \”value borrowed after move\” errors for newcomers to HashMaps, and it is covered in Common Mistakes below.

By default, Rust’s HashMap uses a hashing algorithm called SipHash, chosen specifically because it resists a denial-of-service attack where an adversary crafts keys that all collide into the same bucket, degrading lookups toward O(n). This makes the default HashMap somewhat slower than a hasher optimized purely for speed — a deliberate, security-conscious trade-off. If profiling shows hashing is a real bottleneck in a context where attacker-controlled keys are not a concern, you can swap in a faster hasher from a crate such as ahash, but HashMap::new() with its default hasher is the right choice for the vast majority of programs. One more consequence of hashing: HashMaps do not preserve insertion order, and the order you get when iterating is unspecified and can even change between runs of the same program. If you need predictable ordering, sort the keys yourself before printing (as the examples below do), or reach for std::collections::BTreeMap, which keeps keys sorted at the cost of slightly slower operations.

Syntax

use std::collections::HashMap;

let mut map: HashMap<KeyType, ValueType> = HashMap::new();

map.insert(key, value);              // insert or overwrite
map.get(&key);                        // Option<&ValueType>
map.remove(&key);                     // Option<ValueType>, removes the entry
map.contains_key(&key);               // bool
map.entry(key).or_insert(default);   // get-or-insert in one step

• HashMap::new() creates an empty map; Rust infers the key/value types from usage, or you annotate them explicitly as shown.
• KeyType must implement Hash and Eq; ValueType can be almost anything.
• map must be declared mut to insert, remove, or update entries — HashMap follows the same mutability rules as any other Rust value.

Method	Returns	Description
insert(k, v)	Option<V>	Inserts or overwrites; returns the old value if the key already existed.
get(&k)	Option<&V>	Borrowed lookup; None if the key is absent.
remove(&k)	Option<V>	Removes the entry and returns its value, if present.
contains_key(&k)	bool	Checks for a key without needing to borrow its value.
entry(k)	Entry<K, V>	Update-or-insert a slot in a single, idiomatic operation.
len()	usize	Number of key-value pairs currently stored.
keys() / values()	iterators	Borrowed iterators over just the keys or just the values.

Examples

Example 1: Creating a HashMap and Looking Up Values

use std::collections::HashMap;

fn main() {
    let mut scores: HashMap<String, i32> = HashMap::new();

    scores.insert(String::from(\"Alice\"), 95);
    scores.insert(String::from(\"Bob\"), 82);

    match scores.get(\"Alice\") {
        Some(score) => println!(\"Alice's score: {}\", score),
        None => println!(\"Alice not found\"),
    }

    if scores.contains_key(\"Bob\") {
        println!(\"Bob is in the map\");
    }

    println!(\"Total players: {}\", scores.len());
}

Output:

Alice's score: 95
Bob is in the map
Total players: 2

This program creates a HashMap mapping player names (String) to scores (i32). Calling .get(\"Alice\") returns an Option<&i32> rather than the value itself, because the key might not be present — matching on Some/None forces you to handle both cases instead of risking a crash. Note that even though the map’s key type is String, you can look it up with a plain &str literal like \"Alice\"; Rust’s Borrow trait lets get, remove, and contains_key accept a borrowed slice of the key type without allocating a new String just to perform a lookup.

Example 2: Counting Words with the Entry API

use std::collections::HashMap;

fn main() {
    let text = \"the quick brown fox jumps over the lazy dog the fox runs\";
    let mut word_count: HashMap<&str, i32> = HashMap::new();

    for word in text.split_whitespace() {
        let count = word_count.entry(word).or_insert(0);
        *count += 1;
    }

    let mut pairs: Vec<(&&str, &i32)> = word_count.iter().collect();
    pairs.sort();

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

Output:

brown: 1
dog: 1
fox: 2
jumps: 1
lazy: 1
over: 1
quick: 1
runs: 1
the: 3

This is the classic word-frequency counter, and it shows off the entry API, the idiomatic way to update-or-initialize a value in one step. word_count.entry(word) returns an Entry that either points at the existing slot for that key or, via .or_insert(0), inserts a fresh 0 and returns a mutable reference to it — either way you get back a &mut i32 you can immediately increment with *count += 1. Without entry, you would need to call get to check for existence and then separately call insert, which is both more verbose and more error-prone. The example also demonstrates the ordering gotcha from the Overview: because HashMap iteration order is unspecified, the code collects the pairs into a Vec and sorts them before printing so the output is deterministic.

Example 3: Updating and Removing Entries

use std::collections::HashMap;

fn main() {
    let mut inventory: HashMap<String, u32> = HashMap::new();
    inventory.insert(String::from(\"sword\"), 1);
    inventory.insert(String::from(\"shield\"), 2);

    *inventory.entry(String::from(\"sword\")).or_insert(0) += 5;
    *inventory.entry(String::from(\"potion\")).or_insert(0) += 3;

    if let Some(count) = inventory.remove(\"shield\") {
        println!(\"Removed {} shields from inventory\", count);
    }

    let mut items: Vec<(&String, &u32)> = inventory.iter().collect();
    items.sort();

    for (item, count) in items {
        println!(\"{}: {}\", item, count);
    }
}

Output:

Removed 2 shields from inventory
potion: 3
sword: 6

This example manages a simple inventory. It uses entry(...).or_insert(0) twice — once to increment an item that already exists (\"sword\") and once to create a brand-new one (\"potion\") — showing that the same one-liner correctly handles both cases. remove returns an Option<V> containing the removed value if the key was present, which is why if let Some(count) = inventory.remove(\"shield\") both deletes the entry and gives you back how many shields there were in a single expression.

How It Works Step by Step

Follow what happens when Example 2 runs: for the very first word, \"the\", Rust hashes the string to a bucket index, finds nothing stored there, and entry().or_insert(0) creates a new slot holding 0 and hands back a mutable reference to it, which is immediately incremented to 1. The next time the loop encounters \"the\", hashing the same string produces the same bucket index, Rust finds the existing entry, and or_insert simply returns a reference to the value already there — no new slot is created — and the counter climbs to 2, then 3. This is the core mechanic of every hash map: the hash of the key is a deterministic shortcut straight to the right bucket, so lookup cost does not grow with the number of entries already stored, barring the rare case of many keys colliding into the same bucket, which the map handles internally at some cost to that bucket’s lookup speed. When the map’s load factor — the ratio of entries to buckets — gets too high, HashMap automatically allocates a larger backing array and re-hashes every existing entry into it, exactly like the reallocate-and-copy that happens when a Vec outgrows its capacity.

Common Mistakes

Mistake 1: Using a Value After It Has Moved Into the Map

Passing a String to insert moves it — ownership transfers to the map, and the original variable is no longer valid. Trying to use it afterward is a compile-time error, not a runtime bug:

use std::collections::HashMap;

fn main() {
    let key = String::from(\"username\");
    let mut map: HashMap<String, i32> = HashMap::new();
    map.insert(key, 1);

    println!(\"{}\", key);
}

Compiler output:

error[E0382]: borrow of moved value: `key`

The fix is to decide up front whether you actually need the original variable afterward. If you do, clone the key before inserting — cloning a String allocates a second heap buffer, so only do this when you truly need two independent owners; if you don’t, simply stop referencing the moved variable.

use std::collections::HashMap;

fn main() {
    let key = String::from(\"username\");
    let mut map: HashMap<String, i32> = HashMap::new();
    map.insert(key.clone(), 1);

    println!(\"{}\", key);
}

Output:

username

Mistake 2: Holding a Borrow While Mutating the Map

HashMap enforces Rust’s borrowing rule just like any other value: you cannot hold an immutable reference returned by get across a call that mutably borrows the map, such as insert or remove. This trips people up because the mutation looks unrelated to the earlier lookup:

use std::collections::HashMap;

fn main() {
    let mut scores: HashMap<String, i32> = HashMap::new();
    scores.insert(String::from(\"Alice\"), 10);

    let alice_score = scores.get(\"Alice\");
    scores.insert(String::from(\"Bob\"), 20);

    println!(\"{:?}\", alice_score);
}

Compiler output:

error[E0502]: cannot borrow `scores` as mutable because it is also borrowed as immutable

Rust’s borrow checker uses non-lexical lifetimes, meaning the immutable borrow from get is considered alive for as long as it is still used later in the function — here, that is the final println!, which spans across the insert call and creates the conflict. The fix is to end the borrow before mutating, typically by extracting an owned copy of the data you need with .copied() for Copy types, or .cloned() for anything else:

use std::collections::HashMap;

fn main() {
    let mut scores: HashMap<String, i32> = HashMap::new();
    scores.insert(String::from(\"Alice\"), 10);

    let alice_score = scores.get(\"Alice\").copied();
    scores.insert(String::from(\"Bob\"), 20);

    println!(\"{:?}\", alice_score);
}

Output:

Some(10)

Best Practices

• Prefer the entry API over a manual get-then-insert pair whenever you are updating or initializing a value — it is both shorter and avoids doing the hash lookup twice.
• Use get combined with match or if let instead of indexing with map[&key], which panics if the key is missing.
• Call HashMap::with_capacity(n) when you know roughly how many entries you will insert, to avoid repeated reallocation and re-hashing as the map grows.
• Never rely on iteration order; sort keys explicitly before printing, or switch to BTreeMap if you genuinely need sorted, stable order.
• When using a custom struct as a key, derive Hash, Eq, and PartialEq together, and make sure the fields that determine equality are exactly the fields that feed the hash — inconsistency between the two silently breaks lookups.
• Use Entry::or_insert_with(...) instead of or_insert(...) when the default value is expensive to compute, since or_insert_with only calls the closure when a new entry is actually needed.
• Stick with the default hasher unless profiling proves it is a bottleneck; it trades a little speed for resistance to hash-flooding denial-of-service attacks.

Practice Exercises

1. Write a program that builds a HashMap<String, i32> of product names to prices, then prints the price of one specific product using get and a match, handling the case where the product is missing.
2. Given the sentence \"mississippi river\", use a HashMap<char, i32> to count how many times each non-space character appears, then print the counts sorted by character. Hint: iterate with .chars() and use entry(c).or_insert(0).
3. Write a function that takes a &HashMap<String, u32> of names to ages and returns the name with the highest age using .iter() and max_by_key. For {\"Sam\": 40, \"Lee\": 52, \"Kim\": 31} it should identify \"Lee\" with age 52.

Summary

• HashMap<K, V> stores key-value pairs and gives average O(1) insert, lookup, and removal by hashing keys into buckets.
• Keys must implement Hash and Eq; most built-in types already do, and custom structs need #[derive(Hash, Eq, PartialEq)].
• insert moves ownership of both the key and value into the map; look up with borrowed keys via get, remove, and contains_key.
• entry(key).or_insert(default) is the idiomatic update-or-initialize pattern and avoids a redundant lookup.
• Iteration order is unspecified and can change between runs — sort explicitly, or use BTreeMap when order matters.
• The borrow checker treats a HashMap like any other value: you cannot hold a borrow from get across a later mutation such as insert.