Java Collections: HashMap Example

🧩 Understanding Java HashMap — Internal Working Explained Step by Step

The HashMap is one of the most powerful and widely used data structures in Java.
It stores key–value pairs, allowing fast lookups, insertions, and deletions — on average, in O(1) time.

---

⚙️ Key Features of HashMap

• ✅ Stores key–value pairs

• 🚫 Duplicate keys are not allowed (latest value replaces old)

• ⚡ Fast put() and get() operations

• 🔄 Order is not maintained

• ⚠️ Not synchronized (use ConcurrentHashMap for thread safety)

• 💾 Allows one null key and multiple null values

---

💡 Internal Data Structure

Internally, a HashMap is an array of buckets,
and each bucket holds a linked list (or red-black tree, since Java 8) of entries.

Each entry (also called a Node) stores:

• key

• value

• hash (calculated from the key)

• next (a pointer to the next node — used when multiple entries fall into the same bucket)

Array (buckets)
     ↓
[0] → [Key=10, Val=A] → [Key=26, Val=B] → null
[1] → [Key=12, Val=C] → null
[2] → null

This chaining structure is the key to how HashMap handles collisions — when two different keys map to the same bucket index.

---

🧮 Step-by-Step: How put() Works

Let’s take an example:

map.put("Apple", "Red");

Step 1️⃣ Compute Hash Code

HashMap calls the hashCode() method of the key:

int hash = key.hashCode();

For "Apple", this produces an integer (e.g., 63043).

Then HashMap spreads the hash bits using an internal formula to reduce collisions:

hash = hash ^ (hash >>> 16);

---

Step 2️⃣ Find the Bucket Index

The index is computed using modulo on the array size:

index = hash % array_length;

If the array size is 16, and hash = 63043 →
index = 63043 % 16 = 3

So this entry goes into bucket 3.

---

Step 3️⃣ Check for Collision

If bucket 3 is empty → insert a new node directly.

If not empty → traverse the linked list using the next pointer and compare keys using .equals():

• If key already exists → replace its value.

• Otherwise → attach the new entry at the end of the list.

This is why each node has a next pointer — it allows HashMap to connect multiple entries inside the same bucket.

---

Step 4️⃣ Store the Entry

Each entry looks like this internally:

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

When "Apple" is inserted:

table[3] → [hash=63043, key="Apple", value="Red", next=null]

If "Mango" also hashes to index 3:

table[3] → [Apple, Red] → [Mango, Yellow] → null

---

Step 5️⃣ Resize if Needed

When the number of stored entries exceeds the load factor threshold (default = 0.75 × capacity),
the HashMap doubles its capacity and rehashes all entries to new buckets.

This process ensures performance stays close to O(1).

---

🧩 Step-by-Step: How get() Works

When you call:

map.get("Apple");

Here’s what happens:

1️⃣ Compute hash for "Apple" again.
2️⃣ Find bucket index using hash % array_length.
3️⃣ Go to that bucket and check the first node:

• If key matches → return value.

• If not → follow next pointer to check the next node.
  4️⃣ Continue until key is found or next == null.

✅ Result: Returns "Red".

---

🔗 Why the Linked List (and next Pointer) Is Needed

Let’s imagine two different keys produce the same index:

Key	hash(key)	index
"Apple"	63043	3
"Mango"	75395	3

Both fall into bucket 3 — this is a hash collision.

To prevent overwriting existing entries,
HashMap connects them using a linked list.

Bucket[3]
↓
[Key="Apple", Val="Red"] → [Key="Mango", Val="Yellow"] → null

When get("Mango") is called, HashMap checks the first node (Apple), finds no match, then follows the next pointer to Mango and retrieves "Yellow".

👉 Without the linked list, only one entry could exist per bucket — collisions would cause data loss.

---

🌳 Tree Optimization (Since Java 8)

If too many nodes end up in the same bucket (default threshold = 8),
HashMap converts the linked list into a Red-Black Tree.

Why?

• Linked list lookup = O(n)

• Tree lookup = O(log n)

Before (Linked List)
[Apple] → [Mango] → [Banana] → [Grape]

After (Tree)
       [Mango]
       /     \
   [Apple]  [Banana]

This significantly improves performance in worst-case scenarios.

---

🧠 Summary of Internal Workflow

Operation	Description	Complexity
put()	Hash → Index → Insert/Replace → Rehash if needed	O(1) avg, O(n) worst
get()	Hash → Index → Traverse linked list/tree	O(1) avg, O(log n) tree
remove()	Hash → Index → Remove node	O(1) avg
Collision Handling	Linked list (or tree) per bucket	O(n) or O(log n)
Resizing	Doubles capacity when threshold exceeded	O(n) (rehash)

---

🧾 Quick Example

Map<Integer, String> cities = new HashMap<>();
cities.put(1, "Bangalore");
cities.put(2, "Chennai");
cities.put(3, "Cochin");
cities.put(4, "Hyderabad");

System.out.println(cities.get(1)); // Output: Bangalore

Output

Bangalore
Key 1 Value Bangalore
Key 2 Value Chennai
Key 3 Value Cochin
Key 4 Value Hyderabad

---

🧩 Text-Based Visualization

HashMap Internal View
---------------------

     +-------------------------------------------------+
     |                 HashMap Buckets                 |
     +-------------------------------------------------+
        ↓
Index 0 → null
Index 1 → [Key=1, Value="Bangalore"] → null
Index 2 → [Key=2, Value="Chennai"] → null
Index 3 → [Key=3, Value="Cochin"] → [Key=19, Value="Goa"] → null
Index 4 → [Key=4, Value="Hyderabad"] → null

If keys 3 and 19 hash to the same bucket,
they are connected using the next pointer to form a chain.

---

⚠️ Important Notes

• HashMap is not thread-safe — concurrent writes can cause corruption.

• Load factor (default = 0.75) controls how full the table can get before resizing.

• You can specify both initial capacity and load factor when creating:

  Map<K,V> map = new HashMap<>(32, 0.8f);
  

---

✅ Final Takeaways

Concept	Purpose
Bucket Array	Primary storage of entries
Linked List / Tree	Handles collisions
next Pointer	Connects entries within the same bucket
Rehashing	Redistributes keys when capacity grows
O(1) Average Time	Thanks to hash distribution & chaining
O(n) Worst Case	If many keys land in same bucket