# 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.

| Feature | Status |
| --- | --- |
| `put(K, V)` | ✅ Yes |
| `get(K)` | ✅ Yes |
| Collision Handling (Chaining) | ✅ Yes |
| Load Factor Check | ✅ Yes |
| Rehashing Logic | ✅ Yes |
| `remove()` | ❌ Nope |
| `null` Key Support | ❌ Nope |
| Thread Safety | ❌ Nope |

---

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

```java
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

```java
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

```java
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

```java
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

```java
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)

```java
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

```java
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.** 🎬