HashMap Implementation from Scratch in DSA C# - Execution Trace

Concept Flow - HashMap Implementation from Scratch

Start

↓

Compute Hash(key)

↓

Find Bucket Index = hash % capacity

↓

Check Bucket for key

↓

Key Found?

↓

Update Value

↓

Done

No↓

Add new key-value node to bucket

↓

Increase size

↓

Check Load Factor > Threshold?

↓

Resize and Rehash

↓

Done

No↓

Done

The HashMap stores key-value pairs by computing a hash for the key, finding the bucket, checking if the key exists to update or adding a new node, then resizing if needed.

Execution Sample

DSA C#

class HashMap {
  void Put(key, value) {
    int hash = Hash(key);
    int index = hash % capacity;
    if (key in bucket) update;
    else add new node;
    if (loadFactor > threshold) resize;
  }
}

This code adds or updates a key-value pair in the HashMap, resizing if the load factor is too high.

Execution Table

Step	Operation	Bucket Index	Bucket State Before	Action	Bucket State After	Visual State
1	Put("apple", 10)	2	[]	Add new node (apple,10)	[ (apple,10) ]	[ ] -> [ ] -> [ (apple,10) ] -> [ ] -> [ ]
2	Put("banana", 20)	4	[]	Add new node (banana,20)	[ (banana,20) ]	[ ] -> [ ] -> [ (apple,10) ] -> [ ] -> [ (banana,20) ]
3	Put("apple", 15)	2	[ (apple,10) ]	Update value of apple to 15	[ (apple,15) ]	[ ] -> [ ] -> [ (apple,15) ] -> [ ] -> [ (banana,20) ]
4	Put("cherry", 30)	2	[ (apple,15) ]	Add new node (cherry,30) at head	[ (cherry,30) -> (apple,15) ]	[ ] -> [ ] -> [ (cherry,30) -> (apple,15) ] -> [ ] -> [ (banana,20) ]
5	Put("date", 40)	0	[]	Add new node (date,40)	[ (date,40) ]	[ (date,40) ] -> [ ] -> [ (cherry,30) -> (apple,15) ] -> [ ] -> [ (banana,20) ]
6	Load factor check	-	-	Load factor 4/5=0.8 > 0.75, resize triggered	-	-
7	Resize and rehash	-	-	Capacity doubled to 10, rehash all nodes	-	[ (date,40) ] -> [ ] -> [ (apple,15) ] -> [ ] -> [ ] -> [ ] -> [ (banana,20) ] -> [ ] -> [ ] -> [ (cherry,30) ]
8	Put("elderberry", 50)	7	[ ]	Add new node (elderberry,50)	[ (elderberry,50) ]	[ (date,40) ] -> [ ] -> [ (apple,15) ] -> [ ] -> [ ] -> [ ] -> [ (banana,20) ] -> [ (elderberry,50) ] -> [ ] -> [ (cherry,30) ]
9	Done	-	-	All operations complete	-	Final HashMap state as above

💡 All key-value pairs inserted and updated; resizing done when load factor exceeded threshold.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
size	0	1	2	2	3	4	4	4	5	5
capacity	5	5	5	5	5	5	5	10	10	10
loadFactor	0	0.2	0.4	0.4	0.6	0.8	0.8	0.4	0.5	0.5
buckets	[[],[],[],[],[]]	[[],[],[ (apple,10)],[],[]]	[[],[],[(apple,10)],[],[(banana,20)]]	[[],[],[(apple,15)],[],[(banana,20)]]	[[],[],[(cherry,30)->(apple,15)],[],[(banana,20)]]	[[(date,40)],[],[(cherry,30)->(apple,15)],[],[(banana,20)]]	same	10 buckets with rehashed nodes	updated with elderberry	final state as in execution_table

Key Moments - 3 Insights

Why do we add new nodes at the head of the bucket's linked list instead of the tail?

Adding at the head is faster because we don't need to traverse the list. See Step 4 where cherry is added before apple in the bucket.

Why do we need to resize and rehash when load factor exceeds threshold?

To keep operations fast, we increase capacity and redistribute nodes. Step 6 triggers resize at load factor 0.8, and Step 7 shows rehashing.

How does updating a key's value work in the bucket?

We search the bucket for the key and update its value directly. Step 3 shows updating apple's value from 10 to 15.

Visual Quiz - 3 Questions

Look at the execution table, what is the bucket state after Step 4?

A [ (apple,15) ]

B [ (cherry,30) -> (apple,15) ]

C [ (banana,20) ]

D [ (cherry,30) ]

💡 Hint

Check the 'Bucket State After' column for Step 4 in the execution_table.

At which step does the HashMap resize and rehash?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look for the step labeled 'Resize and rehash' in the execution_table.

If we did not update the value in Step 3 but added a new node instead, what would happen to the size variable?

A It would remain the same

B It would decrease

C It would increase by 1

D It would reset to zero

💡 Hint

Refer to variable_tracker for 'size' changes after each step.

Concept Snapshot

HashMap stores key-value pairs using an array of buckets.
Hash function maps keys to bucket indices.
Collisions handled by linked lists in buckets.
Put operation updates existing keys or adds new nodes.
Resize and rehash when load factor exceeds threshold.
Fast average insert and lookup with proper resizing.

Full Transcript

This visual execution shows how a HashMap works internally. When adding a key-value pair, the key is hashed to find the bucket index. If the key exists in that bucket's linked list, its value is updated. Otherwise, a new node is added at the head of the list. The size increases with new nodes. When the load factor (size divided by capacity) exceeds a threshold, the HashMap resizes by doubling capacity and rehashing all nodes to new buckets. This keeps operations efficient. The execution table tracks each step's bucket states and actions, while the variable tracker shows size, capacity, and load factor changes. Key moments clarify why nodes are added at the head, why resizing is needed, and how updates work. The quiz tests understanding of bucket states, resizing steps, and size changes.

Practice

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

easy

A. To store data sequentially like a list

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

C. To store data in a sorted order

D. To perform mathematical calculations

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 lists or arrays, 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 = fast key to value 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 in C# using generics?

easy

A. Hashtable map = new Hashtable();

B. HashMap map = new HashMap();

C. Map map = new Map();

D. Dictionary map = new Dictionary();

Solution

1. Step 1: Recall C# standard HashMap equivalent

   In C#, Dictionary<K,V> is the built-in generic collection similar to HashMap.

2. Step 2: Check syntax correctness

   Dictionary map = new Dictionary(); correctly declares a Dictionary with int keys and string values.

3. Final Answer:

   Dictionary map = new Dictionary(); -> Option D

4. Quick Check:

   C# HashMap = Dictionary [OK]

Hint: Use Dictionary for HashMap in C# [OK]

Common Mistakes:

• Using non-existent HashMap class in C#
• Confusing Hashtable with generic Dictionary
• Wrong generic syntax

3. Consider this simple HashMap implementation snippet in C#:

class SimpleHashMap {
  private int[] keys = new int[5];
  private string[] values = new string[5];

  public void Put(int key, string value) {
    int index = key % 5;
    keys[index] = key;
    values[index] = value;
  }

  public string Get(int key) {
    int index = key % 5;
    if (keys[index] == key) return values[index];
    return null;
  }
}

SimpleHashMap map = new SimpleHashMap();
map.Put(1, "One");
map.Put(6, "Six");
string result = map.Get(1);

What is the value of result after this code runs?

medium

A. null

B. "One"

C. "Six"

D. Runtime error

Solution

1. Step 1: Calculate index for key 1

   Index = 1 % 5 = 1. So keys[1] = 1, values[1] = "One".

2. Step 2: Calculate index for key 6

   Index = 6 % 5 = 1. This overwrites keys[1] = 6, values[1] = "Six".

3. Step 3: Get value for key 1

   Index = 1 % 5 = 1. keys[1] is now 6, not 1, so Get returns null.

4. Final Answer:

   null -> Option A

5. Quick Check:

   Collision overwrites key 1, so Get(1) = null [OK]

Hint: Check key collision and overwrite in simple hash arrays [OK]

Common Mistakes:

• Ignoring key collision overwrite
• Assuming values are stored separately
• Expecting 'One' despite collision

4. Identify the bug in this simple HashMap Put method and choose the correct fix:

public void Put(int key, string value) {
  int index = key % 5;
  if (keys[index] != key) {
    keys[index] = key;
    values[index] = value;
  }
}

medium

A. Change modulus to key % 10 for bigger array

B. Remove the if check to always overwrite key and value

C. Add linear probing to handle collisions

D. Use keys[index] == key instead of != in if condition

Solution

1. Step 1: Understand current behavior

   The if (keys[index] != key) inserts only if the existing key differs: overwrites on collisions (data loss for previous keys) and skips updates for matching keys.

2. Step 2: Identify collision handling

   Without collision handling like linear probing, new keys that hash to occupied slots overwrite existing data.

3. Step 3: Fix by adding linear probing

   Linear probing searches next slots to find an empty or matching key slot, preventing overwrites.

4. Final Answer:

   Add linear probing to handle collisions -> Option C

5. Quick Check:

   Collision fix = linear probing [OK]

Hint: Handle collisions with probing, not just overwrite [OK]

Common Mistakes:

• Removing if causes overwrites
• Changing modulus without resizing array
• Wrong if condition logic

5. You want to implement a HashMap from scratch in C# that supports storing string keys and integer values. Which approach correctly handles collisions and allows retrieval of values?

class MyHashMap {
  private List>[] buckets;
  private int size = 10;

  public MyHashMap() {
    buckets = new List>[size];
    for (int i = 0; i < size; i++) buckets[i] = new List>();
  }

  private int GetBucketIndex(string key) {
    return Math.Abs(key.GetHashCode()) % size;
  }

  public void Put(string key, int value) {
    int index = GetBucketIndex(key);
    var bucket = buckets[index];
    for (int i = 0; i < bucket.Count; i++) {
      if (bucket[i].Key == key) {
        bucket[i] = new KeyValuePair(key, value);
        return;
      }
    }
    bucket.Add(new KeyValuePair(key, value));
  }

  public int? Get(string key) {
    int index = GetBucketIndex(key);
    var bucket = buckets[index];
    foreach (var kvp in bucket) {
      if (kvp.Key == key) return kvp.Value;
    }
    return null;
  }
}

MyHashMap map = new MyHashMap();
map.Put("apple", 5);
map.Put("banana", 3);
map.Put("apple", 10);
int? val = map.Get("apple");

What is the value of val after this code runs?

hard

A. 10

B. 5

C. 3

D. null

Solution

1. Step 1: Understand Put method behavior

   When inserting "apple" the second time, the code finds the existing key and updates its value to 10.

2. Step 2: Understand Get method behavior

   Get("apple") searches the bucket and returns the updated value 10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Updated value for "apple" = 10 [OK]

Hint: Update existing key value, else add new pair [OK]

Common Mistakes:

• Returning old value instead of updated
• Ignoring collision handling with buckets
• Returning null if key exists