Why HashMap Implementation from Scratch in DSA Java?

The Big Idea

What if you could find any piece of data instantly without flipping through pages?

The Scenario

Imagine you have a huge phone book written on paper. To find a friend's number, you have to flip through every page until you find their name.

The Problem

This takes a lot of time and effort, especially if the phone book is very big. You might lose your place or make mistakes while searching.

The Solution

A HashMap acts like a magical index that instantly tells you the page and line where your friend's number is, so you don't have to search through everything.

Before vs After

✗ Before

String findNumber(String name) {
  for (Entry entry : phoneBook) {
    if (entry.name.equals(name)) {
      return entry.number;
    }
  }
  return null;
}

✓ After

String findNumber(String name) {
  int index = Math.abs(hash(name)) % capacity;
  for (Entry entry : buckets[index]) {
    if (entry.name.equals(name)) {
      return entry.number;
    }
  }
  return null;
}

What It Enables

It enables lightning-fast lookups, insertions, and deletions even with millions of entries.

Real Life Example

Online shopping sites use HashMaps to quickly find product details when you search by name or ID.

Key Takeaways

Manual searching is slow and error-prone.

HashMaps use a smart index to find data quickly.

This makes programs faster and more efficient.

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