HashMap Implementation from Scratch in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the array that will store the buckets for the HashMap.

DSA Java

private Entry<K, V>[] [1];

Drag options to blanks, or click blank then click option'

Aelements

Bbuckets

Citems

Dnodes

Attempts:

3 left

💡 Hint

Common Mistakes

Using a generic name like 'elements' instead of 'buckets'.

Confusing the array with a list of entries.

The array that stores the linked list heads in the HashMap is commonly named 'buckets'.

2fill in blank

medium

Complete the code to compute the index for a key in the buckets array.

DSA Java

int index = (key.hashCode() & 0x7fffffff) [1] buckets.length;

Drag options to blanks, or click blank then click option'

A%

B/

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using division '/' which gives a quotient, not an index.

Using multiplication '*' which can exceed array bounds.

The modulo operator '%' is used to ensure the index fits within the array length.

3fill in blank

hard

Fix the error in the put method to correctly add a new entry at the head of the linked list.

DSA Java

Entry<K, V> newEntry = new Entry<>(key, value, [1]);
buckets[index] = newEntry;

Drag options to blanks, or click blank then click option'

AnewEntry

Bnull

Cbuckets[index]

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Setting next to null loses the existing entries.

Setting next to newEntry causes a cycle.

The new entry's next pointer should point to the current head at buckets[index].

4fill in blank

hard

Fill both blanks to complete the get method that searches for a key in the linked list.

DSA Java

for (Entry<K, V> e = buckets[index]; e != [1]; e = e.[2]) {
    if (e.key.equals(key)) {
        return e.value;
    }
}

Drag options to blanks, or click blank then click option'

Anull

Bbuckets[index]

Cnext

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using buckets[index] in the loop condition causes infinite loop.

Using 'value' instead of 'next' to move to next entry.

The loop continues until e is null, moving to the next entry via e.next.

5fill in blank

hard

Fill all three blanks to complete the remove method that deletes an entry by key.

DSA Java

Entry<K, V> prev = null;
for (Entry<K, V> e = buckets[index]; e != null; e = e.[1]) {
    if (e.key.equals(key)) {
        if (prev == null) {
            buckets[index] = e.[2];
        } else {
            prev.[3] = e.[2];
        }
        return e.value;
    }
    prev = e;
}

Drag options to blanks, or click blank then click option'

Anext

Bprev

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'value' instead of 'next' for traversal or link update.

Using 'prev' instead of 'next' for link update.

Use 'next' to traverse and update links; prev.next skips the removed entry.

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