Lesson 25 • Advanced
Advanced Maps: HashMap, TreeMap & LinkedHashMap
Choose the right Map type and understand hashing, ordering, and complexity.
Before You Start
You should understand Collections Internals (Lesson 24), hashCode/equals, and Generics (Lesson 14). This lesson builds on HashMap internals to cover TreeMap, LinkedHashMap, and modern Map methods.
What You'll Learn
- ✅ HashMap vs TreeMap vs LinkedHashMap
- ✅ Custom hashCode() and equals() contracts
- ✅ ConcurrentHashMap for thread safety
- ✅ Map.compute(), merge(), and getOrDefault()
- ✅ Real-world use cases for each Map type
1️⃣ Choosing the Right Map
Java provides multiple Map implementations, each optimized for different access patterns. Choosing the wrong one is a common performance mistake in code reviews.
💡 Decision Guide
HashMap: Your default choice. O(1) get/put, no ordering. TreeMap: Sorted by key (natural ordering or Comparator). O(log n) operations. Use for range queries. LinkedHashMap: Maintains insertion order (or access order for LRU caches). Slightly slower than HashMap.
Try It: HashMap vs TreeMap vs LinkedHashMap
// Comparing Map Implementations
console.log("=== Map Implementations ===\n");
// 1. HashMap — unordered, O(1)
console.log("1. HASHMAP (unordered, fastest):");
let hashMap = new Map();
hashMap.set("banana", 3);
hashMap.set("apple", 5);
hashMap.set("cherry", 1);
hashMap.set("date", 7);
hashMap.set("elderberry", 2);
console.log(" Entries (no guaranteed order):");
hashMap.forEach((v, k) => console.log(" " + k + ": " + v));
// 2. TreeMap — sorted by key
console.log("\n2. TREEMAP (sorted by key
...2️⃣ The hashCode/equals Contract
If you use custom objects as Map keys, you must override both hashCode() and equals(). The contract: if a.equals(b), then a.hashCode() == b.hashCode(). Breaking this contract means HashMap can't find your keys. Use Objects.hash(field1, field2) for easy, correct implementations.
3️⃣ ConcurrentHashMap
Never use Collections.synchronizedMap() in production — it locks the entire map for every operation. ConcurrentHashMap uses CAS operations (Java 8+), allowing multiple threads to read/write simultaneously. It's the only thread-safe Map you should use.
Try It: Modern Map Methods
// Modern Map Methods — compute, merge, getOrDefault
console.log("=== Modern Map Methods ===\n");
// 1. getOrDefault
console.log("1. GET OR DEFAULT:");
let config = new Map([["timeout", "30"], ["host", "localhost"]]);
console.log(" timeout:", config.get("timeout") || "60");
console.log(" port:", config.get("port") || "8080");
console.log(" (getOrDefault avoids null checks)");
// 2. putIfAbsent
console.log("\n2. PUT IF ABSENT:");
let cache = new Map();
cache.set("user:1", "Alice");
let exist
...4️⃣ LRU Cache with LinkedHashMap
One of the most common interview questions! LinkedHashMap with accessOrder=true moves recently accessed entries to the end. Override removeEldestEntry() to automatically evict the oldest entry when the cache exceeds a size limit — a complete LRU cache in 5 lines of code.
Try It: LRU Cache Implementation
// LRU Cache with LinkedHashMap
console.log("=== LRU Cache ===\n");
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) return null;
// Move to end (most recently used)
let value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
put(key, value) {
if (this.cache.has(key)) this.cache.delet
...Common Mistakes
Pro Tips
💡 LRU Cache with LinkedHashMap: Pass accessOrder=true and override removeEldestEntry(). Instant LRU cache in 5 lines.
💡 Map.merge() is incredibly powerful: map.merge("count", 1, Integer::sum) increments a counter, inserting 1 if missing.
💡 Map.of() (Java 9+) creates small immutable maps: Map.of("key1", "val1", "key2", "val2").
📋 Quick Reference
| Method | Purpose | Example |
|---|---|---|
| getOrDefault(k, v) | Get or return default | map.getOrDefault("x", 0) |
| putIfAbsent(k, v) | Put only if missing | map.putIfAbsent("x", 1) |
| compute(k, fn) | Compute new value | map.compute("x", (k,v) → v+1) |
| merge(k, v, fn) | Merge with existing | map.merge("x", 1, Integer::sum) |
🎉 Lesson Complete!
You now know when to use HashMap, TreeMap, and LinkedHashMap — plus how to build an LRU Cache!
Next: Multithreading — create and manage threads, use thread pools and ExecutorService.
Sign up for free to track which lessons you've completed and get learning reminders.