HashMap Implementation from Scratch in DSA Rust

Mental Model

A HashMap stores key-value pairs by turning keys into indexes to quickly find values.

Analogy: Imagine a library where each book's title is turned into a shelf number so you can find the book fast without searching all shelves.

Buckets array:
[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null
Each bucket can hold a linked list of entries (key -> value -> next).

Dry Run Walkthrough

Input: Insert keys and values: (apple, 5), (banana, 3), (grape, 7) into a HashMap with 5 buckets

Goal: Store key-value pairs so we can find values by keys quickly using hashing and handle collisions

Step 1: Hash 'apple' to bucket 0 and insert (apple, 5)

[0] -> (apple -> 5 -> null)
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: We use hash to find bucket 0 and place the first entry there

Step 2: Hash 'banana' to bucket 2 and insert (banana, 3)

[0] -> (apple -> 5 -> null)
[1] -> null
[2] -> (banana -> 3 -> null)
[3] -> null
[4] -> null

Why: Hash 'banana' points to bucket 2, so we add it there

Step 3: Hash 'grape' to bucket 0, collision occurs, add (grape, 7) at bucket 0 linked list head

[0] -> (grape -> 7 -> (apple -> 5 -> null))
[1] -> null
[2] -> (banana -> 3 -> null)
[3] -> null
[4] -> null

Why: Collision handled by chaining: add new entry at bucket 0's linked list head

Result:

[0] -> (grape -> 7 -> (apple -> 5 -> null))
[1] -> null
[2] -> (banana -> 3 -> null)
[3] -> null
[4] -> null

Annotated Code

DSA Rust

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

struct Entry<K, V> {
    key: K,
    value: V,
    next: Option<Box<Entry<K, V>>>,
}

struct HashMap<K, V> {
    buckets: Vec<Option<Box<Entry<K, V>>>>,
    capacity: usize,
}

impl<K: Hash + Eq, V> HashMap<K, V> {
    fn new(capacity: usize) -> Self {
        let mut buckets = Vec::with_capacity(capacity);
        buckets.resize_with(capacity, || None);
        Self { buckets, capacity }
    }

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

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

        while let Some(ref mut entry) = current {
            if entry.key == key {
                entry.value = value; // update existing key
                return;
            }
            current = &mut entry.next;
        }

        let new_entry = Box::new(Entry { key, value, next: self.buckets[index].take() });
        self.buckets[index] = Some(new_entry);
    }

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

        while let Some(ref entry) = current {
            if &entry.key == key {
                return Some(&entry.value);
            }
            current = &entry.next;
        }
        None
    }
}

fn main() {
    let mut map = HashMap::new(5);
    map.insert("apple", 5);
    map.insert("banana", 3);
    map.insert("grape", 7);

    println!("apple -> {:?}", map.get(&"apple"));
    println!("banana -> {:?}", map.get(&"banana"));
    println!("grape -> {:?}", map.get(&"grape"));
    println!("orange -> {:?}", map.get(&"orange"));
}

let index = self.hash(&key);

compute bucket index by hashing key

while let Some(ref mut entry) = current { if entry.key == key { entry.value = value; return; } current = &mut entry.next; }

traverse bucket linked list to update value if key exists

let new_entry = Box::new(Entry { key, value, next: self.buckets[index].take() }); self.buckets[index] = Some(new_entry);

insert new entry at head of bucket linked list to handle collisions

while let Some(ref entry) = current { if &entry.key == key { return Some(&entry.value); } current = &entry.next; }

search bucket linked list for key to get value

Output

apple -> Some(5)

banana -> Some(3)

grape -> Some(7)

orange -> None

Complexity Analysis

Time: O(n/k) average, where n is number of entries and k is buckets, because each bucket holds few entries on average

Space: O(n) because we store all entries plus bucket array

vs Alternative: Compared to array search O(n), hashing reduces average search to O(1) by direct bucket indexing

Edge Cases

Inserting duplicate key

Value is updated instead of adding new entry

DSA Rust

if entry.key == key { entry.value = value; return; }

Getting value for non-existent key

Returns None gracefully

DSA Rust

while let Some(ref entry) = current { ... } None

Empty HashMap (no entries)

Get returns None, insert adds first entry

DSA Rust

buckets vector initialized with None entries

When to Use This Pattern

When you need fast key-value lookup and want to avoid slow linear search, use a HashMap pattern with hashing and collision handling.

Common Mistakes

Mistake: Not handling collisions, overwriting entries in buckets
Fix: Use linked list chaining or another collision method to store multiple entries per bucket

Mistake: Not updating value when inserting duplicate key
Fix: Check keys during insert and update value if key exists

Summary

Stores key-value pairs using hashing to find bucket indexes quickly.

Use when you want fast average lookup, insert, and update by key.

The key insight is to convert keys to bucket indexes and handle collisions with linked lists.

Practice

1. What is the main purpose of a HashMap in data structures?

easy

A. To store elements in a queue-like manner

B. To store elements in sorted order

C. To store key-value pairs for fast lookup

D. To store elements in a stack-like manner

Solution

1. Step 1: Understand HashMap functionality

   A HashMap stores data as key-value pairs, allowing quick access by key.

2. Step 2: Compare with other data structures

   Unlike stacks or queues, HashMaps do not maintain order but focus on fast lookup.

3. Final Answer:

   To store key-value pairs for fast lookup -> Option C

4. Quick Check:

   HashMap = key-value fast access [OK]

Hint: HashMap = fast key-value storage [OK]

Common Mistakes:

• Confusing HashMap with sorted structures
• Thinking HashMap stores elements in order
• Mixing HashMap with stack or queue behavior

2. Which of the following is the correct Rust syntax to create an empty HashMap from scratch?

easy

A. let map = HashMap::empty();

B. let map = new HashMap();

C. let map = HashMap();

D. let map = HashMap::new();

Solution

1. Step 1: Recall Rust HashMap creation syntax

   Rust uses HashMap::new() to create an empty HashMap.

2. Step 2: Check other options for Rust correctness

   Options B, C, and D are not valid Rust syntax for HashMap creation.

3. Final Answer:

   let map = HashMap::new(); -> Option D

4. Quick Check:

   Rust HashMap empty = HashMap::new() [OK]

Hint: Use HashMap::new() to create empty map [OK]

Common Mistakes:

• Using constructor syntax like new HashMap()
• Calling HashMap() without ::new()
• Using non-existent methods like empty()

3. Consider this simplified Rust code snippet for a custom HashMap insert method:

let mut map = MyHashMap::new();
map.insert("apple", 3);
map.insert("banana", 5);
map.insert("apple", 7);
println!("{:?}", map.get("apple"));

What will be printed?

medium

A. Some(3)

B. Some(7)

C. None

D. Some(5)

Solution

1. Step 1: Analyze insertions for key "apple"

   First insert sets "apple" to 3, second insert updates "apple" to 7.

2. Step 2: Check the get method output

   Getting "apple" returns the latest value, which is 7, wrapped in Some.

3. Final Answer:

   Some(7) -> Option B

4. Quick Check:

   Last insert value = get output [OK]

Hint: Last inserted value for key is returned [OK]

Common Mistakes:

• Assuming first inserted value remains
• Confusing None with Some value
• Mixing values of different keys

4. Given this Rust snippet for a custom HashMap insert method, what is the bug?

fn insert(&mut self, key: K, value: V) {
    let index = self.hash(&key) % self.buckets.len();
    if self.buckets[index].is_empty() {
        self.buckets[index].push((key, value));
    } else {
        self.buckets[index].push((key, value));
    }
}

medium

A. It does not update value if key exists, causing duplicates

B. It uses wrong hash function signature

C. It does not handle empty buckets correctly

D. It forgets to resize buckets when full

Solution

1. Step 1: Review insert logic for existing keys

   The code always pushes new (key, value) pairs without checking for existing keys.

2. Step 2: Identify consequence of missing update

   This causes duplicate keys in the same bucket, breaking expected HashMap behavior.

3. Final Answer:

   It does not update value if key exists, causing duplicates -> Option A

4. Quick Check:

   Insert must update existing key, not just push [OK]

Hint: Check for existing key before inserting [OK]

Common Mistakes:

• Ignoring key existence before insert
• Assuming push replaces existing entries
• Missing bucket resizing logic

5. You are implementing a custom HashMap in Rust with separate chaining. Which approach best handles collisions and updates existing keys efficiently?

hard

A. Store key-value pairs in a vector at each bucket; on insert, search vector for key to update or append

B. Use a single vector for all keys without hashing; append all pairs sequentially

C. Replace entire bucket vector on each insert without checking keys

D. Use a linked list but never check for existing keys before inserting

Solution

1. Step 1: Understand separate chaining collision handling

   Separate chaining uses a list (vector) at each bucket to store multiple key-value pairs.

2. Step 2: Efficient insert requires checking existing keys

   Before inserting, search the bucket's vector for the key to update value or append if not found.

3. Step 3: Evaluate options

   Store key-value pairs in a vector at each bucket; on insert, search vector for key to update or append correctly describes this approach; others ignore key checks or hashing.

4. Final Answer:

   Store key-value pairs in a vector at each bucket; on insert, search vector for key to update or append -> Option A

5. Quick Check:

   Separate chaining + key check = efficient insert [OK]

Hint: Search bucket vector for key before insert [OK]

Common Mistakes:

• Ignoring key existence in bucket
• Not using hashing for bucket selection
• Replacing bucket data blindly