I've always felt that the best way to truly understand how a HashMap works under the hood is to build a stripped-down version of one. We aren't going to beat the standard library's performance—std::collections::HashMap uses a sophisticated algorithm called Swiss Tables—but for our purposes, we'll build a classic hash table using separate chaining. This is the "textbook" approach where each slot in our array (a bucket) holds a list of entries that hashed to the same index.

Setting up the bucket array

First, we need a structure. I want this to be generic so it can handle different types of keys and values, but we have to ensure the key can be hashed. In Rust, that means the key must implement Hash and Eq. I'll use a Vec of Vecs for my buckets. Each inner Vec will store tuples of (K, V).

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

struct SimpleHash<K, V> {
    buckets: Vec<Vec<(K, V)>>,
    capacity: usize,
}

impl<K: Hash + Eq, V> SimpleHash<K, V> {
    fn new(capacity: usize) -> Self {
        let mut buckets = Vec::with_capacity(capacity);
        for _ in 0..capacity {
            buckets.push(Vec::new());
        }
        SimpleHash { buckets, capacity }
    }
}

Mapping keys to indices

Now we need a way to turn a key into an index within our buckets vector. I'll create a private helper method for this. I'm using DefaultHasher here because it's built-in and reliable. I'll feed the key into the hasher and then use the modulo operator to keep the result within the bounds of our capacity.

impl<K: Hash + Eq, V> SimpleHash<K, V> {
    // ... new() method ...

    fn calculate_hash(&self, key: &K) -> usize {
        let mut s = DefaultHasher::new();
        key.hash(&mut s);
        (s.finish() as usize) % self.capacity
    }
}

The mistake: Ignoring existing keys

When I first sketched out the insert method, I did something lazy. I just calculated the index and pushed the key-value pair into the bucket. It felt efficient at the time, but here is what that looked like:

// WRONG VERSION - Don't do this!
fn insert(&mut self, key: K, value: V) {
    let index = self.calculate_hash(&key);
    self.buckets[index].push((key, value));
}

I quickly realized the problem when I tried to update a value. If I inserted ("user_1", "Alice") and then inserted ("user_1", "Bob"), my bucket now contains both. When I call get, I'll likely find "Alice" first, and "Bob" will just sit there taking up space. That's not a map; that's just a weirdly organized list. I need to check if the key already exists and update it in place.

Fixing the insertion logic

To fix this, I'll iterate through the bucket. If I find the key, I'll update the value and return early. If I reach the end of the bucket without finding it, only then will I push a new pair. This keeps our data clean.

fn insert(&mut self, key: K, value: V) {
    let index = self.calculate_hash(&key);
    let bucket = &mut self.buckets[index];

    for pair in bucket.iter_mut() {
        if pair.0 == key {
            pair.1 = value;
            return;
        }
    }
    bucket.push((key, value));
}

Retrieving values with references

Finally, we need a get method. Since we don't want to take ownership of the value (which would remove it from the table), we return an Option<&V>. This is the standard Rust pattern for lookups.

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

    for (k, v) in bucket {
        if k == key {
            return Some(v);
        }
    }
    None
}

And there we have it. It's not the fastest implementation in the world, but it demonstrates the core cycle of hashing: Key → Hash → Index → Bucket Search. By using Vec<Vec<(K, V)>>, we've handled collisions gracefully via separate chaining.

📋 Practical Task

Implementing a Remove Method for SimpleHash

Now it's your turn. The SimpleHash implementation we built is missing a crucial piece of functionality: the ability to delete a key-value pair.

Your task is to add a remove method to the SimpleHash struct. The method should:

• Take a reference to a key &K as an argument.
• Calculate the correct bucket index.
• Find the element with the matching key within that bucket.
• Remove the element from the Vec and return the value V wrapped in Some().
• Return None if the key was not found.

Hint: Look into the Vec::retain method or use position() combined with swap_remove() or remove() for efficient deletion from a vector.