Java provides several Map implementations, but three of the most commonly used are HashMap, LinkedHashMap, and TreeMap.
At first glance, all three store data as key-value pairs. However, their internal implementations, ordering guarantees, performance characteristics, and real-world applications are significantly different.
As a Java developer working on enterprise applications, understanding these differences is important—not just for writing code, but also for making the right architectural decisions.
Consider a banking application:
- Customer account details need fast lookups.
- Recent transactions should maintain insertion order.
- Transaction records may need to be sorted by transaction date.
Would you use the same Map implementation for all three scenarios?
Probably not.
Let's understand how these Map implementations work internally and when to use each one.
1. Understanding the Map Interface
The Map interface stores data in key-value pairs.
Each key must be unique, while multiple keys can have the same value.
Map<Integer, String> customers = new HashMap<>(); customers.put(101, "John"); customers.put(102, "David"); customers.put(103, "Michael"); System.out.println(customers.get(102)); Output:
David Java provides multiple implementations of the Map interface, including:
- HashMap
- LinkedHashMap
- TreeMap
- Hashtable
- ConcurrentHashMap
In this article, we will focus on HashMap, LinkedHashMap, and TreeMap.
2. HashMap: Fast Key-Value Lookups
HashMap is one of the most widely used Map implementations in Java.
It provides average constant-time complexity for basic operations such as:
- put()
- get()
- remove()
- containsKey()
Internal Architecture
HashMap internally uses an array of buckets.
Each bucket can contain:
- A linked list of nodes.
- A balanced Red-Black Tree when collision handling reaches the treeification threshold and other conditions are satisfied.
Each node stores:
static class Node<K,V> { final int hash; final K key; V value; Node<K,V> next; } How does HashMap store an entry?
- The key's
hashCode()is calculated. - HashMap spreads the hash bits.
- The bucket index is calculated.
- The entry is stored in the corresponding bucket.
- If another key maps to the same bucket, collision handling takes place.
The simplified bucket-index calculation is:
index = (capacity - 1) & hash; Java uses a power-of-two table capacity to make this calculation efficient.
Hash Collision Handling
A collision occurs when multiple keys map to the same bucket.
Example:
Map<Integer, String> map = new HashMap<>(); map.put(1, "Customer A"); map.put(17, "Customer B"); map.put(33, "Customer C"); Assuming a table capacity of 16, these integer keys map to the same bucket under the simplified index calculation.
HashMap handles collisions using linked nodes.
When collisions become sufficiently high, the bucket may be converted into a Red-Black Tree.
Important Java 21 implementation details:
- Default initial capacity: 16.
- Default load factor: 0.75.
- Treeification threshold: 8.
- Minimum capacity for treeification: 64.
- Untreeification threshold: 6.
These are implementation details, not guarantees of the Map interface.
HashMap Performance
| Operation | Average | Worst case |
|---|---|---|
| get() | O(1) | O(n) |
| put() | O(1) | O(n) |
| remove() | O(1) | O(n) |
With effective hashing and treeified collision buckets, collision-heavy lookups can achieve O(log n) behavior within those buckets.
Real-World Use Cases
HashMap is suitable for:
- Customer ID to customer details mapping.
- Product ID to product information.
- API response caching.
- Configuration properties.
- Frequently accessed reference data.
Example:
Map<String, Customer> customerCache = new HashMap<>(); customerCache.put("CUST101", customer); Customer result = customerCache.get("CUST101"); When should you use HashMap?
When fast key-based lookup is your primary requirement and you do not need ordering.
3. LinkedHashMap: Maintaining Insertion Order
LinkedHashMap extends HashMap and maintains a doubly linked list across its entries.
Unlike HashMap, it provides predictable iteration order.
By default, that order is insertion order.
Internal Architecture
LinkedHashMap maintains:
- Hash table for fast key lookup.
- Doubly linked list for maintaining entry order.
Each entry maintains additional references:
before after These references connect entries in insertion order.
Example
Map<Integer, String> map = new LinkedHashMap<>(); map.put(103, "Michael"); map.put(101, "John"); map.put(102, "David"); map.forEach((key, value) -> System.out.println(key + " : " + value) ); Output:
103 : Michael 101 : John 102 : David Notice that entries are returned in insertion order.
Access-Order LinkedHashMap
One interesting feature of LinkedHashMap is that it supports access-order iteration.
LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true); map.put(101, "John"); map.put(102, "David"); map.put(103, "Michael"); map.get(101); map.forEach((key, value) -> System.out.println(key + " : " + value) ); Output:
102 : David 103 : Michael 101 : John The accessed entry moves to the end of the iteration order.
This feature is particularly useful when implementing an LRU (Least Recently Used) cache.
Implementing an LRU Cache
class LRUCache<K, V> extends LinkedHashMap<K, V> { private final int capacity; public LRUCache(int capacity) { super(16, 0.75f, true); this.capacity = capacity; } @Override protected boolean removeEldestEntry( Map.Entry<K, V> eldest) { return size() > capacity; } } Usage:
LRUCache<Integer, String> cache = new LRUCache<>(3); cache.put(1, "Customer A"); cache.put(2, "Customer B"); cache.put(3, "Customer C"); cache.get(1); cache.put(4, "Customer D"); System.out.println(cache); Entry 2 is removed because it is the least recently accessed entry.
Note: This example is not thread-safe. Production cache implementations need appropriate concurrency controls or a dedicated caching solution.
LinkedHashMap Performance
| Operation | Average |
|---|---|
| get() | O(1) |
| put() | O(1) |
| remove() | O(1) |
| Iteration | O(n) |
It has additional memory overhead because every entry maintains linked-list references.
Real-World Use Cases
- LRU cache implementation.
- Maintaining API response insertion order.
- Ordered transaction processing.
- Maintaining predictable configuration output.
- Recently accessed customer or product records.
When should you use LinkedHashMap?
When you need HashMap-like lookup performance along with predictable iteration order.
4. TreeMap: Maintaining Sorted Order
TreeMap is different from HashMap and LinkedHashMap.
It internally uses a Red-Black Tree, which is a self-balancing binary search tree.
Unlike the previous implementations, TreeMap maintains its keys in sorted order.
By default, keys are sorted using their natural ordering. You can also provide a custom Comparator.
Internal Architecture
A Red-Black Tree maintains balance through:
- Node coloring.
- Left and right rotations.
- Recoloring during insertion and deletion.
These mechanisms prevent the tree from becoming excessively unbalanced.
Example
Map<Integer, String> map = new TreeMap<>(); map.put(103, "Michael"); map.put(101, "John"); map.put(102, "David"); map.forEach((key, value) -> System.out.println(key + " : " + value) ); Output:
101 : John 102 : David 103 : Michael Even though entries were inserted in a different order, TreeMap maintains sorted key order.
Custom Sorting with Comparator
Suppose a banking application needs to sort transactions based on transaction amount.
Map<Double, String> transactions = new TreeMap<>(Comparator.reverseOrder()); transactions.put(5000.0, "Payment A"); transactions.put(1500.0, "Payment B"); transactions.put(9000.0, "Payment C"); System.out.println(transactions); Output:
{9000.0=Payment C, 5000.0=Payment A, 1500.0=Payment B} Important: TreeMap uses key comparison to determine key uniqueness. Two keys for which the comparator returns zero are treated as the same key.
For real financial applications, avoid using floating-point values as monetary keys. Prefer BigDecimal with a carefully defined comparator, or use a unique transaction ID as the key and sort transaction objects separately.
NavigableMap Features
TreeMap implements NavigableMap, providing useful methods:
TreeMap<Integer, String> map = new TreeMap<>(); map.put(100, "A"); map.put(200, "B"); map.put(300, "C"); map.put(400, "D"); System.out.println(map.firstKey()); System.out.println(map.lastKey()); System.out.println(map.lowerKey(300)); System.out.println(map.higherKey(300)); System.out.println(map.floorKey(250)); System.out.println(map.ceilingKey(250)); Output:
100 400 200 400 200 300 These methods are especially useful for range-based queries.
TreeMap Performance
| Operation | Complexity |
|---|---|
| get() | O(log n) |
| put() | O(log n) |
| remove() | O(log n) |
| firstKey() | O(log n) |
| lastKey() | O(log n) |
Real-World Use Cases
- Maintaining transactions by timestamp.
- Sorting customer records by account number.
- Price-based product ordering.
- Range-based searches.
- Scheduling events by execution time.
- Finding the nearest available time slot.
When should you use TreeMap?
When sorted keys, range queries, or navigation operations are important.
5. HashMap vs LinkedHashMap vs TreeMap
Let's compare all three implementations.
| Feature | HashMap | LinkedHashMap | TreeMap |
|---|---|---|---|
| Internal structure | Hash table | Hash table + doubly linked list | Red-Black Tree |
| Ordering | No guarantee | Insertion/access order | Sorted key order |
| get() | O(1) average | O(1) average | O(log n) |
| put() | O(1) average | O(1) average | O(log n) |
| remove() | O(1) average | O(1) average | O(log n) |
| Null key | One allowed | One allowed | Generally not allowed with natural ordering |
| Null values | Allowed | Allowed | Allowed |
| Memory overhead | Lower | Higher | Higher |
| Thread-safe | No | No | No |
Remember: HashMap and LinkedHashMap do not guarantee constant-time operations in every situation. Their performance depends on hash distribution and resizing behavior.
6. Real-World Banking Application: Choosing the Right Map
Let's consider a fintech platform with three requirements.
Scenario 1: Customer Lookup
Requirement:
Retrieve customer information quickly using customer ID.
Recommended implementation: HashMap.
Map<String, Customer> customerMap = new HashMap<>(); customerMap.put("C101", customer); Customer customer = customerMap.get("C101"); Reason: Fast key-based lookups without ordering requirements.
Scenario 2: Recently Accessed Accounts
Requirement:
Maintain recently accessed customer accounts in access order and remove older entries when the cache reaches its capacity.
Recommended implementation: LinkedHashMap.
Reason: Access-order iteration and eldest-entry removal support LRU cache implementation.
Scenario 3: Transactions Sorted by Timestamp
Requirement:
Maintain transaction records in timestamp order and retrieve transactions within a date range.
Recommended implementation: TreeMap.
NavigableMap<LocalDateTime, Transaction> transactions = new TreeMap<>(); transactions.put( LocalDateTime.now(), transaction ); Range query:
NavigableMap<LocalDateTime, Transaction> dailyTransactions = transactions.subMap( startTime, true, endTime, true ); Reason: Sorted keys and efficient range navigation.
Production consideration: If multiple transactions can share the same timestamp, a TreeMap keyed only by timestamp will overwrite earlier entries. Use a composite key or another collection strategy to preserve every transaction.
7. Important Internal Concepts Every Java Developer Should Know
Understanding these concepts helps explain the performance differences during technical interviews.
A. Hashing and hashCode()
HashMap uses hashCode() to identify the bucket where an entry should be stored.
The equals() method determines whether two keys are logically equal.
The contract is important:
- If two objects are equal according to equals(), they must have the same hashCode().
- Different objects may have the same hashCode().
- hashCode() does not guarantee uniqueness.
B. Resizing and Load Factor
HashMap and LinkedHashMap resize when the number of entries exceeds their threshold.
Default configuration:
capacity = 16; loadFactor = 0.75; threshold = capacity * loadFactor; Therefore:
16 * 0.75 = 12 When the threshold is exceeded, the table is resized, generally doubling its capacity.
Resizing involves redistributing entries into the new table.
C. Why TreeMap Does Not Need Hashing
TreeMap does not use hashCode().
It relies on key comparison using:
- Comparable
- Comparator
This is why TreeMap can maintain sorted key order without calculating hash buckets.
D. Thread Safety
None of these three Map implementations is inherently thread-safe.
For concurrent applications, consider:
Map<String, Customer> customerMap = new ConcurrentHashMap<>(); ConcurrentHashMap supports concurrent access and updates.
For a synchronized wrapper:
Map<String, Customer> synchronizedMap = Collections.synchronizedMap(new HashMap<>()); Remember that compound operations and iteration still require appropriate synchronization.
8. Common Interview Questions
Q1. Why is HashMap faster than TreeMap?
HashMap provides average O(1) lookup using hashing, whereas TreeMap uses a Red-Black Tree and provides O(log n) lookup.
Q2. Does LinkedHashMap maintain insertion order?
Yes. By default, it maintains insertion order. It can also maintain access order using its constructor parameter.
Q3. How does HashMap handle collisions?
It uses linked nodes within buckets and can convert heavily populated buckets into Red-Black Trees when the required conditions are met.
Q4. Can TreeMap contain null keys?
With natural ordering, null keys are not supported. A custom comparator may support null if it explicitly handles them.
Q5. Why is TreeMap useful for range queries?
It implements NavigableMap, which provides methods such as subMap(), headMap(), tailMap(), floorKey(), and ceilingKey().
Q6. Is LinkedHashMap suitable for implementing an LRU cache?
Yes. Its access-order mode and removeEldestEntry() method make it a convenient starting point for a simple LRU cache.
Q7. What happens when two HashMap keys have the same hashCode()?
They are placed in the same bucket. HashMap uses equals() to distinguish them.
9. Final Thoughts
Choosing a Map implementation is not just about knowing Java Collections. It is about understanding application requirements and making the right engineering trade-offs.
My recommendation:
- Use HashMap when fast key-based lookups are the priority.
- Use LinkedHashMap when predictable iteration order or simple LRU behavior is required.
- Use TreeMap when sorted keys and range-based operations are important.
- Use ConcurrentHashMap when concurrent access is required.
In enterprise applications, selecting the correct collection can improve performance, simplify implementation, and make the code easier to maintain.
A good Java developer knows how to use collections. A strong engineer knows why a particular collection is the right choice for a particular problem.
Conclusion
Java Collections are fundamental to building scalable backend applications.
Understanding their internal data structures, complexity, memory overhead, and operational trade-offs helps developers write better production code.
Keep exploring. Keep building. Keep architecting.
Ram The Architect (RTA)
Follow me for more practical insights on Java 21 | Spring Boot | Microservices | Apache Kafka | AWS | System Design | GenAI
Github: https://github.com/Ramu-fsd/
Linkedin: https://www.linkedin.com/in/ramuboya/
References
- Java 21 HashMap Documentation: https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/HashMap.html
- Java 21 LinkedHashMap Documentation: https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/LinkedHashMap.html
- Java 21 TreeMap Documentation: https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/TreeMap.html
- Java Collections Framework: https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/package-summary.html




