HashMap Implementation from Scratch in DSA Rust - Execution Trace

Concept Flow - HashMap Implementation from Scratch

Start

↓

Compute hash(key)

↓

Find bucket index = hash % bucket_count

↓

Check bucket for key

↓

Key found?

Yes→Update value

↓

Insert new key-value pair

↓

Done

The HashMap stores key-value pairs by hashing the key to find a bucket, then inserts or updates the pair in that bucket.

Execution Sample

DSA Rust

let mut hash_map = HashMap::new();
hash_map.insert("apple", 3);
hash_map.insert("banana", 5);
hash_map.insert("apple", 7);
let value = hash_map.get("apple");

This code creates a HashMap, inserts two keys with values, updates one key, and retrieves a value.

Execution Table

Step	Operation	Bucket Index	Bucket Content Before	Action	Bucket Content After	Visual State
1	Create new HashMap	-	[]	Initialize empty buckets	[[], [], [], [], []]	[[], [], [], [], []]
2	Insert ("apple", 3)	0	[]	Insert new pair	[[("apple", 3)], [], [], [], []]	[(apple,3)] -> [] -> [] -> [] -> []
3	Insert ("banana", 5)	4	[]	Insert new pair	[[("apple", 3)], [], [], [], [("banana", 5)]]	[(apple,3)] -> [] -> [] -> [] -> [(banana,5)]
4	Insert ("apple", 7)	0	[("apple", 3)]	Update value for key "apple"	[[("apple", 7)], [], [], [], [("banana", 5)]]	[(apple,7)] -> [] -> [] -> [] -> [(banana,5)]
5	Get value for "apple"	0	[("apple", 7)]	Return value 7	No change	[(apple,7)] -> [] -> [] -> [] -> [(banana,5)]
6	End	-	-	-	-	Final HashMap state as above

💡 All operations complete; final HashMap contains updated and inserted key-value pairs.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
hash_map.buckets	[[], [], [], [], []]	[[("apple", 3)], [], [], [], []]	[[("apple", 3)], [], [], [], [("banana", 5)]]	[[("apple", 7)], [], [], [], [("banana", 5)]]	[[("apple", 7)], [], [], [], [("banana", 5)]]	[[("apple", 7)], [], [], [], [("banana", 5)]]
value (get)	None	None	None	None	7	7

Key Moments - 3 Insights

Why do we update the value when the key already exists instead of adding a new pair?

Because the HashMap stores unique keys, so when the key "apple" is found in the bucket (see step 4 in execution_table), we replace its value to keep only one entry per key.

How do we find the correct bucket for a key?

We compute the hash of the key and then use modulo with the number of buckets to find the bucket index (shown in the 'Bucket Index' column in execution_table).

What happens if two keys hash to the same bucket?

Both key-value pairs are stored in the same bucket list. We check each pair in that bucket to find or update the key (collision handling by chaining).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the bucket content after updating "apple"?

A [[("apple", 7)], [], [], [], [("banana", 5)]]

B [[("apple", 3)], [], [], [], [("banana", 5)]]

C [[], [], [], [], [("banana", 5)]]

D [[("banana", 5)], [], [], [], [("apple", 7)]]

💡 Hint

Check the 'Bucket Content After' column at step 4 in execution_table.

At which step does the HashMap insert the key "banana"?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'Operation' and 'Bucket Content After' columns in execution_table.

If the number of buckets was increased, how would the bucket index for "apple" change?

A It would stay the same

B It would be hash(key) % new_bucket_count, possibly different

C It would always be zero

D It would be the hash value directly

💡 Hint

Refer to the concept_flow where bucket index is computed as hash % bucket_count.

Concept Snapshot

HashMap stores key-value pairs using hashing.
Compute hash(key) and find bucket index = hash % bucket_count.
Insert new pair or update existing key's value in bucket.
Handles collisions by chaining (list in buckets).
Get operation searches bucket for key and returns value.
Efficient average O(1) insert and lookup.

Full Transcript

This visual trace shows how a HashMap works internally. We start by creating an empty HashMap with buckets. When inserting a key-value pair, we compute the hash of the key and find the bucket index by taking modulo with the number of buckets. If the key is not in the bucket, we add the pair. If the key exists, we update its value. For example, inserting "apple" with 3 stores it in bucket 0. Inserting "banana" with 5 goes to bucket 4. Updating "apple" to 7 replaces the old value in bucket 0. Getting "apple" returns 7. The variable tracker shows how buckets change after each step. Key moments clarify why updates happen and how collisions are handled. The quiz tests understanding of bucket contents and hashing. This is a simple but powerful data structure for fast key-value storage.

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