Mastering Java HashMap: Internal Mechanics, Pitfalls, and Interview Questions

Most Java developers use HashMap daily, but far fewer understand what happens internally when a key-value pair is inserted or retrieved.

Understanding HashMap internals is important because many production bugs, performance issues, and interview questions revolve around concepts such as hashing, collisions, treeification, and the equals/hashCode contract.

Let’s dive into the concepts first and then test our understanding with some advanced questions.

1. How HashMap Stores Data

HashMap stores data in an internal array called a bucket array.

Each key is processed through its hashCode() method, and the resulting hash value is used to determine which bucket should store the entry.

Simplified flow:

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

A bucket may contain:

• Nothing (empty bucket)
• One node
• Multiple nodes (collision)

2. Collision Handling

Two completely different objects can produce the same bucket index.

This situation is called a collision.

Example:

map.put(key1, "A");
map.put(key2, "B");

Even if key1 and key2 are different, they may end up in the same bucket.

When this happens, HashMap stores multiple entries inside that bucket and uses equals() to distinguish between them.

3. The Equals and HashCode Contract

HashMap relies on both methods.

Rule:

If two objects are equal,
they MUST return the same hashCode.

Valid:

obj1.equals(obj2) == true
obj1.hashCode() == obj2.hashCode()

Invalid:

obj1.equals(obj2) == true
obj1.hashCode() != obj2.hashCode()

Breaking this rule causes retrieval failures and duplicate logical keys.

4. Java 8 Treeification

Before Java 8, collisions were handled using linked lists.

Large numbers of collisions caused lookup performance to degrade:

O(1) → O(n)

To solve this problem, Java 8 introduced treeification.

When a bucket becomes heavily populated, the linked list is converted into a Red-Black Tree.

Complexity improves to:

O(log n)

This protects applications from severe performance degradation caused by hash collisions.

Note: If wanted to more about Collisions, Key Replacement, and Lookup in HashMap with example check below

Question 1: The Basics (Internal Storage)

How does a HashMap decide exactly where to store a key-value pair when you call .put(K, V)? What happens internally if two different keys end up pointing to the exact same location?

Answer

When put() is called:

Step 1: Generate Hash

HashMap calls:

key.hashCode()

and performs an additional bit-mixing operation to improve distribution.

Step 2: Calculate Bucket Index

The bucket is determined using:

hash & (capacity - 1)

This calculation determines where the entry should be stored.

Step 3: Check Bucket

If the bucket is empty:

Insert new node

If the bucket already contains entries:

Collision detected

Step 4: Compare Keys

HashMap uses:

equals()

to determine whether:

• an existing key should be updated
• a new node should be added

Result:

Same key    → Update value
Different key → Add new node

Question 2: The Contract (Equals & HashCode)

What are the consequences if you override equals() in a custom object but forget to override hashCode(), and then use that object as a key in a HashMap?

Answer

Suppose:

User user1 = new User(101);
User user2 = new User(101);

and:

user1.equals(user2) == true

but hashCode() is not overridden.

The default implementation from Object is used.

As a result:

user1.hashCode() != user2.hashCode()

Consequence 1: Duplicate Logical Keys

map.put(user1, "Admin");
map.put(user2, "Manager");

HashMap places them into different buckets.

Instead of updating the existing entry, it creates two separate records.

Consequence 2: Retrieval Failure

Later:

map.get(new User(101));

may return:

null

because the new object’s hash code points to a different bucket.

Consequence 3: Data Appears Missing

The data exists inside the map.

HashMap simply looks in the wrong bucket because the hash codes don’t match.

This is one of the most common HashMap bugs seen in production systems.

Question 3: The Evolution (Java 8 Performance)

In Java 8, the internal storage mechanism for handling collisions was upgraded. What change was made, what is the specific trigger condition for this change, and why was it introduced?

Answer

Before Java 8:

Bucket
 ↓
Linked List

Every lookup inside a crowded bucket required a linear scan.

Worst-case complexity:

O(n)

The Upgrade

Java 8 introduced:

Linked List
      ↓
Red-Black Tree

for heavily populated buckets.

Trigger Conditions

Treeification occurs when:

Bucket Size > 8

and

Map Capacity >= 64

Both conditions must be satisfied.

Why Was It Introduced?

Without treeification:

Many collisions
        ↓
Long linked lists
        ↓
Slow lookups

With treeification:

Many collisions
        ↓
Balanced tree
        ↓
O(log n) lookups

This significantly improves worst-case performance.

Question 4: The Edge Case (Memory & Performance)

Imagine you have a HashMap where the keys are a custom User object. Over time, you notice that fetching values from the map is getting slower and slower (O(n) time complexity), and the application is experiencing high memory usage.

Assuming the keys are not changing after insertion, what is the most likely root cause in the User class?

Answer

The most likely problem is a poor hashCode() implementation.

Example:

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

Every User object generates the same hash value.

Result:

User1
User2
User3
User4
User5
...

all end up in the same bucket.

Effects

1. Performance Degradation

Every lookup requires scanning many entries:

get()
 ↓
equals()
 ↓
equals()
 ↓
equals()
 ↓
equals()

Performance gradually approaches:

O(n)

2. Increased CPU Usage

HashMap must repeatedly call:

equals()

to find the correct entry.

3. Increased Memory Usage

Large collision chains require additional node objects and references.

The bucket becomes heavily congested.

What Should Be Investigated?

Review:

hashCode()

and verify that:

• it uses fields that uniquely identify the object
• it distributes values evenly
• it is consistent with equals()

A poorly designed hashCode() method is one of the most common causes of HashMap performance issues in production.

Question 5: The Silent Killer (Mutable Keys)

Consider the following code:

User user = new User(101);

map.put(user, "Alice");

user.setId(202);

System.out.println(map.get(user));

Why might the lookup return null even though we are using the exact same object reference?

Answer

HashMap determines the storage bucket using the key’s hashCode() at insertion time.

Initially:

user.hashCode() -> 101

The entry is stored in a bucket based on that hash.

After:

user.setId(202);

the hashCode changes:

user.hashCode() -> 202

Now HashMap searches a completely different bucket.

The entry still exists in the old bucket, but HashMap no longer knows where to find it.

This is why keys used in a HashMap should generally be immutable.

Question 6: Capacity vs Size vs Threshold

A developer creates:

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

After inserting 10 elements:

map.size();

returns 10.

What is the difference between:

• Capacity
• Size
• Threshold

Answer

Capacity

Number of buckets available.

Example:

16

Size

Actual number of stored key-value pairs.

Example:

10

Threshold

Point at which resizing occurs.

Formula:

threshold = capacity × loadFactor

Default load factor:

0.75

Therefore:

16 × 0.75 = 12

When the 13th element is inserted, resizing begins.

Question 7: Why is the Default Load Factor 0.75?

Why didn’t Java choose:

1.0

or

0.5

as the default?

Answer

Load factor controls the balance between:

• Memory usage
• Collision probability

Load Factor = 1.0

Pros:

• Better memory utilization

Cons:

• More collisions

Load Factor = 0.5

Pros:

• Fewer collisions

Cons:

• More memory consumption

Java’s designers found:

0.75

to be a practical compromise between speed and memory.

Question 8: What Happens During Resizing?

Suppose a HashMap reaches its threshold.

What exactly happens internally?

Answer

The bucket array size doubles.

Example:

16 → 32

HashMap then redistributes all existing entries into the new buckets.

This process is called:

Rehashing

Although individual lookups are usually O(1), resizing itself is expensive because every existing entry must be relocated.

This is why large applications often pre-size HashMaps.

Question 9: Why Does HashMap Use Powers of Two?

Why are bucket capacities:

16
32
64
128
256

instead of:

15
30
100
250

Answer

HashMap calculates bucket positions using:

hash & (capacity - 1)

Bitwise operations are significantly faster than modulo operations.

Example:

hash % 16

can be replaced with:

hash & 15

This optimization only works efficiently when capacity is a power of two.

Question 10: Can Two Objects Have the Same HashCode?

Is the following legal?

obj1.hashCode() == obj2.hashCode()

but

obj1.equals(obj2) == false

Answer

Yes.

This situation is called a:

Hash Collision

HashMap expects collisions to happen.

When two keys land in the same bucket:

hashCode()
     ↓
same bucket
     ↓
equals()

equals() is used to identify the correct entry.

Hash collisions are normal.

Incorrect equals()/hashCode() implementations are not.

Question 11: Worst-Case Complexity of HashMap

What is the worst-case complexity of:

map.get(key);

Answer

Java 7

Buckets used linked lists only.

Worst case:

O(n)

because every node in the list may need to be scanned.

Java 8+

Buckets can become Red-Black Trees.

Worst case:

O(log n)

after treeification.

This was one of the most important HashMap performance improvements.

Question 12: The Production Memory Leak

A HashMap keeps growing.

The application never intentionally inserts duplicate users.

Eventually:

OutOfMemoryError

occurs.

What bug might exist in the key class?

Answer

A common cause is:

equals() implemented
hashCode() broken

Example:

@Override
public boolean equals(Object o) {
    return id == ((User)o).id;
}

but

@Override
public int hashCode() {
    return super.hashCode();
}

Logically identical users are treated as different keys and repeatedly inserted.

The map grows forever.

Question 13: Why Doesn’t HashMap Use hashCode() Alone?

If hashCode() already determines the bucket, why is equals() still needed?

Answer

Different objects can produce identical hash codes.

Example:

obj1.hashCode() == obj2.hashCode()

does not imply:

obj1.equals(obj2)

Without equals(), HashMap would not know which entry is the correct one inside a collision bucket.

hashCode() narrows the search.

equals() confirms the exact key.

Question 14: Can HashMap Store Duplicate Keys?

Consider:

map.put("A", 1);
map.put("A", 2);

How many entries exist afterward?

Answer

Only one.

HashMap first finds the bucket.

Then:

existingKey.equals(newKey)

returns:

true

Therefore the old value is replaced.

Final state:

A -> 2

Size remains:

1

Question 15: Initial Capacity Optimization

You know beforehand that a HashMap will store approximately:

100,000

records.

Why is this better?

new HashMap<>(131072);

instead of:

new HashMap<>();

Answer

Without pre-sizing:

16
 ↓
32
 ↓
64
 ↓
128
 ↓
...

Multiple expensive resize operations occur.

Each resize requires:

Allocate new bucket array
+
Rehash existing entries

Pre-sizing avoids repeated rehashing and improves insertion performance significantly for large datasets.

Production Scenarios: Can You Find the Bug?

Scenario 1: The Growing Linked List

A payment service stores transactions in a HashMap using a custom Transaction object as the key.

After several months:

• CPU usage increases
• Request latency increases
• Memory usage grows
• Profiling shows thousands of equals() calls during lookups

The developers discover that nearly all entries are ending up in the same bucket.

What is the most likely root cause?

Answer

The Transaction class probably has a poor hashCode() implementation.

Example:

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

Every key lands in the same bucket.

As the bucket grows:

Bucket 5
 ├── Tx1
 ├── Tx2
 ├── Tx3
 ├── Tx4
 ├── Tx5
 ...

HashMap must repeatedly call equals() to locate entries.

The result is:

More CPU
More memory
Slower lookups

Scenario 2: The Missing Customer

A banking application stores customers using:

HashMap<Customer, Account>

The customer class contains:

equals()

but does not override:

hashCode()

A developer inserts:

Customer c1 = new Customer(101);
map.put(c1, account);

Later:

Customer c2 = new Customer(101);
map.get(c2);

returns:

null

even though the customer exists.

Why?

Answer

The two objects are logically equal.

c1.equals(c2) == true

However:

c1.hashCode() != c2.hashCode()

HashMap searches a different bucket and never finds the entry.

This is a direct violation of the equals/hashCode contract.

Scenario 3: The Vanishing Employee

An HR system uses:

HashMap<Employee, Salary>

as a cache.

The Employee class contains:

id
name
department

The id field participates in hashCode().

After insertion:

employee.setId(999);

Suddenly:

map.get(employee)

returns null.

Why?

Answer

The key became mutable.

HashMap stored the entry using the old hash value.

After changing id:

Old hash → Bucket 3
New hash → Bucket 12

HashMap now searches Bucket 12 while the entry still lives in Bucket 3.

The object exists but becomes effectively unreachable.

Scenario 4: The Treeification Mystery

A bucket now contains:

9 elements

A developer expects Java 8 to convert it into a Red-Black Tree.

However, treeification never happens.

Why?

Answer

Many developers remember:

TREEIFY_THRESHOLD = 8

but forget the second condition.

Treeification occurs only when:

Bucket Size > 8
AND
Map Capacity >= 64

If capacity is less than 64, HashMap prefers resizing the entire table rather than creating a tree.

The developer should investigate:

map.capacity()

rather than focusing only on bucket size.

Scenario 5: The Memory Leak Nobody Could Explain

An e-commerce application stores products in:

HashMap<Product, Inventory>

Months later:

Heap usage continuously grows

Yet business logs show no duplicate product IDs.

Investigation reveals:

equals()

compares productId,

while:

hashCode()

uses SKU.

What is happening?

Answer

Two logically identical products can generate different hash codes.

HashMap places them into different buckets.

Instead of updating existing entries:

put(product)

creates new ones repeatedly.

The map grows forever and eventually causes:

OutOfMemoryError

Scenario 6: The Interview Trick Question

Imagine a HashMap where:

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

for every key.

The map contains 1 million entries.

Will Java 8 always guarantee O(log n) lookups because of treeification?

Answer

Not necessarily.

Treeification requires:

Bucket Size > 8
AND
Capacity >= 64

In addition, tree performance works best when keys can be meaningfully ordered.

The real issue remains the terrible hash function.

Treeification reduces the damage but does not fix the root cause.

The correct solution is to implement a well-distributed hashCode().

ADDITIONAL:

Understanding Collisions, Key Replacement, and Lookup in HashMap

One of the most misunderstood parts of HashMap is what happens when two objects have the same hash code and how HashMap decides whether to replace an existing value or store a new entry.

To understand this, remember:

hashCode() → Determines WHICH bucket to search
equals()   → Determines WHICH key inside that bucket matches

Scenario 1: Same HashCode + equals() Returns True

Suppose:

User user1 = new User("Alice", 20);
User user2 = new User("Alice", 20);

Assume:

user1.hashCode() == user2.hashCode()
user1.equals(user2) == true

Now:

map.put(user1, "Admin");
map.put(user2, "Manager");

What Happens Internally?

Step 1:

user1.hashCode()
     ↓
Bucket 4

HashMap stores:

Bucket 4
└── [Alice,20] -> Admin

Step 2:

When inserting user2:

user2.hashCode()
     ↓
Bucket 4

HashMap finds an existing key in Bucket 4.

It then executes:

user2.equals(user1)

Result:

true

HashMap concludes:

This is the SAME logical key.

Instead of creating a new entry, it updates the value.

Final state:

Bucket 4
└── [Alice,20] -> Manager

Map size:

1

The old value is replaced.

Scenario 2: Same HashCode + equals() Returns False

Suppose:

User user1 = new User("Alice", 20);
User user2 = new User("Ben", 30);

Assume:

user1.hashCode() == user2.hashCode()

but:

user1.equals(user2) == false

This is called a:

Hash Collision

Now:

map.put(user1, "Admin");
map.put(user2, "Manager");

Both keys map to the same bucket.

HashMap checks:

user2.equals(user1)

Result:

false

HashMap concludes:

Different keys

and stores both entries.

Result:

Bucket 4

[Alice -> Admin]
       ↓
[Ben -> Manager]

Map size:

2

No replacement occurs.

Why the Equals/HashCode Contract Exists

HashMap relies on the following rule:

If equals() returns true,
hashCode() MUST return the same value.

Reason:

Equal Objects
      ↓
Same HashCode
      ↓
Same Bucket
      ↓
equals() finds the match
      ↓
Correct value returned

Without this guarantee, HashMap would search the wrong bucket and never find the key.

How Lookup Works Internally

Consider:

User user1 = new User("Alice", 20);

map.put(user1, "Admin");

Internally:

user1.hashCode() = 100

Bucket calculation:

100 → Bucket 4

Storage:

Bucket 4
└── [Alice,20] -> Admin

Lookup Using a New Object

Later:

User lookupUser = new User("Alice", 20);

map.get(lookupUser);

Even though this is a completely different object instance, lookup succeeds.

Step 1: Calculate HashCode

lookupUser.hashCode()

returns:

100

Step 2: Find Bucket

100 → Bucket 4

HashMap jumps directly to Bucket 4.

Step 3: Compare Keys

HashMap executes:

lookupUser.equals(user1)

Result:

true

Match found.

Return:

"Admin"

What Happens If hashCode() Is Wrong?

Suppose:

user1.equals(lookupUser) == true

but:

user1.hashCode() = 100
lookupUser.hashCode() = 500

Now lookup becomes:

lookupUser
     ↓
hashCode() = 500
     ↓
Bucket 12

HashMap searches:

Bucket 12

But the data is stored in:

Bucket 4

HashMap never reaches the correct bucket.

Result:

null

Notice something important:

HashMap never even gets a chance to call equals() on the stored key because it searched the wrong bucket.

This is exactly why the equals/hashCode contract is critical.

Quick Revision

hashCode()
     ↓
Find Bucket
     ↓
equals()
     ↓
Find Exact Key

Remember:

Same hashCode + equals() true → Update existing value

Same hashCode + equals() false → Collision, store new entry

equals() true → hashCode() must be same

hashCode() finds the bucket

equals() identifies the correct key inside that bucket