HashMap Implementation from Scratch in DSA Java

Mental Model

A HashMap stores key-value pairs by turning keys into indexes using a hash function, so we can find values quickly without searching all items.

Analogy: Imagine a library where each book's title is turned into a shelf number by a special code. Instead of searching every shelf, you go directly to that shelf to find the book.

Buckets array: [0] -> null
                [1] -> null
                [2] -> null
                ...
Each bucket can hold a linked list of entries:
Bucket[i]: key1:value1 -> key2:value2 -> null

Dry Run Walkthrough

Input: Insert keys and values: (10, 'A'), (22, 'B'), (31, 'C') into a HashMap with 5 buckets

Goal: Store key-value pairs so that keys map to buckets by hash, handling collisions by chaining

Step 1: Calculate hash for key 10: 10 % 5 = 0, insert (10, 'A') into bucket 0

[0] -> (10:'A') -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: We use modulo to find bucket index; bucket 0 is empty, so insert directly

Step 2: Calculate hash for key 22: 22 % 5 = 2, insert (22, 'B') into bucket 2

[0] -> (10:'A') -> null
[1] -> null
[2] -> (22:'B') -> null
[3] -> null
[4] -> null

Why: Bucket 2 is empty, so insert (22, 'B') directly

Step 3: Calculate hash for key 31: 31 % 5 = 1, insert (31, 'C') into bucket 1

[0] -> (10:'A') -> null
[1] -> (31:'C') -> null
[2] -> (22:'B') -> null
[3] -> null
[4] -> null

Why: Bucket 1 is empty, so insert (31, 'C') directly

Step 4: Insert key 15 with value 'D': 15 % 5 = 0, bucket 0 has (10:'A'), add (15:'D') at head

[0] -> (15:'D') -> (10:'A') -> null
[1] -> (31:'C') -> null
[2] -> (22:'B') -> null
[3] -> null
[4] -> null

Why: Collision at bucket 0 handled by chaining; new entry added at front

Step 5: Retrieve value for key 22: hash 2, search bucket 2 linked list for key 22

[0] -> (15:'D') -> (10:'A') -> null
[1] -> (31:'C') -> null
[2] -> (22:'B') -> null
[3] -> null
[4] -> null

Why: Directly access bucket 2 and find key 22 quickly

Result:

[0] -> (15:'D') -> (10:'A') -> null
[1] -> (31:'C') -> null
[2] -> (22:'B') -> null
[3] -> null
[4] -> null
Value for key 22 is 'B'

Annotated Code

DSA Java

import java.util.Objects;

public class MyHashMap {
    private static class Entry {
        int key;
        String value;
        Entry next;

        Entry(int key, String value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }

    private Entry[] buckets;
    private int capacity;

    public MyHashMap(int capacity) {
        this.capacity = capacity;
        this.buckets = new Entry[capacity];
    }

    private int hash(int key) {
        return key % capacity;
    }

    public void put(int key, String value) {
        int index = hash(key); // compute bucket index
        Entry head = buckets[index];

        // Check if key exists, update value
        Entry curr = head;
        while (curr != null) {
            if (curr.key == key) {
                curr.value = value; // update existing key
                return;
            }
            curr = curr.next;
        }

        // Insert new entry at head of list
        Entry newEntry = new Entry(key, value);
        newEntry.next = head;
        buckets[index] = newEntry;
    }

    public String get(int key) {
        int index = hash(key); // compute bucket index
        Entry curr = buckets[index];

        while (curr != null) {
            if (curr.key == key) {
                return curr.value; // found key
            }
            curr = curr.next;
        }
        return null; // key not found
    }

    public void printMap() {
        for (int i = 0; i < capacity; i++) {
            System.out.print("[" + i + "] -> ");
            Entry curr = buckets[i];
            while (curr != null) {
                System.out.print("(" + curr.key + ":'" + curr.value + "') -> ");
                curr = curr.next;
            }
            System.out.println("null");
        }
    }

    public static void main(String[] args) {
        MyHashMap map = new MyHashMap(5);
        map.put(10, "A");
        map.put(22, "B");
        map.put(31, "C");
        map.put(15, "D");

        map.printMap();

        System.out.println("Value for key 22 is '" + map.get(22) + "'");
    }
}

int index = hash(key); // compute bucket index

Calculate bucket index from key using hash function

while (curr != null) { if (curr.key == key) { curr.value = value; return; } curr = curr.next; }

Traverse bucket list to find existing key and update value

Entry newEntry = new Entry(key, value); newEntry.next = head; buckets[index] = newEntry;

Insert new entry at head of bucket list to handle collisions

while (curr != null) { if (curr.key == key) { return curr.value; } curr = curr.next; }

Search bucket list for key to retrieve value

Output

[0] -> (15:'D') -> (10:'A') -> null

[1] -> (31:'C') -> null

[2] -> (22:'B') -> null

[3] -> null

[4] -> null

Value for key 22 is 'B'

Complexity Analysis

Time: O(n/k) on average, where n is number of keys and k is number of buckets, because each bucket holds about n/k entries; worst case O(n) if all keys collide

Space: O(n) because we store all key-value pairs in linked lists inside buckets

vs Alternative: Compared to a simple list which is O(n) for search, this reduces average search to O(1) by using hashing and buckets

Edge Cases

Inserting a key that already exists

The value for that key is updated without adding a new entry

DSA Java

if (curr.key == key) { curr.value = value; return; }

Retrieving a key that does not exist

Returns null indicating key not found

DSA Java

return null; // key not found

Empty map (no entries)

Get returns null; print shows all buckets as null

DSA Java

while (curr != null) { ... } return null;

When to Use This Pattern

When you need fast key-value lookup and see problems about mapping keys to values with possible collisions, use the HashMap pattern with hashing and chaining to handle collisions efficiently.

Common Mistakes

Mistake: Not handling collisions, so new entries overwrite existing ones in the same bucket
Fix: Use linked list chaining to store multiple entries in the same bucket

Mistake: Not updating value when inserting a key that already exists
Fix: Check for existing key in bucket and update its value instead of adding a new entry

Summary

Stores key-value pairs using a hash function to find bucket indexes and linked lists to handle collisions.

Use when you want fast insertion and lookup by key without searching all entries.

The key insight is using a hash function to jump directly to a bucket and chaining to handle multiple keys mapping to the same bucket.

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