How HashMap Works Internally in Java – A Hands-on Guide with Custom Implementation

---

When we use Java’s HashMap, it feels like magic. You just put() and get(), and it works in constant time — O(1) in the average case. But have you ever wondered how it actually works under the hood?

In this blog, we’ll demystify the internals of a HashMap by building our own version step-by-step. This guide will help you understand key concepts like hashing, collisions, resizing, and why certain design decisions are made in Java’s standard library.

---

What Is a HashMap?

A HashMap stores key-value pairs. It provides fast retrieval of values based on keys using a technique called hashing.

Internally, a HashMap uses:

• An array of buckets

• Each bucket is a linked list (or in Java 8+, a tree if too many collisions)

• Each node in the list stores a key, value, and next pointer

---

Our Plan: Build

MyHashMap<K, V>

Let’s build our own generic HashMap class in Java, called MyHashMap<K, V>, which supports:

• put(K key, V value)

• get(K key)

• remove(K key)

• containsKey(K key)

• Automatic resizing when the load factor threshold is crossed

---

The Building Block: Node Class

At the heart of our map is the Node<K, V> class, which represents a key-value pair.

Why is key final?

Because once inserted, a key must never change — otherwise, the hash index would be invalid, leading to hard-to-debug issues.

---

Hashing Logic

To determine which bucket a key belongs to, we use:

private int hash(K key) {
    return (key == null) ? 0 : Math.abs(key.hashCode()) % buckets.length;
}

This ensures uniform distribution and avoids ArrayIndexOutOfBounds.

---

Inserting a Key-Value Pair

put()

When calling put(), we:

1. Calculate the hash index.

2. Check if the key exists in the linked list at that index.

   • If yes, update its value.

   • If no, add a new Node at the head of the list.

3. Check if we need to resize the array based on load factor.

---

Retrieving a Value

get()

get() uses the same hash logic to find the right bucket and traverses its list to find the key.

---

Removing a Key

remove()

remove() again hashes to the right bucket and removes the node by adjusting pointers in the chain.

---

Handling Resizing

To keep time complexity low, we resize the array (double its size) when the load factor crosses 0.75. Each node is rehashed and reinserted into the new array.

private void resize() {
    Node<K, V>[] oldBuckets = buckets;
    buckets = new Node[oldBuckets.length * 2];
    size = 0;

    for (Node<K, V> head : oldBuckets) {
        while (head != null) {
            put(head.key, head.value); // Rehash
            head = head.next;
        }
    }
}

---

Sample Output

MyHashMap<String, Integer> map = new MyHashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("A", 5);  // Update
System.out.println(map.get("A")); // Output: 5
System.out.println(map.containsKey("C")); // Output: false
map.remove("B");
System.out.println(map.size()); // Output: 1

---

Advantages of Building Your Own

• Concept Clarity: Understand the core logic behind hashing and memory usage.

• Customization: Add features like time-based eviction, ordering, or thread-safety.

• Interview Preparation: Many product-based companies expect deep knowledge of hash maps.

---

Summary

Your MyHashMap is now a simplified but functional version of Java’s powerful HashMap. You’ve implemented:

• Hashing and collision handling

• Resizing logic

• Core operations (put, get, remove, containsKey)

This isn’t just theory — it’s practical, foundational knowledge that will give you an edge in system design and coding interviews.

---

🔗 Source Code

package MyHashMap;
import java.util.*;
public class MyHashMap<K,V> {
   static class Node<K,V>{
        final K key;
        V value;
       Node<K, V> next;

       Node(K key , V value) {
           this.key = key;
           this.value = value;
       }
   }
    private static final int INITIAL_CAPACITY = 16;
    private static final float LOAD_FACTOR_THRESHOLD = 0.75f;
    private Node<K, V>[] buckets;
    private int size = 0;

    @SuppressWarnings("unchecked")
    public MyHashMap() {
        buckets = new Node[INITIAL_CAPACITY];
    }
    private int hash(K key) {
        return (key == null) ? 0 : Math.abs(key.hashCode()) % buckets.length;
    }
    public int size() {
        return size;
    }
    public boolean containsKey(K key) {
        return get(key) != null;
    }
    public V get(K key) {
        int index = hash(key);
        Node<K, V> current = buckets[index];
        while (current != null) {
            if (Objects.equals(current.key, key)) {
                return current.value;
            }
            current = current.next;
        }
        return null;
    }
    public void put(K key, V value) {
        if ((float) (size + 1) / buckets.length >= LOAD_FACTOR_THRESHOLD) {
            resize();
        }

        int index = hash(key);
        Node<K, V> head = buckets[index];

        for (Node<K, V> node = head; node != null; node = node.next) {
            if (Objects.equals(node.key, key)) {
                node.value = value; // Update
                return;
            }
        }

        Node<K, V> newNode = new Node<>(key, value);
        newNode.next = head;
        buckets[index] = newNode;
        size++;
    }
    public void remove(K key) {
        int index = hash(key);
        Node<K, V> current = buckets[index];
        Node<K, V> prev = null;

        while (current != null) {
            if (Objects.equals(current.key, key)) {
                if (prev == null) {
                    buckets[index] = current.next;
                } else {
                    prev.next = current.next;
                }
                size--;
                return;
            }
            prev = current;
            current = current.next;
        }
    }
    @SuppressWarnings("unchecked")
    private void resize() {
        Node<K, V>[] oldBuckets = buckets;
        buckets = new Node[oldBuckets.length * 2];
        size = 0;

        for (Node<K, V> head : oldBuckets) {
            while (head != null) {
                put(head.key, head.value); // Rehash
                head = head.next;
            }
        }
    }
}