HashMap Implementation from Scratch in DSA Rust - Build from Scratch

HashMap Implementation from Scratch

📖 Scenario: Imagine you want to build a simple phone book app that stores names and phone numbers. To do this efficiently, you decide to create your own HashMap from scratch in Rust, which will help you quickly find a phone number by a person's name.

🎯 Goal: You will build a basic HashMap in Rust that can store key-value pairs (names and phone numbers), handle collisions using chaining, and allow inserting and retrieving values.

📋 What You'll Learn

Create a struct called HashMap with a vector of buckets

Implement a simple hash function for string keys

Add an insert method to add key-value pairs

Add a get method to retrieve values by key

Handle collisions by storing multiple entries in each bucket

💡 Why This Matters

🌍 Real World

HashMaps are used everywhere to store and quickly find data by keys, like phone books, caches, and databases.

💼 Career

Understanding how HashMaps work under the hood helps you write efficient code and debug performance issues in real software projects.

1

Create the basic HashMap structure

Create a struct called HashMap with a field buckets that is a Vec of vectors holding tuples of (String, String). Initialize buckets with 5 empty vectors inside the new function.

DSA Rust

struct HashMap {
    buckets: Vec>,
}

impl HashMap {
    fn new() -> Self {
        // Your code here
    }
}

Hint

Use vec![Vec::new(); 5] to create 5 empty vectors inside the buckets vector.

2

Add a simple hash function

Inside the impl HashMap block, add a private method hash that takes a &str key and returns a usize. The method should sum the bytes of the key and return the sum modulo the number of buckets (5).

DSA Rust

struct HashMap {
    buckets: Vec>,
}

impl HashMap {
    fn new() -> Self {
        let buckets = vec![Vec::new(); 5];
        HashMap { buckets }
    }
}

// Add the hash function below
// Your code here

Hint

Use key.bytes() and fold to sum the byte values of the string.

3

Implement the insert method

Add a public method insert that takes &mut self, a String key, and a String value. Use the hash method to find the bucket index. Append the (key, value) tuple to the bucket vector. If the key already exists in the bucket, update its value instead of adding a new tuple.

DSA Rust

struct HashMap {
    buckets: Vec>,
}

impl HashMap {
    fn new() -> Self {
        let buckets = vec![Vec::new(); 5];
        HashMap { buckets }
    }

    fn hash(&self, key: &str) -> usize {
        let sum = key.bytes().fold(0, |acc, b| acc + b as usize);
        sum % self.buckets.len()
    }

    // Add insert method below
    // Your code here
}

Hint

Loop over the bucket vector with for pair in &mut self.buckets[index] to check for existing keys.

4

Implement the get method and print results

Add a public method get that takes &self and a &str key, and returns an Option<&String>. Use the hash method to find the bucket index. Search the bucket for the key and return Some(&value) if found, otherwise None. Then, create a main function that creates a HashMap, inserts these entries: ("Alice", "1234"), ("Bob", "5678"), ("Charlie", "9012"), and prints the phone number for "Bob" and "Eve" (which is not inserted).

DSA Rust

struct HashMap {
    buckets: Vec>,
}

impl HashMap {
    fn new() -> Self {
        let buckets = vec![Vec::new(); 5];
        HashMap { buckets }
    }

    fn hash(&self, key: &str) -> usize {
        let sum = key.bytes().fold(0, |acc, b| acc + b as usize);
        sum % self.buckets.len()
    }

    fn insert(&mut self, key: String, value: String) {
        let index = self.hash(&key);
        for pair in &mut self.buckets[index] {
            if pair.0 == key {
                pair.1 = value;
                return;
            }
        }
        self.buckets[index].push((key, value));
    }

    // Add get method below
    // Your code here
}

// Add main function below
// Your code here

Hint

Use Option and match to handle the result of get. Print the value if found, or a not found message otherwise.

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