Moms are Hashmapping Geniuses, I Am Not -Part 3: Let's Code a HashMap in Java

From Drawers to Code

I thought I understood HashMap.

I mean — I wrote two whole blogs about it.
With analogies. Diagrams. Even kitchen drawers.

But then I stared at a blank Java file.

Nothing happened.

Just me. A blinking cursor. And a brain that went:

“Wait… how do I even start building one?”

Turns out — understanding something conceptually and implementing it from scratch are two very different things.

So I gave myself a challenge:

Build a working HashMap in Java.
No java.util.*. No shortcuts.
Just plain code, basic logic, and enough logs to annoy the JVM.

This blog is the story of that attempt.

I'll walk you through everything — from hash functions to chaining to rehashing — all using code, not just kitchen metaphors.

---

What We'll Build (and What We Won't)

This is not a production-grade clone of Java's HashMap.
It's a learning-focused implementation to explore the concepts underneath.

---

Step 1: Entry<K, V> — The Bucket Structure

class Entry<K, V> {
    K key;
    V value;
    Entry<K, V> next;

    public Entry(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

Explanation:

• This class represents a single node in a bucket.

• Each entry holds a key, a value, and a pointer to the next node in the chain.

• This linked list structure enables chaining — our strategy for handling collisions.

---

Step 2: MyHashMap Fields

public class MyHashMap<K, V> {
    private Entry<K, V>[] buckets;
    private int capacity = 5;
    private int size = 0;
    private double loadFactor = 0.75;

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

Explanation:

• buckets is the array where all hash entries go — like drawers in the kitchen.

• capacity is the total number of buckets (starts with 5).

• size tracks the current number of key-value pairs.

• loadFactor determines when we rehash (typically 75% full).

---

Step 3: Hashing + put()

Hash Function

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

Explanation:

• Generates an index from a key.

• Uses Java's hashCode() and takes modulo with current capacity.

• Math.abs ensures the result is non-negative.

Insertion with Collision Handling + Rehash Trigger

public void put(K key, V value) {
    int index = hash(key);
    Entry<K, V> newEntry = new Entry<>(key, value);
    Entry<K, V> current = buckets[index];

    if (current == null) {
        buckets[index] = newEntry;
        size++;
    } else {
        Entry<K, V> prev = null;
        while (current != null) {
            if (current.key.equals(key)) {
                current.value = value;
                return;
            }
            prev = current;
            current = current.next;
        }
        prev.next = newEntry;
        size++;
    }

    if ((double) size / capacity >= loadFactor) {
        rehash();
    }
}

Explanation:

• If the target bucket is empty, insert directly.

• If it's occupied, scan the chain for existing key. If found, update.

• If not found, append to end of chain.

• Check load factor after every insert. If exceeded → rehash!

---

Step 4: Rehashing

private void rehash() {
    int oldCapacity = capacity;
    Entry<K, V>[] oldBuckets = buckets;

    capacity = capacity * 2;
    buckets = new Entry[capacity];
    size = 0;

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

    System.out.println("Rehashing complete. New capacity: " + capacity);
}

Explanation:

• Create a new bucket array that's double the size.

• Reinsert all key-value pairs into the new array.

• We use put() again because it handles hashing + chaining correctly.

• size is reset and recalculated during reinsertion.

---

Step 5: get(K)

public V get(K key) {
    int index = hash(key);
    Entry<K, V> current = buckets[index];

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

    return null;
}

Explanation:

• Hash the key to find the bucket.

• Traverse the chain until the key is found.

• Return its value. If not found, return null.

---

Step 6: Demo Time

public class MyHashMapDemo {
    public static void main(String[] args) {
        MyHashMap<Integer, String> map = new MyHashMap<>();

        map.put(17, "Sugar");
        map.put(67, "Salt");
        map.put(32, "Tea");
        map.put(43, "Coffee");

        System.out.println("Get key 17 → " + map.get(17)); // Sugar
        System.out.println("Get key 67 → " + map.get(67)); // Salt
        System.out.println("Get key 32 → " + map.get(32)); // Tea
        System.out.println("Get key 43 → " + map.get(43)); // Coffee

        map.put(98, "Cookies"); // Triggers rehash

        System.out.println("Get key 98 → " + map.get(98)); // Cookies
    }
}

Explanation:

• Adds multiple entries, including ones that collide.

• Retrieves them using get() to validate correctness.

• Adding the fifth item triggers rehashing.

---

Final Thoughts

In this blog, we built a basic HashMap from scratch — covering:

✅ Core building block: Entry<K, V>
✅ Hashing logic and bucket indexing
✅ Collision resolution using chaining
✅ Load factor–based rehashing and resizing
✅ A simple put() / get() API
✅ A quick test in main() to see it all come together

What we skipped (on purpose):

• Support for null keys or values

• remove() and other edge-case operations

• Thread safety or concurrent access

• Optimization strategies (like better hashing or treeification)

This wasn’t about mimicking Java's internal HashMap line for line.
It was about pulling back the curtain.

And when you implement something like this yourself —
even a simplified version — you start seeing the trade-offs in real systems more clearly.

Why certain things are fast.
Where collisions hit performance.
Why rehashing isn't just resizing.
And when you might need something better.

Coding data structures from scratch won’t make you reinvent the wheel.

But it will show you how much thought went into building one that rolls as smoothly as HashMap.

And honestly? That’s a perspective worth having.

---

Fin. 🎬