HashMap Implementation from Scratch in DSA Java - Time & Space Complexity

Time Complexity: HashMap Implementation from Scratch

O(n)

Understanding Time Complexity

When building a HashMap from scratch, it is important to understand how fast it can add and find items.

We want to know how the time to do these operations changes as the number of items grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public class SimpleHashMap {
    private static class Node {
        String key;
        String value;
        Node next;
        Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    private Node[] buckets = new Node[16];

    public void put(String key, String value) {
        int index = Math.abs(key.hashCode()) % buckets.length;
        Node head = buckets[index];
        for (Node curr = head; curr != null; curr = curr.next) {
            if (curr.key.equals(key)) {
                curr.value = value;
                return;
            }
        }
        Node newNode = new Node(key, value);
        newNode.next = head;
        buckets[index] = newNode;
    }
}

This code adds a key-value pair to a simple HashMap using an array of linked lists for buckets.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop through linked list nodes in a bucket to check for existing key.
• How many times: Up to the number of nodes in that bucket, which depends on collisions.

How Execution Grows With Input

As more items are added, the number of nodes in each bucket can grow if many keys collide.

Input Size (n)	Approx. Operations
10	About 1 to 2 checks per put (few collisions)
100	About 6 to 7 checks per put if collisions increase
1000	Up to 60+ checks per put if many keys collide in same bucket

Pattern observation: If keys spread evenly, checks stay low; if many collide, checks grow linearly with n.

Final Time Complexity

Time Complexity: O(n) in worst case

This means adding or finding a key can take time proportional to the number of items if many keys collide.

Common Mistake

[X] Wrong: "HashMap operations always take the same short time no matter what."

[OK] Correct: If many keys end up in the same bucket, the linked list grows and operations slow down.

Interview Connect

Understanding how collisions affect HashMap speed shows you know the trade-offs in data structures.

Self-Check

"What if we replaced the linked list with a balanced tree for buckets? How would the time complexity change?"

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