HashMap Implementation from Scratch in DSA C - Execution Trace

Concept Flow - HashMap Implementation from Scratch

Initialize HashMap with buckets

↓

Compute hash(key) to find bucket index

↓

Check bucket for key existence

↓

Update value

↓

Done

Shows how a key-value pair is added or updated by hashing the key, locating the bucket, and inserting or updating the node.

Execution Sample

DSA C

hashMapPut(map, "apple", 10);
hashMapPut(map, "banana", 20);
hashMapPut(map, "apple", 30);
hashMapPrint(map);

Inserts 'apple' and 'banana' keys with values, then updates 'apple' value, finally prints the map.

Execution Table

Step	Operation	Bucket Index	Bucket Nodes Before	Action	Bucket Nodes After	Visual State
1	Insert ('apple', 10)	2	[]	Insert new node	[('apple',10)]	[Bucket 2]: ('apple',10) -> null
2	Insert ('banana', 20)	0	[]	Insert new node	[('banana',20)]	[Bucket 0]: ('banana',20) -> null
3	Insert ('apple', 30)	2	[('apple',10)]	Update value	[('apple',30)]	[Bucket 2]: ('apple',30) -> null
4	Print map	-	-	-	-	Bucket 0: ('banana',20) -> null Bucket 2: ('apple',30) -> null
5	End	-	-	-	-	No more operations

💡 All insertions done and map printed

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
map.buckets[0]	[]	[]	[('banana',20)]	[('banana',20)]	[('banana',20)]
map.buckets[2]	[]	[('apple',10)]	[('apple',10)]	[('apple',30)]	[('apple',30)]
map.size	0	1	2	2	2

Key Moments - 3 Insights

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

Because the hash function points to the same bucket and the key is found in that bucket's linked list, we update the existing node's value to avoid duplicate keys, as shown in step 3 of the execution_table.

What happens if two different keys hash to the same bucket?

They are stored in the same bucket as a linked list of nodes. Each node holds a key-value pair. This chaining handles collisions, as seen in steps 1 and 2 where different keys go to different buckets, but if they collided, they would be linked.

Why do we need to compute the bucket index using a hash function?

The hash function converts the key into an index to quickly find the bucket where the key-value pair should be stored or searched, making operations efficient. This is shown in the 'Bucket Index' column in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the bucket index for key 'apple'?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'Bucket Index' column for step 3 in the execution_table.

At which step does the map size increase?

A Step 3 only

B Step 1 and Step 2

C Step 4

D Step 3 and Step 4

💡 Hint

Look at the 'map.size' row in variable_tracker after each step.

If we insert a new key that hashes to bucket 2, what will happen to the bucket nodes?

A The new node will be added to the linked list in bucket 2

B The new node will replace the existing node

C The bucket will be cleared before insertion

D Insertion will fail due to collision

💡 Hint

Recall how collisions are handled by chaining in the execution_table and concept_flow.

Concept Snapshot

HashMap stores key-value pairs using an array of buckets.
Keys are hashed to find bucket index.
If key exists in bucket, update value.
If not, insert new node in bucket's linked list.
Handles collisions by chaining nodes in buckets.
Operations: put, get, remove run in average O(1) time.

Full Transcript

This visual trace shows how a HashMap stores and updates key-value pairs. First, the map is initialized with empty buckets. When inserting a key, the hash function computes the bucket index. If the key is found in that bucket's linked list, its value is updated. Otherwise, a new node is inserted at the bucket. Collisions are handled by chaining nodes in the same bucket. The example inserts 'apple' and 'banana', then updates 'apple'. The final print shows the stored pairs. Variables track bucket contents and map size after each step.