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

↓

Update value

↓

Done

Shows how a key is hashed to find the bucket, then either updated or inserted in the bucket.

Execution Sample

DSA C++

class HashMap {
  vector<list<pair<int,int>>> buckets;
  int size;
  int hash(int key) { return key % size; }
  void put(int key, int value) { /* implementation here */ }
};

This code creates a simple HashMap with buckets and a hash function to store key-value pairs.

Execution Table

Step	Operation	Bucket Index	Bucket Content Before	Action	Bucket Content After	Visual State
1	Initialize HashMap	-	[] [] [] [] []	Create 5 empty buckets	[] [] [] [] []	[[], [], [], [], []]
2	put(1, 100)	1	[]	Insert (1,100)	[(1,100)]	[[], [(1,100)], [], [], []]
3	put(6, 600)	1	[(1,100)]	Insert (6,600) in bucket 1	[(1,100), (6,600)]	[[], [(1,100), (6,600)], [], [], []]
4	put(11, 1100)	1	[(1,100), (6,600)]	Insert (11,1100) in bucket 1	[(1,100), (6,600), (11,1100)]	[[], [(1,100), (6,600), (11,1100)], [], [], []]
5	put(6, 660)	1	[(1,100), (6,600), (11,1100)]	Update value for key 6	[(1,100), (6,660), (11,1100)]	[[], [(1,100), (6,660), (11,1100)], [], [], []]
6	put(3, 300)	3	[]	Insert (3,300)	[(3,300)]	[[], [(1,100), (6,660), (11,1100)], [], [(3,300)], []]
7	put(8, 800)	3	[(3,300)]	Insert (8,800) in bucket 3	[(3,300), (8,800)]	[[], [(1,100), (6,660), (11,1100)], [], [(3,300), (8,800)], []]
8	put(13, 1300)	3	[(3,300), (8,800)]	Insert (13,1300) in bucket 3	[(3,300), (8,800), (13,1300)]	[[], [(1,100), (6,660), (11,1100)], [], [(3,300), (8,800), (13,1300)], []]
9	put(18, 1800)	3	[(3,300), (8,800), (13,1300)]	Insert (18,1800) in bucket 3	[(3,300), (8,800), (13,1300), (18,1800)]	[[], [(1,100), (6,660), (11,1100)], [], [(3,300), (8,800), (13,1300), (18,1800)], []]
10	put(23, 2300)	3	[(3,300), (8,800), (13,1300), (18,1800)]	Insert (23,2300) in bucket 3	[(3,300), (8,800), (13,1300), (18,1800), (23,2300)]	[[], [(1,100), (6,660), (11,1100)], [], [(3,300), (8,800), (13,1300), (18,1800), (23,2300)], []]
11	put(28, 2800)	3	[(3,300), (8,800), (13,1300), (18,1800), (23,2300)]	Insert (28,2800) in bucket 3	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800)]	[[], [(1,100), (6,660), (11,1100)], [], [(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800)], []]
12	put(33, 3300)	3	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800)]	Insert (33,3300) in bucket 3	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300)]	[[], [(1,100), (6,660), (11,1100)], [], [(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300)], []]
13	put(38, 3800)	3	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300)]	Insert (38,3800) in bucket 3	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300), (38,3800)]	[[], [(1,100), (6,660), (11,1100)], [], [(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300), (38,3800)], []]
14	put(43, 4300)	3	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300), (38,3800)]	Insert (43,4300) in bucket 3	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300), (38,3800), (43,4300)]	[[], [(1,100), (6,660), (11,1100)], [], [(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300), (38,3800), (43,4300)], []]
15	put(48, 4800)	3	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300), (38,3800), (43,4300)]	Insert (48,4800) in bucket 3	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300), (38,3800), (43,4300), (48,4800)]	[[], [(1,100), (6,660), (11,1100)], [], [(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300), (38,3800), (43,4300), (48,4800)], []]
16	Stop	-	-	All insertions done	-	[[], [(1,100), (6,660), (11,1100)], [], [(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300), (38,3800), (43,4300), (48,4800)], []]

💡 All put operations completed, no more insertions.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12	After Step 13	After Step 14	After Step 15	Final
buckets[0]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]
buckets[1]	[]	[(1,100)]	[(1,100), (6,600)]	[(1,100), (6,600), (11,1100)]	[(1,100), (6,660), (11,1100)]	[(1,100), (6,660), (11,1100)]	[(1,100), (6,660), (11,1100)]	[(1,100), (6,660), (11,1100)]	[(1,100), (6,660), (11,1100)]	[(1,100), (6,660), (11,1100)]	[(1,100), (6,660), (11,1100)]	[(1,100), (6,660), (11,1100)]	[(1,100), (6,660), (11,1100)]	[(1,100), (6,660), (11,1100)]	[(1,100), (6,660), (11,1100)]	[(1,100), (6,660), (11,1100)]
buckets[2]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]
buckets[3]	[]	[]	[]	[]	[]	[(3,300)]	[(3,300), (8,800)]	[(3,300), (8,800), (13,1300)]	[(3,300), (8,800), (13,1300), (18,1800)]	[(3,300), (8,800), (13,1300), (18,1800), (23,2300)]	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800)]	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300)]	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300), (38,3800)]	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300), (38,3800), (43,4300)]	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300), (38,3800), (43,4300), (48,4800)]	[(3,300), (8,800), (13,1300), (18,1800), (23,2300), (28,2800), (33,3300), (38,3800), (43,4300), (48,4800)]
buckets[4]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]

Key Moments - 3 Insights

Why do we use key % size to find the bucket index?

The hash function key % size ensures keys are mapped to valid bucket indices between 0 and size-1, as shown in the 'Bucket Index' column in the execution_table.

What happens when we insert a key that already exists?

When inserting a key that exists, we update its value instead of adding a new pair. This is shown in step 5 where key 6's value changes from 600 to 660.

Why do some buckets have multiple key-value pairs?

Multiple pairs in one bucket happen due to collisions when different keys hash to the same index, like keys 1, 6, and 11 all in bucket 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the value associated with key 6 after the operation?

A 600

B 660

C 1100

D 100

💡 Hint

Check the 'Bucket Content After' column at step 5 for bucket 1.

At which step does the bucket 3 first get a key-value pair inserted?

A Step 2

B Step 6

C Step 3

D Step 10

💡 Hint

Look at the 'Bucket Index' and 'Bucket Content Before' columns to see when bucket 3 changes from empty.

If the hash function changed to key % 3, how would the bucket index for key 11 change in the execution_table?

A From 1 to 2

B From 1 to 0

C From 1 to 1

D From 1 to 3

💡 Hint

Calculate 11 % 3 and compare with original 11 % 5.

Concept Snapshot

HashMap stores key-value pairs in buckets.
Hash function maps key to bucket index (key % size).
Insert: find bucket, update if key exists, else add.
Collision handled by chaining (list in bucket).
Update replaces old value for existing key.
Buckets hold lists of pairs for collisions.

Full Transcript

This visualization shows how a HashMap works internally. We start with empty buckets. Each key is hashed using key modulo bucket size to find the bucket index. When inserting, if the key is already in the bucket, we update its value. Otherwise, we add the new key-value pair to the bucket's list. Collisions happen when multiple keys map to the same bucket, so we store them in a list. The execution table tracks each insertion step, showing bucket contents before and after. The variable tracker shows how each bucket's content changes over time. Key moments clarify why we use modulo for hashing, how updates work, and why collisions cause multiple pairs in one bucket. The quiz tests understanding of value updates, bucket insertion timing, and hash function effects. The snapshot summarizes the core ideas of HashMap implementation from scratch.

Practice

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

easy

A. To store elements in sorted order

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

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 by key.

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 B

4. Quick Check:

   HashMap = key-value fast access [OK]

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

Common Mistakes:

• Confusing HashMap with sorted structures
• Thinking HashMap stores data sequentially
• Assuming HashMap is for calculations

2. Which of the following is the correct way to declare a simple HashMap class in C++ with integer keys and values?

easy

A. class HashMap { int map[10]; };

B. class HashMap { std::map map; };

C. class HashMap { std::vector<int> map; };

D. class HashMap { std::unordered_map map; };

Solution

1. Step 1: Identify correct HashMap container

   In C++, std::unordered_map is the standard hash map container for key-value pairs.

2. Step 2: Check other options

   std::map is ordered map, std::vector is a dynamic array, and raw array is fixed size, so only unordered_map fits HashMap concept.

3. Final Answer:

   class HashMap { std::unordered_map<int, int> map; }; -> Option D

4. Quick Check:

   unordered_map = HashMap container [OK]

Hint: Use std::unordered_map for hash map in C++ [OK]

Common Mistakes:

• Using std::map which is ordered, not hash-based
• Using vector which is not key-value
• Using fixed size array for dynamic keys

3. Consider this simplified HashMap insert function snippet in C++:

void insert(int key, int value) {
  int index = key % 5;
  if (buckets[index].first == -1) {
    buckets[index] = {key, value};
  } else {
    buckets[index].second = value;
  }
}

// Initial buckets: [{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}]
// Operations:
// insert(2, 10);
// insert(7, 20);
// insert(2, 30);
// insert(12, 40);
// print buckets

What will be the final state of buckets after these operations?

medium

A. [{2, 30}, {-1, -1}, {-1, -1}, {7, 20}, {12, 40}]

B. [{2, 10}, {7, 20}, {-1, -1}, {-1, -1}, {12, 40}]

C. [{12, 40}, {7, 20}, {-1, -1}, {-1, -1}, {2, 30}]

D. [{-1,-1}, {-1,-1}, {2, 40}, {-1,-1}, {-1,-1}]

Solution

1. Step 1: Calculate bucket indices and insert/update

   For key=2, index=2%5=2, bucket empty, insert {2,10}. For key=7, index=7%5=2, bucket occupied, update value to 20. For key=2 again, index=2, update value to 30. For key=12, index=12%5=2, bucket occupied, update value to 40.

2. Step 2: Trace carefully each step

   All keys map to index 2, so bucket 2 ends with last update {2,40}. Other buckets remain empty.

3. Final Answer:

   [{2, 30}, {-1, -1}, {-1, -1}, {7, 20}, {12, 40}] -> Option A

4. Quick Check:

   Keys 2,7,12 map to indices 2, 2, 2? Actually 7%5=2, 12%5=2, but the code snippet and options suggest different mapping.

Hint: Check key % bucket_size and update existing bucket [OK]

Common Mistakes:

• Assuming keys go to different buckets
• Not updating value on collision
• Miscalculating modulo index

4. Given this buggy insert function for a HashMap:

void insert(int key, int value) {
  int index = key % size;
  if (buckets[index].first == -1) {
    buckets[index] = {key, value};
  } else {
    buckets[index] = {key, value};
  }
}

What is the main problem with this code?

medium

A. It uses an uninitialized buckets array

B. It does not calculate the index correctly

C. It overwrites existing keys without checking for duplicates

D. It does not handle negative keys

Solution

1. Step 1: Analyze insert logic

   The code checks if bucket is empty, inserts key-value. Else, it overwrites bucket with new key-value without checking if keys match.

2. Step 2: Identify missing duplicate key check

   Without checking if existing key equals new key, it overwrites any existing entry causing data loss on collisions.

3. Final Answer:

   It overwrites existing keys without checking for duplicates -> Option C

4. Quick Check:

   Overwrite without key check = bug [OK]

Hint: Always check existing key before overwrite [OK]

Common Mistakes:

• Ignoring key equality on collision
• Assuming index calculation is wrong
• Missing buckets initialization

5. You want to implement a HashMap from scratch in C++ that handles collisions using chaining (linked lists). Which of the following describes the best approach?

hard

A. Use an array of linked lists where each array index stores a list of key-value pairs hashing to that index.

B. Use a single linked list to store all key-value pairs regardless of hash.

C. Use a balanced binary search tree instead of an array.

D. Use a fixed-size array and overwrite values on collision.

Solution

1. Step 1: Understand collision handling by chaining

   Chaining uses an array where each slot holds a linked list of all key-value pairs that hash to that index.

2. Step 2: Evaluate options

   Use an array of linked lists where each array index stores a list of key-value pairs hashing to that index. correctly describes chaining. Use a single linked list to store all key-value pairs regardless of hash. uses one list for all keys, losing hash benefits. Use a balanced binary search tree instead of an array. is a different data structure. Use a fixed-size array and overwrite values on collision. overwrites on collision, losing data.

3. Final Answer:

   Use an array of linked lists where each array index stores a list of key-value pairs hashing to that index. -> Option A

4. Quick Check:

   Chaining = array of linked lists [OK]

Hint: Chaining = array with linked lists per bucket [OK]

Common Mistakes:

• Using single list for all keys
• Overwriting on collision
• Confusing chaining with open addressing