I Built a Hash Map in Rust. Here Is What the Standard Library Was Hiding From You

Part of the Data Structures in Rust series.

The linked list fought the borrow checker. The binary tree worked with it naturally. The hash map does something more interesting than either: it reveals why the standard library’s HashMap API is shaped the way it is, and once you have built one yourself, the design decisions that previously looked arbitrary start looking inevitable.

Most engineers use HashMap daily without thinking about what is underneath. You insert a key, you retrieve a value, and the whole thing is fast enough that you never have to care about the implementation. Building one from scratch does not make you faster at using the standard library version. It makes you stop being surprised by the parts of the API that initially seemed strange: why get returns Option<&V>, why you cannot hold a reference to a value while inserting a new key into the same map, and what the Entry API is actually solving.

What a hash map actually is

A hash map is an array of buckets. You take a key, run it through a hash function to get an index, and store the key-value pair in the bucket at that index. Lookup works the same way: hash the key, go to that index, find the value.

The complication is collisions. Two different keys can produce the same index, and the hash map needs a strategy for handling that. The two standard approaches are chaining, where each bucket holds a list of all key-value pairs that hashed to that index, and open addressing, where a collision causes the map to probe for the next available slot. The standard library’s HashMap uses a variant of open addressing called Robin Hood hashing. The implementation here uses chaining because it is easier to follow and the ownership model is more transparent, even though it is not what production Rust uses.

const INITIAL_CAPACITY: usize = 16;

struct HashMap<K, V> {
    buckets: Vec<Vec<(K, V)>>,
    count: usize,
}

impl<K: Eq + std::hash::Hash, V> HashMap<K, V> {
    fn new() -> Self {
        let mut buckets = Vec::with_capacity(INITIAL_CAPACITY);
        for _ in 0..INITIAL_CAPACITY {
            buckets.push(Vec::new());
        }
        HashMap { buckets, count: 0 }
    }

    fn bucket_index(&self, key: &K) -> usize {
        use std::hash::{Hash, Hasher};
        use std::collections::hash_map::DefaultHasher;

        let mut hasher = DefaultHasher::new();
        key.hash(&mut hasher);
        (hasher.finish() as usize) % self.buckets.len()
    }
}

The type bounds K: Eq + std::hash::Hash deserve attention. To use a type as a hash map key, it needs to implement two traits: Hash so the hash function can process it, and Eq so the map can check whether two keys are actually the same when they land in the same bucket. This is enforced at the type level in Rust, which means the compiler catches the mistake of trying to use a non-hashable type as a key before any code runs. In Java, HashMap has the same requirement but it is documented rather than enforced: you are supposed to override both hashCode and equals together, and nothing stops you from forgetting, which produces silent incorrect behavior rather than a compile error.

Insertion and why ownership shapes the API

Inserting into the hash map means finding the right bucket and either updating an existing entry or adding a new one:

fn insert(&mut self, key: K, value: V) {
    if self.count >= self.buckets.len() * 3 / 4 {
        self.resize();
    }

    let index = self.bucket_index(&key);
    let bucket = &mut self.buckets[index];

    for (existing_key, existing_value) in bucket.iter_mut() {
        if *existing_key == key {
            *existing_value = value;
            return;
        }
    }

    bucket.push((key, value));
    self.count += 1;
}

The load factor check at the start, triggering a resize when the map is three-quarters full, is what keeps performance stable. A hash map that is completely full has every key colliding into long chains, and lookup degrades from O(1) to O(n). Keeping the load factor below 0.75 bounds the average chain length and keeps lookups fast.

The resize operation is where Rust’s ownership model does something instructive. You cannot just grow the bucket array in place, because every existing key needs to be re-hashed into the new, larger bucket array. That means taking ownership of all the existing key-value pairs, rebuilding the structure from scratch:

fn resize(&mut self) {
    let new_capacity = self.buckets.len() * 2;
    let mut new_buckets = Vec::with_capacity(new_capacity);
    for _ in 0..new_capacity {
        new_buckets.push(Vec::new());
    }

    let old_buckets = std::mem::replace(&mut self.buckets, new_buckets);
    self.count = 0;

    for bucket in old_buckets {
        for (key, value) in bucket {
            self.insert(key, value);
        }
    }
}

std::mem::replace swaps self.buckets with the new empty bucket array and returns the old one. This is how you take ownership of something inside a struct without leaving the struct in an invalid intermediate state, which Rust's move semantics would otherwise prevent. The old buckets get drained, each entry gets re-inserted into the new structure, and the map now has twice the capacity with all its data intact.

Lookup and the Option return type

fn get(&self, key: &K) -> Option<&V> {
    let index = self.bucket_index(key);
    let bucket = &self.buckets[index];

    for (existing_key, existing_value) in bucket.iter() {
        if existing_key == key {
            return Some(existing_value);
        }
    }

    None
}

The return type Option<&V> is not a Rust quirk or an inconvenience. It is the honest type for this operation. The key might not be in the map, and the only alternatives to Option are panicking on a missing key (which HashMap::index actually does, which is why you should prefer get over [] when the key might be absent) or returning some sentinel value, which requires V to have a meaningful "absent" state that not all types have.

The &V rather than V matters too. Returning a reference to the value avoids cloning it, which is significant when values are large. You cannot hold a reference to a value and mutate the map simultaneously because that would require both an immutable borrow and a mutable borrow of the map at the same time. Resize is just the most obvious case where that becomes unsafe in other languages.

let mut map = HashMap::new();
map.insert("key", vec![1, 2, 3]);

let value = map.get("key"); // borrows map immutably

// This would not compile:
// map.insert("other", vec![4, 5, 6]); // cannot borrow mutably while immutably borrowed
println!("{:?}", value); // borrow ends here
map.insert("other", vec![4, 5, 6]); // now fine

In Java, this constraint does not exist at the type system level. You can hold a reference to a value inside a HashMap and then add a new key that triggers a resize, and the reference now points into memory that has been freed and reallocated. This is a ConcurrentModificationException waiting to happen, detected at runtime if you are lucky and causing silent corruption if you are not. Rust makes the entire class of iterator-invalidation bugs impossible by design.

The Entry API and why it exists

The Entry API in the standard library exists to solve a specific problem: checking whether a key exists and conditionally inserting a default value without doing two separate lookups.

The naive approach requires two hash computations:

// Two lookups: one to check, one to insert
if !map.contains_key(&key) {
    map.insert(key, default_value);
}

The Entry API computes the hash once and gives you a handle to the location where the key would be, whether it exists or not:

// One lookup, conditional insert
map.entry(key).or_insert(default_value);

// More complex case: get existing or compute and insert
map.entry(key).or_insert_with(|| expensive_computation());

Implementing a simplified version of this in our custom map requires returning a reference to the slot where the value lives, whether the key existed or not:

enum Entry<'a, V> {
    Occupied(&'a mut V),
    Vacant(&'a mut Vec<(String, V)>, String),
}

impl<'a, V> Entry<'a, V> {
    fn or_insert(self, default: V) -> &'a mut V {
        match self {
            Entry::Occupied(value) => value,
            Entry::Vacant(bucket, key) => {
                bucket.push((key, default));
                &mut bucket.last_mut().unwrap().1
            }
        }
    }
}

The lifetime 'a on the Entry ties the returned reference to the lifetime of the map itself. The compiler knows that the &mut V returned by or_insert borrows from the same map that the Entry was created from, so it prevents you from using that reference after the map is mutated in a way that would invalidate it. The API is not just convenience. It is what makes the operation single-lookup and keeps you from accidentally writing the slower, duplicated version.

What building this teaches you

The standard library’s HashMap uses a more sophisticated hash algorithm, Robin Hood hashing for better cache performance than chaining, and a growth strategy tuned through benchmarking over years of real usage. The implementation here is simpler. That simplicity is the point. Building it gives you answers to questions the standard library normally hides behind a clean API.

get returns Option<&V> because the key might not be there and the value is borrowed from the map. You cannot hold a reference and mutate simultaneously because that would require both an immutable and a mutable borrow of the same structure. The Entry API exists because two-lookup patterns are both slower and semantically weaker than a single-lookup handle to the slot. K: Eq + Hash is required because hashing without equality checking produces a broken map, and the compiler enforces this rather than leaving it to documentation.

None of these issues are specific to Rust. They show up anywhere you are managing memory directly. Rust just forces you to confront them at compile time instead of at runtime.

This is part of the Data Structures in Rust series. The linked list article covers why pointer-based structures fight Rust’s ownership model, and the binary tree article covers why hierarchical ownership works cleanly. LinkedList Binary Tree

If the ownership model behind these examples is still fuzzy, the field guide builds it from the ground up.

$7 — Zero to Rust: A Systems Programmer’s Field Guide You can read the free sample here — Free 20-page sample