HashMap Implementation from Scratch in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of put and get operations in custom HashMap

What is the output of the following Java code using a custom HashMap implementation after inserting and retrieving values?

DSA Java

CustomHashMap<String, Integer> map = new CustomHashMap<>();
map.put("apple", 10);
map.put("banana", 20);
map.put("apple", 30);
System.out.println(map.get("apple"));
System.out.println(map.get("banana"));
System.out.println(map.get("cherry"));

A 10\n20\n0

B 30\n20\nnull

C 30\n20\n0

D 10\n20\nnull

💡 Hint

Remember that putting a value with an existing key updates the value.

The key "apple" is first inserted with 10, then updated to 30. "banana" is 20. "cherry" is not present, so get returns null.

🧠 Conceptual

intermediate

Understanding collision handling in custom HashMap

In a custom HashMap implementation using separate chaining, what happens when two different keys produce the same hash index?

A Both key-value pairs are stored in a linked list at that index.

B The second key-value pair replaces the first one at that index.

C An error is thrown due to collision.

D The HashMap automatically resizes to avoid collision.

💡 Hint

Think about how separate chaining works to handle collisions.

Separate chaining stores multiple entries in a linked list at the same bucket index to handle collisions.

🔧 Debug

advanced

Identify the bug in put method of custom HashMap

What is the bug in this put method snippet of a custom HashMap that uses separate chaining?

DSA Java

public void put(K key, V value) {
    int index = key.hashCode() % buckets.length;
    Node<K, V> head = buckets[index];
    while (head != null) {
        if (head.key.equals(key)) {
            head.value = value;
            return;
        }
        head = head.next;
    }
    Node<K, V> newNode = new Node<>(key, value);
    newNode.next = buckets[index];
    buckets[index] = newNode;
}

A The buckets array is not initialized.

B The new node is not linked to the existing list.

C The method does not update the value if key exists.

D Using % operator can cause negative index if hashCode is negative.

💡 Hint

Consider what happens if hashCode returns a negative number.

Using % operator directly can produce negative indices if hashCode is negative, causing ArrayIndexOutOfBoundsException.

📝 Syntax

advanced

Correct syntax for generic Node class in custom HashMap

Which option correctly declares a generic Node class for a custom HashMap in Java?

A class Node<K, V> { K key; V value; Node<K, V> next; Node(K key, V value) { this.key = key; this.value = value; } }

B class Node { K key; V value; Node next; Node(K key, V value) { this.key = key; this.value = value; } }

C class Node<K, V> { K key; V value; Node next; Node(K key, V value) { this.key = key; this.value = value; } }

D class Node<K, V> { K key; V value; Node<K> next; Node(K key, V value) { this.key = key; this.value = value; } }

💡 Hint

The next node should have the same generic types as the current node.

Option A correctly uses generics for key, value, and next node. Others miss generics or mismatch types.

🚀 Application

expert

Resulting size after multiple put and remove operations

Given a custom HashMap with separate chaining, what is the size of the map after these operations?

DSA Java

CustomHashMap<String, Integer> map = new CustomHashMap<>();
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
map.put("a", 4);
map.remove("b");
map.put("d", 5);
map.remove("e");

A 4

B 2

C 3

D 5

💡 Hint

Remember that updating a key does not increase size and removing a non-existent key does nothing.

Keys "a", "c", and "d" remain. "b" is removed. "e" was never added, so size is 3.

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