HashMap in Java

Let’s break down how HashMap works internally (Java 8+ implementation).

---

What Is a HashMap?

HashMap<K, V> is a hash table–based implementation of the Map interface.

It stores data as:

key → value

It provides average O(1) time complexity for:

• put()

• get()

• remove()

---

Core Data Structure

Internally, HashMap uses:

Array of buckets

Each bucket contains:

• A LinkedList (before Java 8)

• A LinkedList OR Red-Black Tree (Java 8+)

Structure simplified:

Node<K,V>[] table

Each array index is called a bucket.

---

How put() Works Internally

When you do:

map.put("apple", 10);

Step 1: Calculate Hash

It calls:

int hash = key.hashCode();

Then applies a hash spreading function:

(hash ^ (hash >>> 16))

This improves distribution.

---

Step 2: Calculate Bucket Index

index = (n - 1) & hash

Where:

• n = array length

• & = bitwise AND (faster than modulo)

This determines where the entry will go.

---

Step 3: Insert into Bucket

Now 3 cases:

Case 1: Bucket is empty

→ Insert new node.

Case 2: Same key already exists

→ Replace value.

Case 3: Collision (different key, same index)

→ Add node to:

• LinkedList (if small)

• Red-Black Tree (if too many collisions)

---

What Is a Collision?

A collision happens when:

Different keys → Same bucket index

Example:

hash("FB") == hash("Ea")

Both go to same bucket.

HashMap handles collisions by chaining.

---

Treeification (Java 8 Improvement)

If a bucket has more than:

8 nodes

It converts the linked list into a:

Red-Black Tree

Why?

• LinkedList lookup = O(n)

• Red-Black Tree lookup = O(log n)

This prevents performance degradation.

---

How get() Works

When you call:

map.get("apple");

Steps:

1. Compute hash

2. Find bucket index

3. Traverse bucket:

   • If LinkedList → iterate

   • If Tree → binary search

4. Compare using:

key.equals(existingKey)

Important:
equals() is used to find the correct key — not ==.

---

Resizing (Rehashing)

Default initial capacity:

16

Default load factor:

0.75

Resize condition:

size > capacity × loadFactor

So:

16 × 0.75 = 12

When 13th element is added:
→ capacity doubles to 32
→ all elements are rehashed

---

Why hashCode() and equals() Matter

HashMap uses:

1. hashCode() → to find bucket

2. equals() → to find exact key inside bucket

If you override one,
you MUST override the other.

Otherwise, HashMap breaks.

---

Internal Node Structure (Simplified)

static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

For tree buckets:

TreeNode extends Node

---

Time Complexity Summary

Operation	Average	Worst Case
put()	O(1)	O(log n)
get()	O(1)	O(log n)
remove()	O(1)	O(log n)

Worst case happens when many collisions occur.

---

Not Thread Safe

HashMap is not synchronized.

For concurrency use:

• ConcurrentHashMap

• Collections.synchronizedMap()

---

Tip

If we ask “How does HashMap work?” we could say in this order:

1. Array of buckets

2. hashCode()

3. Index calculation

4. Collision handling

5. Treeification (Java 8)

6. Resize mechanism

7. equals() importance