HashMap vs TreeMap vs LinkedHashMap
Fast recall
Quick revision
Core answer
Understanding of Map implementations, ordering guarantees, and time complexity trade-offs
Assuming HashMap is always the best choice, or not knowing that TreeMap uses a Red-Black tree internally
Mention that LinkedHashMap can be used to implement an LRU cache by overriding removeEldestEntry, and that TreeMap supports NavigableMap operations like floorKey and ceilingKey
Interview-ready guide
Interview answer
HashMap, TreeMap, and LinkedHashMap are Java's three most commonly compared Map implementations — each making different trade-offs between access speed and ordering guarantees.
HashMap:
- O(1) average for put/get — bucket array with hash-based indexing, no ordering guarantee
- The right default for key-value lookup when iteration order doesn't matter
TreeMap:
- Sorted keys via Red-Black tree — O(log n) for all operations
- Real value: NavigableMap operations like
subMap(),headMap(),tailMap(),floorKey(),ceilingKey() - Null keys not allowed — comparing null throws NPE; HashMap puts null at bucket 0
LinkedHashMap:
- HashMap plus a doubly-linked list — preserves insertion order by default
- Set
accessOrder=truein constructor to switch to access-order mode — everyget()moves the entry to the tail - Override
removeEldestEntry()to evict when size exceeds a limit — instant LRU cache in a few lines
I recommend HashMap as the default, TreeMap when you need sorted iteration or range queries, and LinkedHashMap when insertion order or LRU eviction matters.
HashMap vs TreeMap vs LinkedHashMap
Direct Answer
HashMap offers O(1) average operations with no ordering. TreeMap provides O(log n) operations with natural/custom sorted order. LinkedHashMap gives O(1) average with insertion or access order maintained — ideal for LRU caches.
Common Mistakes & Pitfalls
Assuming HashMap is always the best choice, or not knowing that TreeMap uses a Red-Black tree internally
Check your understanding
Answer these without looking back at the article.
- How does HashMap handle hash collisions internally?
- How would you implement an LRU cache using LinkedHashMap?
- What happens if two keys have the same hashCode in a HashMap?
Related interview prep categories
1Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.