👋 Everyone knows HashMap as “key & value”… but what’s inside?
Honestly, I was also in that majority who just knew:
👉 “HashMap = key & value storage.”
…and never cared how it actually works under the hood.
But recently I got curious and explored it myself, and here’s what I learned 👇 (sharing in case it helps someone else too 💛).
🔧 HashMap, HashSet, HashTable — what do they use internally?
All of them rely on a common concept: Hashing Technique ⚡
…but there’s more happening than I expected!
🏗️ How does Hashing work here?
Think of it as splitting data into an array of buckets:
✅ Each bucket holds entries (key → value).
✅ When you insert, the hash function decides which bucket to drop your data into.
➡️ In Java:
-
Your key’s
hashCode()is used. -
That hash code is transformed into a bucket index.
-
Inside that bucket, Java stores a
Map.Entry(key and value pair).
Why override hashCode()?
✔️ To give a good distribution → fewer collisions → faster lookups.
Why override equals() too?
✔️ To correctly compare keys inside the same bucket.
💡 What algorithm?
I initially guessed B+ Tree (🤔) — but that’s not what HashMap uses.
Here’s what I found out:
✅ HashMap uses a combination of Hash Table + Linked List / Red‑Black Tree (from Java 8 onwards):
Normally, each bucket stores entries in a linked list.
-
If too many collisions occur in one bucket (default threshold = 8 entries), that bucket switches to a balanced Red‑Black Tree for faster lookups.
😯 My sudden doubt…
While digging deeper into HashMap internals, I came across this line:
“If too many collisions occur in one bucket (default threshold = 8 entries), that bucket switches to a balanced Red‑Black Tree for faster lookups.”
👉 Wait… what does that really mean? 🤨
At first, I only knew HashMap stores entries in buckets using hashing.
But this line made me pause and explore further. 🔍
🧭 My exploration & what I found
When two different keys produce the same bucket index (because their hashCode() after processing points to the same slot), they collide and get stored together.
Before digging in, my assumption:
“Hmm, maybe HashMap just keeps chaining them in a list…?”
Then I found out:
✅ Yes! In older Java (before 8), each bucket was a Linked List.
✅ But if many entries land in the same bucket, searching becomes slow because it goes one by one.
👉 O(n) time in worst cases. 😩
🌳 The optimization I discovered
In Java 8 and above, the designers made it smarter:
✅ If a single bucket gets too many entries (more than 8),
✅ HashMap converts that bucket’s linked list into a Red‑Black Tree 🌳.
Why is that cool?
Because searching in a balanced tree is logarithmic (O(log n)),
instead of linear (O(n)).
➡️ Even with many collisions, lookups remain fast! ⚡
✨ How it feels now
It’s like I opened a hidden drawer inside HashMap:
| Condition | Structure | Search Time |
|---|---|---|
| Few collisions (≤8) | Linked List | O(n) for that bucket |
| Too many collisions (>8) | 🌳 Red‑Black Tree | O(log n) for that bucket |
“Wow! HashMap dynamically upgrades its internal structure for performance!” 🤯
So nope, not B+ Tree — it’s Red‑Black Tree in modern Java HashMap.
(TreeMap itself is always a Red‑Black Tree, not hashing.)
🌳 What about others?
✅ HashSet → Internally just a HashMap with dummy values.
✅ HashTable → Older synchronized version of HashMap (still hashing).
✅ LinkedHashMap → Keeps insertion order with a linked list alongside hashing.
✅ TreeMap → Completely different, uses a Red‑Black Tree (no hashing).
✅ ConcurrentHashMap → Advanced locking & segmenting, but still hashing.
🔥 Key Takeaways (My own “aha!” moments):
✅ HashMap isn’t just a simple bucket → it’s smart with hash functions and trees.
✅ Overriding hashCode() and equals() properly is super important.
✅ Different map/set implementations use different internal structures—choose wisely!
Comments
Post a Comment