HashMap in Java Explained Simply

11 min readSep 22, 2026

Understanding HashMap is one of the most common topics in Java.

It is one of the most commonly used classes when we need to store data in key-value pairs.

For example:

Map<String, Integer> marks = new HashMap<>();
marks.put("Java", 90);
marks.put("Spring Boot", 85);
marks.put("SQL", 80);

Using a HashMap is easy.

But what actually happens internally when we write:

marks.put("Java", 90);

How does Java decide where to store "Java"?

And when we write:

marks.get("Java");

How does Java find the value so quickly?

What happens when two different keys end up in the same location?

To answer these questions, let’s understand how HashMap works internally.

What Is a HashMap?

HashMap is a class in Java that stores data in the form of key-value pairs.

HashMap<Key, Value>

For example:

HashMap<Integer, String> employees = new HashMap<>();
employees.put(101, "Riya");
employees.put(102, "Priya");
employees.put(103, "Amit");

Here:

101 → Riya
102 → Priya
103 → Amit

Each key is associated with one value.

A HashMap allows:

One null key
Multiple null values
Duplicate values
Unique keys

If we insert the same key again:

employees.put(101, "Neha");

The previous value "Riya" is replaced.

Now:

101 → Neha
102 → Priya
103 → Amit

What Does HashMap Use Internally?

At a high level, HashMap uses an array of buckets.

Each bucket can contain one or more entries.

A simplified view looks like this:

HashMap
   |
   ↓
Internal Array
   |
   +---- Bucket 0
   |
   +---- Bucket 1
   |
   +---- Bucket 2
   |
   +---- Bucket 3
   |
   +---- Bucket 4
   |
   +---- ...

When we add a key-value pair, Java calculates a hash for the key.

That hash is then used to determine which bucket should contain the entry.

So the basic idea is:

Key
 ↓
hashCode()
 ↓
Hash
 ↓
Bucket Index
 ↓
Store Entry

Let’s understand each step.

What Happens When We Call put()?

Consider:

Map<String, Integer> marks = new HashMap<>();
marks.put("Java", 90);

When put() is called, Java roughly performs the following steps:

"Java"
   ↓
hashCode()
   ↓
Hash calculation
   ↓
Bucket index calculation
   ↓
Check bucket
   ↓
Store key-value pair

Let’s break this down.

Step 1: Java Calculates the Hash

Every Java object has a hashCode() method inherited from Object.

For example:

String key = "Java";
int hash = key.hashCode();

The returned integer is used by HashMap as part of the process of finding the bucket.

Conceptually:

"Java"
   ↓
hashCode()
   ↓
some integer hash

The important thing to understand is that the hash helps HashMap quickly determine where the entry should be stored.

Step 2: HashMap Finds the Bucket

The hash itself is not used directly as an array index.

HashMap calculates an index from the hash and the current table size.

Conceptually:

hash
 ↓
bucket index
 ↓
internal array[index]

In modern Java implementations, the calculation is optimized around the fact that the table size is a power of two.

You may see code similar to:

index = (n - 1) & hash;

where n represents the table length.

You don’t need to memorize the formula to understand the main idea.

The important point is:

The hash is used to determine which bucket should be checked.

What Is a Bucket?

A bucket is simply a position in the internal array where a HashMap entry can be stored.

For example:

Index

0
1
2  → [Java, 90]
3
4
5

If the calculated bucket index for "Java" is 2, the entry is stored at bucket 2.

Internally, the entry contains information such as:

hash
key
value
next

A simplified representation is:

+----------------+
| hash           |
| key            |
| value          |
| next           |
+----------------+

In Java’s implementation, this is represented by internal node structures.

But What If Two Keys Get the Same Bucket?

This is where things become interesting.

Suppose we have two different keys:

Key A
Key B

After hashing and bucket calculation, both happen to point to the same bucket.

This is called a hash collision.

For example:

Bucket 5
       ↓
[Key A, Value A]
       |
       ↓
[Key B, Value B]

Different keys can have the same bucket.

This is completely normal.

So how does HashMap handle it?

How Does HashMap Handle Collisions?

Historically, collisions are handled using a linked structure.

A simplified representation looks like this:

Bucket 5
   |
   ↓
[Key A | Value A | next]
                    |
                    ↓
             [Key B | Value B | next]
                                  |
                                  ↓
                           [Key C | Value C]

When multiple entries belong to the same bucket, they can be connected together.

This allows the HashMap to search through the entries in that bucket.

But there is a problem.

What if a bucket contains a very large number of entries?

Searching through a long linked list can become slower.

This is where Java’s treeification feature becomes important.

HashMap and Red-Black Trees

In Java 8 and later, when a bucket becomes sufficiently large, the linked structure can be converted into a Red-Black Tree.

Instead of:

Entry
  ↓
Entry
  ↓
Entry
  ↓
Entry

it can become a tree-like structure:

             Entry
            /     \
        Entry     Entry
        /           \
     Entry          Entry

This can improve lookup performance when many entries collide into the same bucket.

However, treeification does not happen immediately after a few collisions.

Java uses specific thresholds and conditions before converting a bucket into a tree.

The commonly referenced constants in modern OpenJDK implementations include:

TREEIFY_THRESHOLD = 8
UNTREEIFY_THRESHOLD = 6
MIN_TREEIFY_CAPACITY = 64

These are implementation details and can vary across Java versions, so the important concept is:

A heavily populated bucket can be converted from a linked structure into a tree to improve lookup performance.

What Happens When We Call get()?

Now let’s look at the other common operation:

marks.get("Java");

How does Java find 90?

The process is roughly:

"Java"
   ↓
hashCode()
   ↓
Hash calculation
   ↓
Find bucket index
   ↓
Go to bucket
   ↓
Compare entries
   ↓
Find "Java"
   ↓
Return 90

Suppose the bucket contains:

Bucket 3

[Python, 70]
      ↓
[Java, 90]
      ↓
[SQL, 80]

When we call:

marks.get("Java");

Java finds the appropriate bucket and checks the entries.

It doesn’t simply compare hash codes.

It also needs to check the actual key.

This is why both hashCode() and equals() are important.

Why Are hashCode() and equals() Important?

This is one of the most important concepts to understand when working with HashMap.

Suppose we create our own class:

class Employee {
    private int id;
    private String name;
    public Employee(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

Now imagine using it as a key:

Map<Employee, String> employees = new HashMap<>();

For custom objects, we need to properly implement equals() and hashCode() when logical equality is intended.

For example:

@Override
public int hashCode() {
    return id;
}
@Override
public boolean equals(Object obj) {
    if (this == obj) {
        return true;
    }
    if (!(obj instanceof Employee)) {
        return false;
    }
    Employee other = (Employee) obj;
    return this.id == other.id;
}

The important contract is:

If two objects are equal according to equals(), they must return the same hashCode().

The reverse is not required.

Two different objects can have the same hash code.

That’s one reason collisions are possible.

A Simple Example of hashCode() and equals()

Consider:

Employee e1 = new Employee(101, "Puja");
Employee e2 = new Employee(101, "Puja");

If equals() considers these two employees equal, then:

e1.equals(e2)

should return:

true

And:

e1.hashCode() == e2.hashCode()

should also be:

true

This allows HashMap to correctly locate logically equivalent keys.

What Is the Default Capacity?

A commonly discussed default initial capacity for HashMap is:

This means the internal table can have 16 buckets once initialized.

Conceptually:

0
1
2
3
...
15

However, there is an important detail:

Get Puja Kumari’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

HashMap uses lazy initialization, so creating:

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

doesn’t necessarily mean the internal array is immediately allocated with 16 elements.

The table is initialized when it is first needed.

What Is Load Factor?

Another important concept is the load factor.

The commonly used default load factor is:

0.75

The load factor determines when the HashMap should resize its internal table.

Important: The load factor does not determine how much the capacity increases. It only determines when resizing should happen.

For example:

Capacity = 16
Load Factor = 0.75

The resize threshold is calculated as:

Threshold = Capacity × Load Factor
          = 16 × 0.75
          = 12

So:

Capacity  = 16
Threshold = 12

Here, 16 represents the number of buckets, while 12 represents the point at which the HashMap reaches its resize threshold.

It does not mean that the capacity becomes:

16 + (16 × 0.75) = 28

The load factor is only used to calculate the threshold.

What Happens During Resizing?

Suppose the internal capacity is:

and the number of entries grows beyond the resize threshold:

Capacity = 16
Load Factor = 0.75
Threshold = 12

When the threshold is exceeded, the HashMap needs to resize its internal table.

For the usual growth pattern, the capacity is doubled:

16 → 32

So the new capacity becomes:

The new threshold is then calculated using the same load factor:

New Threshold = 32 × 0.75
              = 24

So the progression looks like:

Capacity = 16
Threshold = 12
        ↓ resize
Capacity = 32
Threshold = 24
        ↓ resize
Capacity = 64
Threshold = 48

A simple way to remember this is:

Load Factor → Determines WHEN to resize
Capacity Growth → Determines HOW MUCH the table grows

The entries then need to be redistributed according to the new table size.

Conceptually:

Before Resize
Capacity = 16
[0] [1] [2] [3] ... [15]
             ↓ resize
After Resize
Capacity = 32
[0] [1] [2] [3] ... [31]

During resizing, existing entries are redistributed into the new table. Because HashMap uses power-of-two capacities, an entry can often either stay at its current index or move to an index offset by the old capacity.

For example, with an old capacity of 16, an entry at index 5 can remain at:

or move to:

5 + 16 = 21

depending on its hash.

Resizing can be an expensive operation because the table needs to be expanded and existing entries need to be redistributed.

This is one reason choosing a reasonable initial capacity can sometimes be useful when you already know approximately how many entries the HashMap will contain.

Why Does HashMap Use a Load Factor of 0.75?

There is a trade-off.

If the map resizes too frequently:

More resizing
→ More work

If the map allows too many entries in the same table:

More collisions
→ Potentially slower lookup

The load factor provides a balance between memory usage and performance.

The default of 0.75 is a commonly used practical choice in Java's implementation.

Is HashMap Really O(1)?

You will often hear:

HashMap provides O(1) average-time for finding a value.

That’s broadly correct for a well-distributed hash table.

For example:

map.put("Java", 90);
map.get("Java");

The average expected complexity is:

put() → O(1)
get() → O(1)
remove() → O(1)

However, this doesn’t mean every operation always takes exactly constant time.

Performance depends on factors such as:

Hash distribution
Number of collisions
Table resizing
Equality checks
Whether a bucket contains a linked structure or tree

With heavy collisions, finding a value can take longer than the ideal average case.

Is HashMap Thread-Safe?

No.

HashMap is not thread-safe.

If multiple threads modify the same HashMap concurrently without proper synchronization, you can encounter inconsistent behavior.

For concurrent access, Java provides alternatives such as:

ConcurrentHashMap

For example:

Map<String, Integer> map = new ConcurrentHashMap<>();

The right collection depends on the application’s concurrency requirements.

Can HashMap Have a Null Key?

Yes.

A HashMap allows:

Map<String, Integer> map = new HashMap<>();
map.put(null, 100);

It can also contain multiple null values:

map.put("Java", null);
map.put("Spring", null);

So:

Null keys   → One
Null values → Multiple

HashMap Internals at a Glance

Let’s put everything together.

                 put(key, value)
                         |
                         ↓
                  key.hashCode()
                         |
                         ↓
                    Hash value
                         |
                         ↓
                  Bucket index
                         |
                         ↓
                  Internal array
                         |
              ┌──────────┴──────────┐ 
              ↓                     ↓ 
           Empty bucket         Existing entry 
              ↓                     ↓ 
            Store            hash + equals() 
                                    | 
                           ┌────────┴────────┐ 
                           ↓                 ↓ 
                        Same key         Different key 
                           ↓                 ↓ 
                       Update value       Collision 
                                             | 
                                   ┌─────────┴─────────┐ 
                                   ↓                   ↓ 
                              Linked structure    Red-Black Tree 
                                                    (Java 8+)

This is the basic idea behind how HashMap works.

What If Two Keys Are the Same?

An important point is that a collision does not necessarily mean the keys are the same.

Suppose we have:

map.put("Java", 90);
map.put("Java", 95);

Here, "Java" is the same key.

When the second put() happens, HashMap finds the existing key and uses equals() to confirm that the keys are equal.

Instead of creating another entry, HashMap updates the existing value:

Before:
"Java" → 90

After:
"Java" → 95

So:

map.get("Java");

returns:

This means a HashMap cannot contain two separate entries with equal keys.

However, two different keys can still end up in the same bucket. That is a collision.

For example:

Different keys
     ↓
Same bucket
     ↓
Collision
     ↓
Linked Structure / Red-Black Tree

So remember the difference:

Same key → Existing value is replaced
Different keys, same bucket → Collision occurs
Different keys, different buckets → Both are stored separately

This distinction is important when understanding how HashMap handles keys internally.

What Is a Red-Black Tree in HashMap?

We have already seen that collisions can occur when multiple keys end up in the same bucket.

Before Java 8, a bucket mainly used a linked list to store entries when collisions occurred.

From Java 8, HashMap introduced an optimization for buckets that contain many entries: the linked structure can be converted into a Red-Black Tree.

A Red-Black Tree is a type of self-balancing Binary Search Tree.

Each node is assigned one of two colors:

Red
Black

The tree follows certain rules to keep itself balanced. Because of this balancing, searching, inserting, and deleting elements in the tree can generally be performed in:

O(log n)

This is useful when many keys end up in the same bucket.

Conceptually:

Few collisions
Bucket
  ↓
Entry → Entry → Entry → Entry
        Linked Structure

Many collisions
     Bucket
       ↓
     Entry
     /   \
 Entry   Entry
 /  \      \
...  ...   ...
 Red-Black Tree

HashMap does not immediately create a Red-Black Tree whenever a collision happens.

In Java 8+, when a bucket becomes heavily populated, HashMap can convert that bucket into a tree. Treeification also depends on the table capacity. If the table is still small, HashMap may resize the table instead of immediately creating a tree.

The commonly known thresholds in the Java implementation are:

TREEIFY_THRESHOLD      = 8
UNTREEIFY_THRESHOLD    = 6
MIN_TREEIFY_CAPACITY   = 64

TREEIFY_THRESHOLD = 8
When a bucket becomes heavily populated, around 8 entries, HashMap may convert the linked list into a Red-Black Tree.
UNTREEIFY_THRESHOLD = 6
If a tree bucket becomes smaller, around 6 entries, HashMap can convert it back into a linked list.
MIN_TREEIFY_CAPACITY = 64
HashMap generally treeifies a bucket only when the table has at least 64 buckets. If the table is smaller, it prefers to resize first.

Easy to Remember

8 → Tree
6 → Linked List
64 → Minimum table capacity for treeification

So, it is better to remember this as:

Java 8 introduced Red-Black Trees in heavily collided HashMap buckets to improve performance when many entries accumulate in the same bucket.

Final Takeaway

HashMap may look simple from the outside:

map.put("Java", 90);
map.get("Java");

But internally, several things happen.

The overall flow is:

Key
 ↓
hashCode()
 ↓
Hash calculation
 ↓
Bucket index
 ↓
Check existing entries
 ↓
No collision → Store entry
        OR
Collision → Compare hash + equals()
        ↓
  Linked Structure / Red-Black Tree

The most important points to remember are:

HashMap stores data as key-value pairs.
It uses an internal array of buckets.
hashCode() helps determine where a key should be stored.
Different keys can produce the same bucket index, causing a collision.
equals() is used to determine whether two keys are actually equal.
Since Java 8, heavily populated buckets can be converted into Red-Black Trees.
The default load factor is 0.75.
Load factor determines when resizing happens, not how much the capacity increases.
HashMap normally grows its capacity by doubling it, such as 16 → 32 → 64.
put(), get(), and remove() have O(1) average expected time, assuming a good distribution of hashes.
HashMap is not thread-safe for concurrent modifications.

Once you understand hashing → buckets → collisions → treeification → resizing, the internal working of HashMap becomes much easier to understand.

Final Interview Question

If an interviewer asks:

“How does HashMap work internally?”

A simple answer is:

HashMap stores key-value pairs in an array of buckets. When we insert a key, HashMap uses its hashCode() to calculate a bucket location. If the bucket is empty, the entry is stored there. If another entry already exists, HashMap handles the collision by comparing the hash and using equals(). Since Java 8, heavily populated buckets can be converted into Red-Black Trees to improve performance. HashMap also resizes when the number of entries crosses the threshold determined by the load factor.

HashMap in Java Explained Simply

What Is a HashMap?

What Does HashMap Use Internally?

What Happens When We Call put()?

Step 1: Java Calculates the Hash

Step 2: HashMap Finds the Bucket

What Is a Bucket?

But What If Two Keys Get the Same Bucket?

How Does HashMap Handle Collisions?

HashMap and Red-Black Trees

What Happens When We Call get()?

Why Are hashCode() and equals() Important?

A Simple Example of hashCode() and equals()

What Is the Default Capacity?

Get Puja Kumari’s stories in your inbox

What Is Load Factor?

What Happens During Resizing?

Why Does HashMap Use a Load Factor of 0.75?

Is HashMap Really O(1)?

Is HashMap Thread-Safe?

Can HashMap Have a Null Key?

HashMap Internals at a Glance

What If Two Keys Are the Same?

What Is a Red-Black Tree in HashMap?

Easy to Remember

Final Takeaway

Final Interview Question

Written by Puja Kumari

No responses yet

More from Puja Kumari

Java Developer Interview Questions— Part 1

If you are preparing for a Java Developer interview with around 2 years of experience, you will often be asked questions that test both…

Understanding @Transactional in Spring Boot: Commit, Rollback, Propagation & Real-World Examples

A practical guide to transaction management in Spring Boot, including commit, rollback, and propagation.

Sorting in Java: Understanding the Basics and Built-in Sorting

Sorting is one of the most common operations in programming.

Java 21 Features You Should Know

Working with Java backend technologies such as Spring Boot, REST APIs, and Microservices, I’ve found that keeping up with newer Java…

Recommended from Medium

Java 17 Features and Interview Questions and Answers

Java 17 is a Long-Term Support (LTS) release with many modern language, JVM, and API improvements. Here are the most important features…

Senior Java Interview Questions and Answers: 30 Advanced Questions for Experienced Backend…

These are not Java syntax questions. They test JVM behavior, concurrency, Spring transactions, database contention, virtual threads…

40 Java Backend Interview Questions to Prepare for in 2026 | 25–30 LPA Salary Range

Preparing for a senior Java backend developer role in 2026? For positions offering compensation in the ₹25–30 LPA range, interviewers often…

Java Multithreading Mastery #2 — Creating Your First Thread (Understanding Thread Class and run())

In Day 1, Java automatically gave us one thread — the Main Thread. But what if one thread isn’t enough? Today, we’ll learn how to create…

5 Java Stream API coding questions I have been asked in interviews

Java Stream API coding questions to prepare for interviews beyond basics

Java 8 Stream API Interview Questions Using Employee Class

11 practical Stream API problems every Java developer with 3–5 years of experience should practice.

No responses yet

More from Puja Kumari

Java Developer Interview Questions— Part 1

If you are preparing for a Java Developer interview with around 2 years of experience, you will often be asked questions that test both…

Understanding @Transactional in Spring Boot: Commit, Rollback, Propagation & Real-World Examples

A practical guide to transaction management in Spring Boot, including commit, rollback, and propagation.

Sorting in Java: Understanding the Basics and Built-in Sorting

Sorting is one of the most common operations in programming.

Java 21 Features You Should Know

Working with Java backend technologies such as Spring Boot, REST APIs, and Microservices, I’ve found that keeping up with newer Java…

Recommended from Medium

Java 17 Features and Interview Questions and Answers

Java 17 is a Long-Term Support (LTS) release with many modern language, JVM, and API improvements. Here are the most important features…

Senior Java Interview Questions and Answers: 30 Advanced Questions for Experienced Backend…

These are not Java syntax questions. They test JVM behavior, concurrency, Spring transactions, database contention, virtual threads…

40 Java Backend Interview Questions to Prepare for in 2026 | 25–30 LPA Salary Range

Preparing for a senior Java backend developer role in 2026? For positions offering compensation in the ₹25–30 LPA range, interviewers often…

Java Multithreading Mastery #2 — Creating Your First Thread (Understanding Thread Class and run())

In Day 1, Java automatically gave us one thread — the Main Thread. But what if one thread isn’t enough? Today, we’ll learn how to create…

5 Java Stream API coding questions I have been asked in interviews

Java Stream API coding questions to prepare for interviews beyond basics

Java 8 Stream API Interview Questions Using Employee Class

11 practical Stream API problems every Java developer with 3–5 years of experience should practice.