# Moms are Hashmapping Geniuses - Part 1: HashMap, Hashing, Collision and an Organized Kitchen

## The Kitchen Where It All Began

I’ve used `HashMap` for years.Put a key, get a value. Fast. Clean. Easy.

I never really thought about *how* it works. It just… worked.

Then one day, I was helping my mom organize our kitchen. We had a lot of drawers — each loosely assigned to different things.

“Tea bags go in drawer 3 as usual,” I said, confidently.

But drawer 3 was already full of tea bags.

I turned to my mom and asked, “Where should I put these now?”

She casually replied,

> “If 3 is full, just put them in 2 or 4 — I’ll still check nearby.”

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1744104828973/b1ced716-3ceb-40b7-9440-743b67045737.png align="center")

I blinked.

Something about that logic felt... oddly smart.

At the time, I didn’t think much of it.

But later that night, I kept coming back to that moment. The way she handled overflow. The fallback plan. The "check nearby" rule.

And out of nowhere, it hit me:

> “Wait… did my mom just HashMap in real life?”

That thought sent me spiraling into late-night docs, internal implementation guides and some very nerdy GitHub issues.

And what I found completely changed how I thought about one of Java’s most-used data structures.

---

## What is a HashMap, Really?

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1744104778930/ccc4adb2-953a-4187-a9f3-499728922e7c.png align="center")

Let’s say you have a cupboard full of drawers, and each drawer is meant to hold a specific item. You want a system where you can store something and instantly find it later — no labels, no search effort.

You tag every item with a key. And based on that key, the cupboard automatically figures out **which drawer** it should go into.

Later, when you provide the same key again, it instantly retrieves the correct item from the exact drawer — no scan, no guesswork.

That’s essentially how a `HashMap` functions: a data structure that provides constant-time complexity — O(1) on average — for inserting, retrieving, and deleting entries using a computed index.

You give it a **key** → it stores your **value** in a calculated slot. Give the same key again → it finds that slot and gives the value back. ***Instantly!!!***

Behind the scenes, it uses something called **hashing** to determine *where* each item should go.

---

## What is Hashing?

Hashing is the process by which a `HashMap` calculates the storage index — or *bucket* — for a key-value pair. It's the secret sauce behind those O(1) lookups.

You provide a key. Internally, the system runs it through a hash function to compute the drawer (bucket) number — a mathematical operation that maps your key to an integer representing the slot.

A simplified version might look like this:

```java
Y = K % N
```

Where:

* `K` is the key (typically an integer or hashed string)
    
* `N` is the total number of drawers (hash table size)
    
* `Y` is the resulting index (bucket number)
    

Let’s assume the drawer count `N` is 10. Here's how a few keys get mapped:

| **Key** | **Hash Function** | **Result** |
| --- | --- | --- |
| 17 | 17 % 10 | 7 |
| 23 | 23 % 10 | 3 |
| 34 | 34 % 10 | 4 |
| 51 | 51 % 10 | 1 |
| 67 | 67 % 10 | 7 |

At first glance, this works perfectly. Each key lands in a precise, predictable drawer. Retrieval becomes instant using the same deterministic formula.

**Hashing enables constant-time access — and that's the whole game.** The better the distribution of keys across buckets, the more performant your map remains.

Or so it seems…

---

## But Why Does Something Feel Odd?

Take a closer look.

Both key `17` and key `67` get mapped to drawer `7`.

They’re completely different values — but they collide at the same location.

This situation is known as a **collision**:

> Two distinct keys are assigned to the same bucket by the hash function.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1744104809745/3e95633c-35f9-43cb-bdfd-682c9ce4b71b.png align="center")

Collisions are not rare edge cases — they’re an expected reality. Anytime you try to map a wide range of inputs (keys) into a limited number of outputs (buckets), overlaps are inevitable.

Which means the system needs to make an internal decision: *How do I store both values without overwriting one?*

So the real question becomes:

> **How does a** `HashMap` gracefully handle collisions — and still maintain its performance guarantees?

In other words: how does it stay fast — *even when things go wrong?*

With the help of collision handling strategies.

---

## Collision Handling Strategies

### 🔄 1. Linear Probing

One of the simplest techniques is **Linear Probing**. When a collision occurs, the map simply checks the next available bucket.

If that's full too? It checks the next one — wrapping around to the start if needed — until it finds an empty spot.

#### 🍽 Kitchen Analogy:

Drawer 7 is full with sugar (key 17). Salt (key 67) also hashes to 7. Mom peeks into drawer 8. If 8 is full, she checks 9, 10, then loops back to 0, 1...

#### 📊 Linear Probing Table Example:

Let’s say the table size is `10`. We try to insert the following keys:

| Key | Hash (key % 10) | Final Position |
| --- | --- | --- |
| 17 | 7 | 7 |
| 67 | 7 → 8 | 8 |
| 97 | 7 → 8 → 9 | 9 |
| 27 | 7 → 8 → 9 → 0 | 0 |

#### 🧠 Internal View:

* Simple to implement and understand
    
* Efficient cache performance due to locality of reference
    

#### ❌ Cons:

* Suffers from **primary clustering** — items with same hash crowd together
    
* Insertions can slow down under high load
    

---

### 🔗 2. Chaining

In **Chaining**, each bucket contains a list or chain of entries. If multiple keys hash to the same bucket, they’re added to the list at that location.

#### 🍽 Kitchen Analogy:

Drawer 7 already has sugar. Now salt also belongs to 7. Mom adds a divider and keeps both in the same drawer — labeled neatly.

#### 🧰 Bucket Representation:

Here’s what drawer 7 would look like if we used chaining:

```java
Bucket 7:
  ┌───────────────┐
  │ 17 | Sugar    │
  ├───────────────┤
  │ 67 | Salt     │
  ├───────────────┤
  │ 97 | Jam      │
  └───────────────┘
```

#### 🔍 Under the Hood:

Each entry is stored as a `(key, value)` pair, often wrapped in a linked list:

```java
7 → [ 17 | Sugar ] → [ 67 | Salt ] → [ 97 | Jam ]
```

During retrieval, the map walks through the list, comparing keys using `.equals()` until it finds the match.

#### ✅ Pros:

* Easy to implement and visualize
    
* Load factor can exceed 1
    

#### ❌ Cons:

* Worst-case lookup degrades to O(n)
    
* Extra memory for linked lists
    

---

### 🔁 3. Double Hashing

**Double Hashing** applies a second hash function to compute a jump interval, reducing clustering and giving each key a more unique probe sequence.

#### 🍽 Kitchen Analogy:

Drawer 7 is full. Instead of checking 8, 9... Mom says, "Let’s jump by 3 drawers." If that’s full, she jumps another 3. The jump size depends on the item.

#### 🧮 Calculation:

```java
hash1 = key % size;
hash2 = prime - (key % prime);
index = (hash1 + i * hash2) % size;
```

#### Example:

Assume: `size = 10`, `prime = 7`

| Key | hash1 | hash2 | Probes |
| --- | --- | --- | --- |
| 17 | 7 | 4 | 7 |
| 67 | 7 | 3 | 7 → 0 |
| 97 | 7 | 1 | 7 → 8 |
| 107 | 7 | 5 | 7 → 2 |

**Final Table:**

```java
0 → 67 → Salt
2 → 107 → Jam
7 → 17 → Sugar
8 → 97 → Coffee Beans
```

#### ✅ Pros:

* Reduces clustering significantly
    
* No linked list or extra memory
    

#### ❌ Cons:

* More complex logic
    
* Needs a good secondary hash to avoid cycles
    

> 🧂 **Real Talk:** Moms don’t do double hashing.  
> They don’t need to. Their drawers are organized from day one.  
> We engineers? We create the chaos and then invent skip logic to fix it.

---

## Cleaning Up — But Not Quite Done Yet

So far, we’ve built a pretty solid kitchen system:

* A way to calculate where to store things (`hashing`)
    
* Strategies to handle drawer collisions (`linear probing`, `chaining`, `double hashing`)
    

Honestly, for many use cases — that’s enough.

Put an item, get it back later. Boom. HashMap magic.

But then…

> One day you open your kitchen drawer… and it’s full.  
> Not just one drawer — *everything* is full.  
> You try putting one more item in… and suddenly, the system **collapses**.

Lookups slow down. Everything feels stuck. The magic is gone.

That’s when you realize: **It’s not just about putting things in the right place. It’s also about knowing when to grow.**

---

> Ever notice how your mom's kitchen never seems to run out of space?  
> No matter how many new packets arrive — there’s always room. Always structure.  
> First we saw how moms are hashing geniuses...  
> Next, we'll see why they’re rehashing geniuses too.

---

### Up Next:

[**Moms are Hashmapping Geniuses – Part 2**  
*Rehashing, Load Factor and an Ever Expanding Kitchen*](https://theharshtech.hashnode.dev/moms-are-hashmapping-geniuses-rehashing-load-factor-and-an-ever-expanding-kitchen)

Because when the kitchen gets full, a good system doesn't panic.  
It **reshuffles and comes back stronger.**