HashMap Implementation from Scratch in DSA Java - Execution Trace

Concept Flow - HashMap Implementation from Scratch

Create array of buckets

↓

Insert key-value pair

↓

Compute hash for key

↓

Find bucket index = hash % array size

↓

Check bucket linked list

↓

Traverse list

↓

If key found

↓

Update value

↓

Done

The HashMap stores key-value pairs in buckets based on hash. On insert, it finds the bucket by hashing the key, then updates or adds the node.

Execution Sample

DSA Java

class HashMap {
  Node[] buckets = new Node[4];
  void put(String key, int val) {
    int idx = Math.abs(hash(key)) % buckets.length;
    // insert or update
  }
}

This code creates a small HashMap with 4 buckets and inserts a key-value pair by hashing the key.

Execution Table

Step	Operation	Bucket Index	Bucket State Before	Pointer Changes	Bucket State After	Visual State
1	Initialize buckets array	-	[] [] [] []	-	[] [] [] []	[] -> null, [] -> null, [] -> null, [] -> null
2	Put("apple", 10)	hash("apple") % 4 = 1	[] [] [] []	Add node (apple,10) at bucket 1	[] [apple:10] [] []	[] -> null, [apple:10] -> null, [] -> null, [] -> null
3	Put("banana", 20)	hash("banana") % 4 = 3	[] [apple:10] [] []	Add node (banana,20) at bucket 3	[] [apple:10] [] [banana:20]	[] -> null, [apple:10] -> null, [] -> null, [banana:20] -> null
4	Put("apple", 15)	hash("apple") % 4 = 1	[] [apple:10] [] [banana:20]	Find node with key "apple", update value to 15	[] [apple:15] [] [banana:20]	[] -> null, [apple:15] -> null, [] -> null, [banana:20] -> null
5	Put("grape", 30)	hash("grape") % 4 = 1	[] [apple:15] [] [banana:20]	Add node (grape,30) at head of bucket 1	[] [grape:30 -> apple:15] [] [banana:20]	[] -> null, [grape:30] -> [apple:15] -> null, [] -> null, [banana:20] -> null
6	Put("melon", 40)	hash("melon") % 4 = 0	[] [grape:30 -> apple:15] [] [banana:20]	Add node (melon,40) at bucket 0	[melon:40] [grape:30 -> apple:15] [] [banana:20]	[melon:40] -> null, [grape:30] -> [apple:15] -> null, [] -> null, [banana:20] -> null
7	Put("berry", 50)	hash("berry") % 4 = 3	[melon:40] [grape:30 -> apple:15] [] [banana:20]	Add node (berry,50) at head of bucket 3	[melon:40] [grape:30 -> apple:15] [] [berry:50 -> banana:20]	[melon:40] -> null, [grape:30] -> [apple:15] -> null, [] -> null, [berry:50] -> [banana:20] -> null
8	Put("apple", 25)	hash("apple") % 4 = 1	[melon:40] [grape:30 -> apple:15] [] [berry:50 -> banana:20]	Find node with key "apple", update value to 25	[melon:40] [grape:30 -> apple:25] [] [berry:50 -> banana:20]	[melon:40] -> null, [grape:30] -> [apple:25] -> null, [] -> null, [berry:50] -> [banana:20] -> null
9	End of operations	-	[melon:40] [grape:30 -> apple:25] [] [berry:50 -> banana:20]	-	[melon:40] [grape:30 -> apple:25] [] [berry:50 -> banana:20]	Final HashMap state as above

💡 All put operations complete, final HashMap buckets contain updated key-value pairs.

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	Final
buckets[0]	null	null	null	null	null	melon:40	melon:40	melon:40	melon:40
buckets[1]	null	apple:10	apple:10	apple:15	grape:30 -> apple:15	grape:30 -> apple:15	grape:30 -> apple:15	grape:30 -> apple:25	grape:30 -> apple:25
buckets[2]	null	null	null	null	null	null	null	null	null
buckets[3]	null	null	banana:20	banana:20	banana:20	banana:20	berry:50 -> banana:20	berry:50 -> banana:20	berry:50 -> banana:20

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 5 and 7 in execution_table where new nodes are added at the start.

How does the HashMap handle inserting a key that already exists?

It traverses the bucket's list to find the key and updates its value instead of adding a new node. See step 4 and 8 where 'apple' value is updated.

Why do we use hash(key) % buckets.length to find the bucket index?

This ensures the index fits within the array size. It distributes keys across buckets. See bucket index column in execution_table for each put operation.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the visual state of bucket 1 after inserting 'grape'?

A [grape:30] -> [apple:15] -> null

B [apple:15] -> [grape:30] -> null

C [apple:15] -> null

D [grape:30] -> null

💡 Hint

Check the 'Visual State' column at step 5 in execution_table.

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

A Step 2

B Step 4

C Step 6

D Step 8

💡 Hint

Look for 'update value' operation for 'apple' in execution_table.

If the buckets array size was increased to 8, how would the bucket index for 'melon' change at step 6?

A It would remain 0

B It would be hash('melon') % 8, possibly different

C It would be 4

D It would be hash('melon') % 4

💡 Hint

Bucket index depends on modulo with buckets.length, see concept_flow and execution_table.

Concept Snapshot

HashMap stores key-value pairs in buckets.
Use hash(key) % bucket_count to find bucket.
Each bucket is a linked list of nodes.
Insert new nodes at head for speed.
Update value if key exists.
Handles collisions by chaining nodes.

Full Transcript

This visual trace shows how a HashMap works internally. We start with an array of empty buckets. When we put a key-value pair, we compute the hash of the key and find the bucket index by modulo with the array size. If the bucket is empty, we add a new node. If not, we traverse the linked list to find if the key exists. If found, we update the value. Otherwise, we add a new node at the head of the list. This chaining handles collisions. The variable tracker shows how each bucket changes after each put operation. Key moments clarify why nodes are added at the head, how updates happen, and why modulo is used. The quiz tests understanding of bucket states and updates. This step-by-step helps beginners see the physical changes inside a HashMap.

Practice

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

easy

A. To store key-value pairs for fast lookup

B. To store elements in sorted order

C. To store only unique values without keys

D. To store elements in a last-in-first-out order

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 sorted or stack structures, HashMap focuses on fast lookup, not order or uniqueness of values alone.

3. Final Answer:

   To store key-value pairs for fast lookup -> Option A

4. Quick Check:

   HashMap = key-value fast access [OK]

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

Common Mistakes:

• Confusing HashMap with TreeMap (sorted)
• Thinking HashMap stores only unique values
• Mixing HashMap with stack or queue behavior

2. Which of the following is the correct way to declare a basic HashMap in Java from scratch?

easy

A. HashMap map = new HashMap<>();

B. HashMap<Integer> map = new HashMap<>();

C. HashMap map = new HashMap();

D. HashMap map = new HashMap();

Solution

1. Step 1: Check generic syntax for HashMap

   Java requires specifying key and value types inside angle brackets <Key, Value>.

2. Step 2: Identify correct generic declaration

   HashMap map = new HashMap(); uses full generic syntax for both declaration and instantiation, which is correct in Java before version 7.

3. Final Answer:

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

4. Quick Check:

   Full generic syntax = HashMap map = new HashMap(); [OK]

Hint: Use on both sides before Java 7 [OK]

Common Mistakes:

• Omitting generic types on instantiation (Option A is Java 7+ syntax)
• Using only one generic type (Option D is invalid)
• Not using generics at all (Option C is raw type)

3. Consider this simplified HashMap put method snippet from scratch:

public void put(K key, V value) {
  int index = key.hashCode() % capacity;
  if (buckets[index] == null) {
    buckets[index] = new Node(key, value);
  } else {
    Node current = buckets[index];
    while (current.next != null) {
      if (current.key.equals(key)) {
        current.value = value;
        return;
      }
      current = current.next;
    }
    current.next = new Node(key, value);
  }
}

What happens if we insert two keys with the same hashCode but different values?

medium

A. A runtime error occurs due to collision

B. The second key-value pair overwrites the first one

C. Both key-value pairs are stored in a linked list at the same bucket

D. Only the first key-value pair is stored, second is ignored

Solution

1. Step 1: Understand collision handling in code

   If bucket is occupied, code traverses linked nodes to check keys and appends new node if key not found.

2. Step 2: Analyze insertion of different keys with same hash

   Since keys differ but hash is same, new node is added at end of linked list, preserving both pairs.

3. Final Answer:

   Both key-value pairs are stored in a linked list at the same bucket -> Option C

4. Quick Check:

   Collision handled by chaining = Both key-value pairs are stored in a linked list at the same bucket [OK]

Hint: Same hash keys chain in linked list bucket [OK]

Common Mistakes:

• Assuming second key overwrites first without key match
• Thinking collision causes error
• Ignoring linked list chaining for collisions

4. Given this buggy put method snippet from a HashMap implementation:

public void put(K key, V value) {
  int index = key.hashCode() % capacity;
  if (buckets[index] == null) {
    buckets[index] = new Node(key, value);
  } else {
    Node current = buckets[index];
    while (current != null) {
      if (current.key.equals(key)) {
        current.value = value;
        return;
      }
      current = current.next;
    }
    current.next = new Node(key, value);
  }
}

What is the error in this code?

medium

A. The loop condition should be while (current.next != null) instead of while (current != null)

B. The hashCode modulo operation should use capacity - 1

C. The key comparison should use == instead of equals()

D. The new node is added before checking existing keys

Solution

1. Step 1: Analyze the while loop condition

   The loop runs while current != null, so after loop current becomes null.

2. Step 2: Check where new node is added

   After loop, code tries current.next = new Node(...), but current is null causing NullPointerException.

3. Step 3: Correct loop condition

   Changing loop to while (current.next != null) stops at last node, allowing safe addition at current.next.

4. Final Answer:

   The loop condition should be while (current.next != null) instead of while (current != null) -> Option A

5. Quick Check:

   Loop must stop at last node to add new node [OK]

Hint: Loop to last node, not null, to add new node safely [OK]

Common Mistakes:

• Using current != null causes NullPointerException on insertion
• Incorrect modulo operation for bucket index
• Using == instead of equals() for key comparison

5. You are implementing a HashMap from scratch with an array of buckets and linked lists for collisions. If the initial capacity is 4 and you insert keys with hashCodes: 2, 6, 10, 14, what will be the structure of the buckets after all insertions?

Assume bucket index = hashCode % capacity and each bucket holds a linked list of nodes.

Choose the correct bucket contents representation (keys only):

hard

A. Bucket 0: 2 -> 6 -> 10 -> 14Bucket 1: nullBucket 2: nullBucket 3: null

B. Bucket 0: nullBucket 1: nullBucket 2: 2 -> 6 -> 10 -> 14Bucket 3: null

C. Bucket 0: nullBucket 1: nullBucket 2: 2Bucket 3: 6 -> 10 -> 14

D. Bucket 0: nullBucket 1: nullBucket 2: 2 -> 6Bucket 3: 10 -> 14

Solution

1. Step 1: Calculate bucket index for each key

   Using index = hashCode % 4:
   2 % 4 = 2
   6 % 4 = 2
   10 % 4 = 2
   14 % 4 = 2

2. Step 2: Re-examine calculation carefully

   Actually:
   2 % 4 = 2
   6 % 4 = 2
   10 % 4 = 2
   14 % 4 = 2
   All keys map to bucket 2, so all should be in bucket 2 linked list.

3. Step 3: Check options for matching bucket 2 content

   Bucket 0: null
   Bucket 1: null
   Bucket 2: 2 -> 6 -> 10 -> 14
   Bucket 3: null shows all keys in bucket 2 linked list, which matches calculation.

4. Step 4: Verify other buckets are null

   Other buckets 0,1,3 are null as no keys map there.

5. Final Answer:

   Bucket 0: null
   Bucket 1: null
   Bucket 2: 2 -> 6 -> 10 -> 14
   Bucket 3: null -> Option B

6. Quick Check:

   All keys % 4 = 2, so bucket 2 holds all [OK]

Hint: Calculate hashCode % capacity for each key [OK]

Common Mistakes:

• Miscomputing modulo operation
• Distributing keys incorrectly across buckets
• Assuming keys spread evenly without modulo check