HashMap Implementation from Scratch in DSA Java - Build from Scratch

HashMap Implementation from Scratch

📖 Scenario: Imagine you want to build a simple phone book app that stores names and phone numbers. To do this efficiently, you decide to create your own version of a HashMap, which stores key-value pairs and allows quick lookup.

🎯 Goal: Build a basic HashMap class in Java from scratch that can store, retrieve, and display key-value pairs.

📋 What You'll Learn

Create an array of buckets to store entries

Implement a simple hash function to map keys to bucket indices

Add methods to put (insert) key-value pairs

Add methods to get (retrieve) values by key

Add a method to display all stored key-value pairs

💡 Why This Matters

🌍 Real World

HashMaps are used in many apps to quickly find data like phone numbers, usernames, or product details.

💼 Career

Understanding how HashMaps work helps in software development roles that require efficient data storage and retrieval.

1

Create the Entry class and buckets array

Create a class called Entry with two public fields: String key and String value. Then, create an array called buckets of type Entry[] with size 5 inside the SimpleHashMap class.

DSA Java

public class SimpleHashMap {
    // Your code here
}

Hint

Think of Entry as a small box holding a name and a phone number. The buckets array will hold these boxes.

2

Add a hash function to map keys to bucket indices

Inside the SimpleHashMap class, add a private method called hash that takes a String key and returns an int. The method should return the remainder of the key's length divided by 5.

DSA Java

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

    Entry[] buckets = new Entry[5];

    // Add the hash method below
    // Your code here
}

Hint

This simple hash function uses the length of the key to decide where to store it.

3

Implement the put method to add key-value pairs

Add a public method called put inside SimpleHashMap that takes String key and String value. Use the hash method to find the bucket index. Store a new Entry with the key and value at that index in the buckets array.

DSA Java

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

    Entry[] buckets = new Entry[5];

    private int hash(String key) {
        return key.length() % 5;
    }

    // Add the put method below
    // Your code here
}

Hint

Use the hash function to find the right spot, then place the new entry there.

4

Add get and display methods, then test the HashMap

Add a public method called get that takes String key and returns the String value stored at the bucket index from the hash method. If the bucket is empty or the key does not match, return null. Also, add a public method called display that prints all stored key-value pairs in the format key -> value. Finally, in the main method, create a SimpleHashMap object, add these pairs: ("Anna", "123"), ("Bob", "456"), ("Clara", "789"), then print the value for key "Bob" and call display.

DSA Java

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

    Entry[] buckets = new Entry[5];

    private int hash(String key) {
        return key.length() % 5;
    }

    public void put(String key, String value) {
        int index = hash(key);
        buckets[index] = new Entry(key, value);
    }

    // Add get and display methods below
    // Add main method below
    // Your code here
}

Hint

Check the bucket for the key and return the value if it matches. Display all entries by looping through buckets.

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