HashMap Internal Working Explained with Examples

If you've been working with Java for a while, you've probably used HashMap countless times. It's one of the most essential data structures in Java and is widely used in everything from simple applications to large-scale enterprise systems.

Most developers regularly write:

map.put(key, value);

or

map.get(key);

without fully understanding the internal operations happening behind the scenes.

Interestingly, HashMap internals are among the most frequently asked topics in Java interviews because they demonstrate a developer's understanding of data structures, performance optimization, memory management, and JVM fundamentals.

In this article, we'll explore how HashMap works internally, how hashing determines storage locations, how collisions are handled, and why Java 8 introduced major improvements to enhance performance.

🎯 Why Understanding HashMap Is Important

Think about applications such as:

✅ Banking Systems

✅ E-Commerce Platforms

✅ Distributed Cache Solutions

✅ Microservices-Based Applications

Performance matters in all of these systems.

HashMap is specifically designed to provide:

Fast Data Retrieval
Quick Insert Operations
Efficient Memory Usage
O(1) Average Time Complexity

Understanding its internals helps developers:

Write optimized code
Improve application performance
Build scalable systems
Crack technical interviews confidently
📚 What Is HashMap?

HashMap is part of the Java Collections Framework that stores information in Key-Value pairs.

Example:

HashMap employees = new HashMap<>();

employees.put(101, "John");
employees.put(102, "David");
employees.put(103, "Alex");

Output:

101 → John
102 → David
103 → Alex

Each key uniquely identifies its corresponding value.

🏗️ HashMap Internal Architecture

Internally, HashMap uses multiple data structures together:

HashMap
   |
   ├── Array (Buckets)
   |
   ├── Linked Lists
   |
   └── Red Black Trees (Java 8+)

Example Structure:

0 → null
1 → Node
2 → Node → Node
3 → null
4 → Node
5 → Node → Node

Every position inside the array is known as a:

Bucket

Each bucket stores nodes like:

static class Node<K,V> {

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

Each node contains:

Hash Value
Key
Value
Next Node Reference

⚙️ Internal Working of put()

Let's understand what happens internally when data is inserted.

Example:

HashMap<Integer, String> map = new HashMap<>();

map.put(101, "John");
🔹 Step 1: Generate Hash Code

HashMap first calls:

key.hashCode();

Example:

Integer key = 101;

key.hashCode();

Output:

101
🔹 Step 2: Apply Hash Function

Java improves hash distribution using:

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

This minimizes clustering and improves bucket distribution.

🔹 Step 3: Calculate Bucket Index

Formula:

index = (n - 1) & hash

Where:

n = Array Capacity

Default Capacity:

16

Example:

index = (16 - 1) & 101

index = 15 & 101

index = 5

The node will be stored in:

Bucket[5]
🔹 Step 4: Insert Node

If the bucket is empty:

Bucket[5] → Node

Insertion completes immediately.

Average Complexity:

O(1)

💥 What Is a Collision?

A collision occurs when multiple keys are mapped to the same bucket.

Example:

map.put(10, "A");
map.put(26, "B");

Suppose both map to:

Bucket[2]

Storage becomes:

Bucket[2]

A → B

This technique is known as:

Separate Chaining

🔗 Collision Handling in Java 7

Before Java 8, collisions were handled using Linked Lists.

Structure:

Node
 |
Node
 |
Node
 |
Node

Searching required traversing each node sequentially.

Worst-Case Complexity:

O(n)

As collisions increased, performance dropped significantly.

🌳 Java 8 Improvement: Treeification

To solve excessive collision problems, Java 8 introduced:

Red Black Trees

When a bucket contains more than:

8 Nodes

HashMap converts the Linked List into a Red Black Tree.

Before:

A
|
B
|
C
|
D
|
E

After:

       C
      / \
     B   E
    /   / \
   A   D   F

Search complexity improves from:

O(n)

to:

O(log n)

📋 Treeification Rules

Tree conversion occurs only when:

✅ Bucket Size ≥ 8

✅ Capacity ≥ 64

Otherwise, HashMap performs resizing instead.

🔍 Internal Working of get()

Example:

map.get(101);

Execution Flow:

1️⃣ Generate Hash
hashCode()
2️⃣ Calculate Bucket Index
(n - 1) & hash
3️⃣ Navigate to Bucket
Bucket[5]
4️⃣ Compare Values
if(node.hash == hash &&
   node.key.equals(key))

If matched, return the value.

⚠️ Why equals() and hashCode() Matter

HashMap heavily depends on:

hashCode()
equals()

Incorrect implementations may cause:

❌ Duplicate Records

❌ Retrieval Failures

❌ Performance Issues

Example:

class Employee {

    int id;

    @Override
    public int hashCode() {
        return id;
    }

    @Override
    public boolean equals(Object obj) {

        Employee emp = (Employee)obj;

        return this.id == emp.id;
    }
}

🔄 HashMap Resize Mechanism

Default Capacity:

16

Default Load Factor:

0.75

Threshold:

16 × 0.75 = 12

Once entries exceed the threshold, HashMap automatically resizes.

🚀 Rehashing Process

Capacity doubles during expansion:

16 → 32

32 → 64

64 → 128

All entries are redistributed into new buckets.

This process is known as:

Rehashing

⚔️ HashMap vs Hashtable

Feature HashMap Hashtable
Thread Safe No Yes
Performance Faster Slower
Null Keys Allowed Not Allowed
Null Values Allowed Not Allowed
🔥 HashMap vs ConcurrentHashMap

For multi-threaded environments:

ConcurrentHashMap is preferred.

Benefits:

✅ Thread Safety

✅ Better Scalability

✅ Higher Throughput

✅ Reduced Lock Contention

Widely used in:

Microservices
Cloud Applications
Enterprise Platforms
🏢 Real-World Applications of HashMap
💾 Caching

User ID → User Data

👤 Session Management

Session ID → Session Object
**
⚙️ Configuration Storage**

Property Key → Value

🌐 API Response Caching

Request → Response

📦 Inventory Management

Product ID → Product Details

🎤 Popular Interview Questions
❓ Why is HashMap so fast?

Because it uses hashing, buckets, and direct indexing.

❓ What causes collisions?

Multiple keys generating the same bucket index.

❓ Why override equals() and hashCode()?

To ensure proper key comparison and retrieval.

❓ What happens after 8 collisions?

The Linked List can be converted into a Red Black Tree.

❓ What is the default load factor?

0.75

❓ Why only one null key?

All null keys map to the same bucket.

🎯 Key Takeaways

✅ HashMap stores data using key-value pairs.

✅ Buckets are backed by arrays.

✅ Hashing determines storage locations.

✅ Collisions are handled through chaining.

✅ Java 8 introduced Red Black Trees.

✅ Default Capacity = 16.

✅ Default Load Factor = 0.75.

✅ Rehashing occurs when thresholds are exceeded.

✅ equals() and hashCode() are critical.

✅ HashMap remains one of Java's most important data structures.

HashMap may appear simple from the outside, but internally it combines hashing algorithms, bucket indexing, collision management, linked lists, Red Black Trees, and dynamic resizing mechanisms to deliver exceptional performance.

Whether you're preparing for Java interviews, building Spring Boot applications, designing microservices, or developing AI-powered systems, understanding HashMap internals is a foundational skill that will make you a stronger software engineer.

The next time you write:

map.put(key, value);

you'll know exactly what happens behind the scenes.