Under the Hood: Building a Custom HashMap in Java

In Java development, maps are everywhere. They store key-value pairs and look up values almost instantaneously. But have you ever wondered how standard maps organize elements and handle keys under the hood?

In this guide, we will explore the internal mechanics of a real HashMap by implementing one from scratch in Java (supporting key operations like put, get, remove, and dynamic resizing). More importantly, we will explain the concepts using a simple real-world analogy.

Core Technical Concepts

1. The Bucket Array and Nodes

Internally, our map stores elements in a simple array. Each index in the array is a "bucket." If multiple keys map to the same bucket, we chain them using a singly linked list. Each link in this chain is a Node containing the key, the value, and a reference to the next node in the chain.

static class Node<K, V> {
    final K key;
    V value;
    Node<K, V> next;
    // Constructor...
}

2. Calculating the Bucket Index (Hash Function)

When you insert a key, we get its hash code (an integer Java computes automatically for objects) and take the modulus of the current array capacity. This keeps the index within the array boundaries. We map null keys explicitly to index 0:

private int hash(K key) {
    if (key == null) return 0;
    return Math.abs(key.hashCode() % capacity);
}

3. Putting Elements (Inserting/Updating)

To store a value, we hash the key to get the index. If the bucket is empty, we place our new node there. If the bucket is occupied (a collision!), we traverse the list:

• If the key already exists (via equals()), we overwrite the old value.
• If the key is new, we append it to the end of the chain.

4. Getting Elements (Retrieval)

Retrieval is quick. We hash the key, jump directly to that bucket, and scan down the linked list comparing keys. If we find a match, we return its value; otherwise, we return null.

5. Resizing and Rehashing

A map's efficiency depends on keeping chains short. If we have too many elements compared to buckets, collisions spike. We define a Load Factor threshold (typically 0.75). If the number of elements exceeds 75% of the capacity, we double the bucket array and rehash (re-run the hash formula for all items under the new capacity) to spread them out evenly.

Complete Source Code

Below is the complete implementation of CustomHashMap.java showing these concepts in action with verbose logging.

package io.practise.map;

public class CustomHashMap<K, V> {
    
    static class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next;

        public Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private Node<K, V>[] table;
    private int capacity;
    private final float loadFactor = 0.75f;
    private int size;

    @SuppressWarnings("unchecked")
    public CustomHashMap(int initialCapacity) {
        this.capacity = initialCapacity;
        this.table = (Node<K, V>[]) new Node[capacity];
        this.size = 0;
    }

    private int hash(K key) {
        if (key == null) return 0;
        return Math.abs(key.hashCode() % capacity);
    }

    public V put(K key, V value) {
        if ((float) (size + 1) / capacity > loadFactor) {
            resize();
        }

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

        if (head == null) {
            table[index] = new Node<>(key, value, null);
            size++;
            return null;
        }

        Node<K, V> curr = head;
        while (curr != null) {
            if (isKeyEqual(curr.key, key)) {
                V oldValue = curr.value;
                curr.value = value;
                return oldValue;
            }
            if (curr.next == null) break;
            curr = curr.next;
        }

        curr.next = new Node<>(key, value, null);
        size++;
        return null;
    }

    public V get(K key) {
        int index = hash(key);
        Node<K, V> curr = table[index];

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

    public V remove(K key) {
        int index = hash(key);
        Node<K, V> curr = table[index];
        Node<K, V> prev = null;

        while (curr != null) {
            if (isKeyEqual(curr.key, key)) {
                V value = curr.value;
                if (prev == null) {
                    table[index] = curr.next;
                } else {
                    prev.next = curr.next;
                }
                size--;
                return value;
            }
            prev = curr;
            curr = curr.next;
        }
        return null;
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        int oldCapacity = capacity;
        Node<K, V>[] oldTable = table;

        capacity = oldCapacity * 2;
        table = (Node<K, V>[]) new Node[capacity];
        size = 0;

        for (int i = 0; i < oldCapacity; i++) {
            Node<K, V> curr = oldTable[i];
            while (curr != null) {
                put(curr.key, curr.value);
                curr = curr.next;
            }
        }
    }

    private boolean isKeyEqual(K k1, K k2) {
        if (k1 == null) return k2 == null;
        return k1.equals(k2);
    }
}

Conclusion

By implementing a custom map, we see how arrays and linked lists combine to form one of Java's most powerful data structures. The performance of lookups is kept close to constant time O(1) by using hash codes to index directly into the bucket array, resolving occasional collisions dynamically using chained lists.