HashMap Implementation from Scratch in DSA Go - Execution Trace

Concept Flow - HashMap Implementation from Scratch

Start

↓

Compute hash(key)

↓

Find bucket index = hash % bucket_count

↓

Check bucket linked list

↓

Key found?

↓

Update value

↓

Done

↓

Add new node at bucket head

↓

Done

The flow shows how a key is hashed to find a bucket, then the bucket's linked list is searched to update or add the key-value pair.

Execution Sample

DSA Go

hash := hashFunction(key)
index := hash % bucketCount
node := buckets[index]
for node != nil {
  if node.key == key { node.value = value; return }
  node = node.next
}
buckets[index] = newNode(key, value, buckets[index])

This code inserts or updates a key-value pair in the hashmap by hashing the key, finding the bucket, searching the linked list, and adding or updating the node.

Execution Table

Step	Operation	Key	Hash	Bucket Index	Bucket State Before	Pointer Changes	Bucket State After	Visual State
1	Compute hash	apple	930292	-	-	-	-	Buckets: [nil, nil, nil, nil, nil]
2	Calculate bucket index	apple	930292	2	-	-	-	Buckets: [nil, nil, nil, nil, nil]
3	Check bucket linked list	apple	930292	2	nil	-	-	Buckets: [nil, nil, nil, nil, nil]
4	Add new node	apple	930292	2	nil	buckets[2] = newNode(apple, 5, nil)	Node(apple:5) -> nil	Buckets: [nil, nil, Node(apple:5), nil, nil]
5	Compute hash	banana	482910	-	-	-	-	Buckets: [nil, nil, Node(apple:5), nil, nil]
6	Calculate bucket index	banana	482910	0	-	-	-	Buckets: [nil, nil, Node(apple:5), nil, nil]
7	Check bucket linked list	banana	482910	0	nil	-	-	Buckets: [nil, nil, Node(apple:5), nil, nil]
8	Add new node	banana	482910	0	nil	buckets[0] = newNode(banana, 3, nil)	Node(banana:3) -> nil	Buckets: [Node(banana:3), nil, Node(apple:5), nil, nil]
9	Compute hash	apple	930292	-	-	-	-	Buckets: [Node(banana:3), nil, Node(apple:5), nil, nil]
10	Calculate bucket index	apple	930292	2	-	-	-	Buckets: [Node(banana:3), nil, Node(apple:5), nil, nil]
11	Check bucket linked list	apple	930292	2	Node(apple:5) -> nil	-	-	Buckets: [Node(banana:3), nil, Node(apple:5), nil, nil]
12	Key found, update value	apple	930292	2	Node(apple:5) -> nil	node.value = 10	Node(apple:10) -> nil	Buckets: [Node(banana:3), nil, Node(apple:10), nil, nil]
13	End	-	-	-	-	-	-	Insertion/Update complete

💡 After updating or adding the node, the operation ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	After Step 12	Final
hash	-	930292	930292	930292	482910	482910	930292	930292	-
index	-	-	2	2	0	0	2	2	-
buckets[0]	nil	nil	nil	nil	nil	nil	Node(banana:3) -> nil	Node(banana:3) -> nil	Node(banana:3) -> nil
buckets[2]	nil	nil	nil	Node(apple:5) -> nil	Node(apple:5) -> nil	Node(apple:5) -> nil	Node(apple:5) -> nil	Node(apple:10) -> nil	Node(apple:10) -> nil
node	nil	nil	nil	nil	nil	nil	Node(apple:5)	Node(apple:10)	-

Key Moments - 3 Insights

Why do we check the linked list in the bucket instead of just placing the node directly?

Because multiple keys can hash to the same bucket index (collision). The linked list stores all nodes in that bucket. See execution_table rows 3, 7, and 11 where the bucket is checked before adding or updating.

What happens if the key already exists in the bucket?

We update the existing node's value instead of adding a new node. This is shown in execution_table row 12 where the value for 'apple' changes from 5 to 10.

Why do we add the new node at the head of the linked list?

Adding at the head is simple and fast because we just point the new node's next to the current head. This is shown in rows 4 and 8 where new nodes are added at the start of the bucket's list.

Visual Quiz - 3 Questions

Look at the execution_table, what is the bucket index for the key 'banana'?

A 2

B 0

C 3

D 1

💡 Hint

Check the 'Bucket Index' column for 'banana' in rows 6 and 7.

At which step does the value for 'apple' get updated?

A Step 4

B Step 8

C Step 12

D Step 10

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns around step 12.

If we add a new key that hashes to bucket 2, where will the new node be placed?

A At the head of the linked list in bucket 2

B At the end of the linked list in bucket 2

C In a new bucket after bucket 2

D It replaces the existing node in bucket 2

💡 Hint

Refer to rows 4 and 8 where new nodes are added at the head of the bucket's linked list.

Concept Snapshot

HashMap stores key-value pairs using an array of buckets.
Keys are hashed to an index: index = hash(key) % bucket_count.
Each bucket holds a linked list to handle collisions.
Insert: hash key, find bucket, search list, update or add node at head.
Update: find node by key, change value.
This keeps insert and lookup efficient on average.

Full Transcript

This visualization shows how a HashMap works internally by using an array of buckets and linked lists to handle collisions. When inserting or updating a key-value pair, the key is hashed to find the bucket index. The bucket is a linked list where nodes store keys and values. The code checks if the key exists in the list; if yes, it updates the value. If not, it adds a new node at the head of the list. The execution table traces each step, showing how buckets and nodes change. The variable tracker follows key variables like hash, index, and bucket contents. Key moments clarify why linked lists are needed, how updates happen, and why new nodes are added at the head. The quiz tests understanding of bucket indexing, update steps, and node placement. The snapshot summarizes the core idea: hashing keys to buckets, handling collisions with linked lists, and efficient insert/update operations.

Practice

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

easy

A. To store key-value pairs for fast data retrieval

B. To store elements in a sorted order

C. To perform mathematical calculations

D. To store data sequentially like an array

Solution

1. Step 1: Understand the role of HashMap

   A HashMap stores data as key-value pairs, allowing quick access to values using keys.

2. Step 2: Compare with other data structures

   Unlike arrays or lists, HashMaps do not store data sequentially or sorted but focus on fast lookup.

3. Final Answer:

   To store key-value pairs for fast data retrieval -> Option A

4. Quick Check:

   HashMap = key-value fast access [OK]

Hint: HashMap = key-value pairs for quick lookup [OK]

Common Mistakes:

• Confusing HashMap with arrays or lists
• Thinking HashMap stores data in order
• Assuming HashMap is for mathematical operations

2. Which of the following is the correct way to declare a HashMap in Go?

easy

A. var m = make(map[string]int)

B. var m map[string]int = map[string]int

C. var m = map[string]int()

D. var m map[string]int

Solution

1. Step 1: Understand Go map declaration

   In Go, maps are created using make function: make(map[keyType]valueType).

2. Step 2: Check each option

   A declares a nil map which cannot be used for assignments. B has invalid syntax (cannot assign type as value). C has incorrect syntax (cannot call map type as function). D uses make correctly.

3. Final Answer:

   var m = make(map[string]int) -> Option A

4. Quick Check:

   Use make() to create maps in Go [OK]

Hint: Use make(map[key]value) to create HashMap in Go [OK]

Common Mistakes:

• Declaring without initializing (nil map)
• Using map type without literal or make
• Trying to call map as a function

3. What will be the output of the following Go code snippet implementing a simple HashMap?

package main
import "fmt"
func main() {
  m := make(map[string]int)
  m["apple"] = 5
  m["banana"] = 3
  m["apple"] = 7
  fmt.Println(m["apple"])
}

medium

A. 5

B. Compilation error

C. 0

D. 7

Solution

1. Step 1: Analyze map insertions

   Initially, "apple" is set to 5, then updated to 7, so the last value is 7.

2. Step 2: Print the value for key "apple"

   Printing m["apple"] outputs the updated value 7.

3. Final Answer:

   7 -> Option D

4. Quick Check:

   Last assigned value for key is returned [OK]

Hint: Last value assigned to key is stored [OK]

Common Mistakes:

• Assuming first value remains after update
• Confusing zero value with stored value
• Expecting compilation error due to reassignment

4. Identify the error in this Go code implementing a HashMap:

package main
import "fmt"
func main() {
  var m map[string]int
  m["key"] = 10
  fmt.Println(m["key"])
}

medium

A. Key type is incorrect

B. Map is not initialized before use

C. Value type is incorrect

D. Print statement syntax error

Solution

1. Step 1: Check map initialization

   The map variable m is declared but not initialized with make(), so it is nil.

2. Step 2: Understand assignment to nil map

   Assigning to a nil map causes runtime panic because map is not ready to store data.

3. Final Answer:

   Map is not initialized before use -> Option B

4. Quick Check:

   Maps must be initialized with make() before assignment [OK]

Hint: Always initialize map with make() before adding keys [OK]

Common Mistakes:

• Forgetting to initialize map before use
• Assuming declaration alone creates map
• Confusing map initialization with slice

5. You want to implement a HashMap from scratch in Go without using built-in maps. Which of the following is the best approach to handle collisions?

hard

A. Ignore collisions and store only one key-value pair per bucket

B. Overwrite existing key-value pair without checking

C. Use a linked list at each bucket to store multiple key-value pairs

D. Use an array of fixed size without hashing keys

Solution

1. Step 1: Understand collision in HashMap

   When two keys hash to the same bucket, collision occurs and must be handled to store both pairs.

2. Step 2: Evaluate collision handling methods

   Using a linked list at each bucket allows storing multiple pairs safely. Overwriting loses data, ignoring collisions loses data, and fixed arrays without hashing lose efficiency.

3. Final Answer:

   Use a linked list at each bucket to store multiple key-value pairs -> Option C

4. Quick Check:

   Separate chaining with linked lists handles collisions [OK]

Hint: Use linked lists per bucket to handle collisions [OK]

Common Mistakes:

• Overwriting values on collision
• Ignoring collisions causing data loss
• Not using hashing for key distribution