MediumExperience level: 3-5 years · 8-15 years1 min read

Walk me through what happens inside HashMap.put() in Java 8.

Reviewed by Gurusankar M.

Asked inAmazonMicrosoftDeloitte
#hashmap#internals#treeify#hashing#buckets
Report issue

Short Answer

put() hashes the key (with a spread to mix high bits), finds the bucket via (n-1)&hash, then appends/updates in that bucket. Buckets are linked lists that convert to red-black trees once they exceed 8 entries (and the table ≥ 64), giving O(log n) worst case instead of O(n).

On this page

Concept Made Simple

Coffee Chat Question

“Walk me through what happens inside HashMap.put() in Java 8.”

Remember It Faster

Mind Map Answer

Java 8 HashMap = array of buckets. Each bucket is a linked list that treeifies to a balanced tree under heavy collision, so a hot bucket degrades to O(log n), not O(n).

hash(key)
h ^ (h >>> 16) — spreads high bits
bucket
(n - 1) & hash
Treeify
bucket > 8 entries & table ≥ 64
Untreeify
shrinks back below 6

Think Beyond the Expected

What If?

Why does HashMap mix the high bits of the hash before indexing?

The bucket index is (n-1) & hash, which only uses the low bits. Many hashCodes differ mainly in high bits, so without spreading (h ^ (h>>>16)) they'd collide in the same bucket. Mixing reduces collisions cheaply.

Real World

Understanding treeify explains why a HashMap keyed by objects with a poor hashCode (all colliding) is 'slow' — pre-Java 8 it was O(n) per bucket; Java 8 caps it at O(log n) via trees.

Interviewer's Expectation

Keywords they're listening for:

  • spread function
  • (n-1)&hash indexing
  • treeify threshold 8 / table 64
  • O(log n) worst case
  • needs equals + hashCode

Common Mistakes

  • Thinking collisions are always O(n) in Java 8
  • Using mutable objects as keys
  • Ignoring the equals/hashCode contract

Best Practices

  • Use immutable keys with well-distributed hashCode
  • Pre-size the map when the count is known
  • Prefer records/value objects as keys

Follow-up Questions

  1. What triggers a resize and how does it rehash?
  2. Why must keys be effectively immutable?
  3. Why is the default capacity 16 and load factor 0.75?

Continue Learning with AI

Take this question deeper with your favourite AI assistant. Pick a depth, copy the prompt, or open it directly — AI is your learning companion, not a shortcut.

Plain-language foundations

I'm preparing for a software engineering interview and want to understand this from scratch, as a beginner.

Topic: HashMap Internals (Java Collections)
Interview question: "Walk me through what happens inside HashMap.put() in Java 8."

Please:
1. Explain the core idea in simple, plain language, using an everyday analogy.
2. Define any technical terms you use.
3. Walk through one small, concrete example.
4. Finish with a single sentence I can easily remember.

Keep the tone friendly and assume I'm new to this topic.
Open inChatGPTGeminiClaude

Was this answer helpful?

Affiliate links

Tools for Your Developer Workspace

Equipment for a comfortable, productive setup.

As an Amazon Associate I earn from qualifying purchases.