Definition
- HashMap: hash table, no ordering, O(1) average get/put, allows one null key
- LinkedHashMap: extends HashMap with a doubly-linked list of entries; maintains insertion order (default) or access order (LRU mode); O(1) with slight memory overhead
- TreeMap: Red-Black tree, sorted by key (natural order or Comparator), O(log n) get/put, NavigableMap interface, no null keys
- Choose based on ordering needs: no order → HashMap, insertion order → LinkedHashMap, sorted → TreeMap
HashMap is a filing cabinet with drawers placed wherever there is space – fastest filing and retrieval, but drawers are in no particular order. LinkedHashMap is the same cabinet but with drawers chained in the order you added them – you can walk through in filing order. TreeMap is a cabinet where drawers are always alphabetically sorted – adding takes longer because you must find the right position, but you can always read A to Z.
Understanding the Concepts
What is the difference between HashMap, LinkedHashMap, and TreeMap?
All three implement the Map interface but differ in ordering, performance, and internal structure.
| Feature | HashMap | LinkedHashMap | TreeMap |
|---|---|---|---|
| Internal structure | Hash table | Hash table + linked list | Red-Black tree |
| Ordering | None | Insertion or access order | Sorted (natural/Comparator) |
| get/put | O(1) | O(1) | O(log n) |
| Null key | 1 allowed | 1 allowed | Not allowed |
| Null values | Yes | Yes | Yes |
| NavigableMap | No | No | Yes |
| Memory | Lowest | Medium (+pointers) | Highest (+tree nodes) |
| Thread-safe | No | No | No |
package com.bank.demo;
import java.math.BigDecimal;
import java.util.*;
public class MapComparisonDemo {
public static void main(String[] args) {
Map<String, BigDecimal> hashMap = new HashMap<>();
Map<String, BigDecimal> linkedMap = new LinkedHashMap<>();
Map<String, BigDecimal> treeMap = new TreeMap<>();
// Insert in this order: CUR, SAV, FD
for (var m : List.of(hashMap, linkedMap, treeMap)) {
m.put("CUR3001", new BigDecimal("75000"));
m.put("SAV2001", new BigDecimal("150000"));
m.put("FD4001", new BigDecimal("500000"));
}
System.out.println("HashMap: " + hashMap.keySet());
System.out.println("LinkedHashMap: " + linkedMap.keySet());
System.out.println("TreeMap: " + treeMap.keySet());
}
}
HashMap: [FD4001, CUR3001, SAV2001]
LinkedHashMap: [CUR3001, SAV2001, FD4001]
TreeMap: [CUR3001, FD4001, SAV2001]
How do you build an LRU cache with LinkedHashMap?
LinkedHashMap supports access-order mode: when you call get() or put() on an existing key, the entry moves to the end of the linked list. Combined with removeEldestEntry(), this creates an LRU (Least Recently Used) cache.
package com.bank.service;
import java.math.BigDecimal;
import java.util.*;
public class LRUCacheDemo {
public static void main(String[] args) {
// LRU cache: max 3 entries, access-order
Map<String, BigDecimal> cache = new LinkedHashMap<>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, BigDecimal> eldest) {
return size() > 3; // evict when more than 3 entries
}
};
cache.put("SAV2001", new BigDecimal("150000"));
cache.put("CUR3001", new BigDecimal("75000"));
cache.put("FD4001", new BigDecimal("500000"));
System.out.println("Initial: " + cache.keySet());
// [SAV2001, CUR3001, FD4001]
// Access SAV2001 → moves to end
cache.get("SAV2001");
System.out.println("After get(SAV): " + cache.keySet());
// [CUR3001, FD4001, SAV2001]
// Add new entry → evicts CUR3001 (eldest/least recently used)
cache.put("LON5001", new BigDecimal("200000"));
System.out.println("After put(LON): " + cache.keySet());
// [FD4001, SAV2001, LON5001]
}
}
Initial: [SAV2001, CUR3001, FD4001]
After get(SAV): [CUR3001, FD4001, SAV2001]
After put(LON): [FD4001, SAV2001, LON5001]
What are TreeMap's NavigableMap operations?
TreeMap implements NavigableMap, providing powerful range query methods:
package com.bank.service;
import java.math.BigDecimal;
import java.util.*;
public class NavigableMapDemo {
public static void main(String[] args) {
TreeMap<String, BigDecimal> accounts = new TreeMap<>();
accounts.put("CUR3001", new BigDecimal("75000"));
accounts.put("FD4001", new BigDecimal("500000"));
accounts.put("LON5001", new BigDecimal("200000"));
accounts.put("SAV2001", new BigDecimal("150000"));
accounts.put("SAV2002", new BigDecimal("80000"));
System.out.println("First: " + accounts.firstKey()); // CUR3001
System.out.println("Last: " + accounts.lastKey()); // SAV2002
System.out.println("Floor(G): " + accounts.floorKey("G")); // FD4001 (<=G)
System.out.println("Ceiling(G): " + accounts.ceilingKey("G")); // LON5001 (>=G)
// Range queries
System.out.println("Sub [CUR..SAV): " + accounts.subMap("CUR3001", "SAV2001"));
System.out.println("Head (<LON): " + accounts.headMap("LON5001"));
System.out.println("Tail (>=LON): " + accounts.tailMap("LON5001"));
// Descending order
System.out.println("Descending: " + accounts.descendingMap().keySet());
}
}
First: CUR3001
Last: SAV2002
Floor(G): FD4001
Ceiling(G): LON5001
Sub [CUR..SAV): {CUR3001=75000, FD4001=500000, LON5001=200000}
Head (<LON): {CUR3001=75000, FD4001=500000}
Tail (>=LON): {LON5001=200000, SAV2001=150000, SAV2002=80000}
Descending: [SAV2002, SAV2001, LON5001, FD4001, CUR3001]
When do you use each?
| Use case | Best choice | Why |
|---|---|---|
| Fast key-value lookup, order irrelevant | HashMap | O(1), lowest memory |
| Preserve insertion order | LinkedHashMap | O(1), deterministic iteration |
| LRU cache | LinkedHashMap (access-order) | O(1) with automatic eviction |
| Sorted keys | TreeMap | O(log n), NavigableMap |
| Range queries ("accounts between A and F") | TreeMap | subMap, headMap, tailMap |
| JSON serialization with consistent order | LinkedHashMap | Insertion order = field order |
| Thread-safe map | ConcurrentHashMap | Per-bucket locking |
| Thread-safe sorted map | ConcurrentSkipListMap | Lock-free, sorted |
What are common mistakes?
Mistake 1: Using HashMap when output order matters
// WRONG: JSON output order is unpredictable
Map<String, String> response = new HashMap<>();
response.put("status", "OK");
response.put("account", "SAV2001");
// Serialized: {"account":"SAV2001","status":"OK"} – random order!
// CORRECT: use LinkedHashMap for predictable field order
Map<String, String> response = new LinkedHashMap<>();
response.put("status", "OK");
response.put("account", "SAV2001");
// Serialized: {"status":"OK","account":"SAV2001"} – insertion order!
Mistake 2: Using TreeMap when you only need sorted output once
// SUBOPTIMAL: TreeMap for one-time sort (O(n log n) on every put)
TreeMap<String, String> sorted = new TreeMap<>(dataMap);
// BETTER: HashMap for storage, sort once when needed
Map<String, String> fast = new HashMap<>(dataMap);
List<String> sortedKeys = new ArrayList<>(fast.keySet());
Collections.sort(sortedKeys); // one-time O(n log n)
What should a senior engineer know?
- LinkedHashMap.removeEldestEntry is called on every put. If it returns true, the eldest entry is removed. This is the hook for building caches with bounded size.
- TreeMap.subMap, headMap, tailMap return views. Modifications to the view affect the original TreeMap. Use new TreeMap<>(map.subMap(from, to)) for an independent copy.
- ConcurrentSkipListMap. The thread-safe sorted map equivalent of TreeMap. It uses a skip list instead of a Red-Black tree and supports NavigableMap.
- EnumMap. When keys are enum constants, use EnumMap instead of HashMap. It uses an array indexed by enum ordinal – faster and more memory-efficient than any hash-based map.
What are common interview follow-up questions?
- "How do you implement an LRU cache?" – LinkedHashMap with accessOrder=true + removeEldestEntry.
- "What is the time complexity of TreeMap operations?" – O(log n) for get/put/remove.
- "Can TreeMap have null keys?" – No, compareTo/Comparator cannot handle null.
- "What is NavigableMap?" – Extended SortedMap with floor/ceiling/lower/higher and range operations.
Visual Overview
Map implementations
HashMap (hash table):
┌─────────────────────────────────┐
│ {FD4001, CUR3001, SAV2001} │ ← no ordering
│ O(1) get/put │
└─────────────────────────────────┘
LinkedHashMap (hash table + linked list):
┌─────────────────────────────────┐
│ CUR3001 ↔ SAV2001 ↔ FD4001 │ ← insertion order
│ O(1) get/put │
│ access-order mode → LRU cache │
└─────────────────────────────────┘
TreeMap (Red-Black tree):
┌─────────────────────────────────┐
│ FD4001 │
│ / \ │
│ CUR3001 SAV2001 │ ← sorted
│ O(log n) get/put │
│ NavigableMap: floor/ceiling/sub │
└─────────────────────────────────┘
Key Takeaway
HashMap, LinkedHashMap, and TreeMap serve different ordering needs. HashMap is the fastest with no ordering. LinkedHashMap preserves insertion order with the same O(1) performance, and its access-order mode enables a clean O(1) LRU cache implementation. TreeMap sorts keys using a Red-Black tree and provides NavigableMap range queries at the cost of O(log n) operations.
In the National Bank of India system, Rajesh uses HashMap for the real-time balance cache because lookup speed is all that matters. He uses LinkedHashMap with access-order for the session cache, where the least recently used session is evicted when the cache reaches 10,000 entries. For the branch account report sorted by account ID, he uses TreeMap with range queries: accounts.subMap("SAV", "SAW") returns all savings accounts.
Remember one sentence: HashMap for speed, LinkedHashMap for insertion order and LRU caching, TreeMap for sorted keys and range queries.
---