🟢 Junior Level

HashMap, LinkedHashMap and TreeMap — three main Map implementations.

Main difference:

	HashMap	LinkedHashMap	TreeMap
Order	None	Insertion order	Sorting
Speed	Fast O(1)	Slightly slower O(1) + DLL overhead	Slower O(log n) tree
null key	✅ One	✅ One	❌ Not allowed
Complexity	O(1)	O(1)	O(log n)

// HashMap: no order
Map<String, Integer> hm = new HashMap<>();
hm.put("C", 3); hm.put("A", 1); hm.put("B", 2);
// → {A=1, C=3, B=2} (order not guaranteed)

// LinkedHashMap: insertion order
Map<String, Integer> lh = new LinkedHashMap<>();
lh.put("C", 3); lh.put("A", 1); lh.put("B", 2);
// → {C=3, A=1, B=2} (as inserted)

// TreeMap: sorted by keys
Map<String, Integer> tm = new TreeMap<>();
tm.put("C", 3); tm.put("A", 1); tm.put("B", 2);
// → {A=1, B=2, C=3} (sorted!)

---

🟡 Middle Level

HashMap: speed

// Internally: bucket array + lists/trees
// O(1) for get/put
// → Best default choice

// Treeification (Java 8+):
// > 8 elements in a bucket → tree
// → Protection against bad hashCode()

// Resize: × 2 on fill
// → Expensive operation (copying all elements)

LinkedHashMap: order + LRU

// Internally: HashMap + doubly linked list
// O(1) for get/put
// + insertion order

// LRU cache:
Map<K, V> cache = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX;
    }
};
// accessOrder = true → get() moves to end

TreeMap: sorting

// Internally: red-black tree
// O(log n) for get/put
// → Sorting by keys
// → floorKey, ceilingKey, subMap

// Does not accept null (without custom Comparator)
// compareTo determines uniqueness!

When to use which

Scenario	What to choose
Dictionary, cache	HashMap
Insertion order	LinkedHashMap
LRU cache	LinkedHashMap (accessOrder)
Key sorting	TreeMap
Range queries	TreeMap

Cache Locality

Cache Locality: HashMap — bucket array, elements are close in memory (better cache locality). LinkedHashMap — nodes linked by references, scattered across heap (more cache misses during iteration).

---

🔴 Senior Level

Memory Comparison

HashMap entry: ~32 bytes
LinkedHashMap entry: ~48 bytes (+ before/after)
TreeMap entry: ~40-56 bytes (left/right/parent/color)

→ 1 million entries:
  HashMap: ~36 MB
  LinkedHashMap: ~52 MB
  TreeMap: ~44 MB

Java 21: SequencedMap

// LinkedHashMap and TreeMap → SequencedMap (SequencedMap is Java 21+, not available on older versions.)
map.putFirst("A", 1);    // New method!
map.putLast("Z", 26);    // New method!
map.firstEntry();        // New method!
map.reversed();          // Reverse order (view)

// HashMap is NOT SequencedMap

False Sharing in multithreading

synchronizedMap(new HashMap<>())
  → Competition for cache lines
  → False sharing on multi-core CPUs

ConcurrentHashMap → the solution!

compareTo vs equals

// TreeMap uses compareTo!
// If compareTo = 0 → element already exists
// Even if equals = false!

class Key implements Comparable<Key> {
    String name;
    public int compareTo(Key o) {
        return name.compareTo(o.name);
    }
    public boolean equals(Object o) {
        return false; // Different logic!
    }
}

// → Data loss if not consistent!

Production Experience

Real scenario: LRU cache

// 10,000 elements, frequent reads
// HashMap + manual old element removal → complex

// LinkedHashMap with accessOrder + removeEldestEntry
// → 5 lines of code → ready-made cache!

Best Practices

1. HashMap — default choice if no order or sorting is needed
2. LinkedHashMap — order or LRU
3. TreeMap — sorting/ranges
4. initialCapacity → avoid resize
5. Immutable keys — mandatory
6. Java 21 → SequencedMap API
7. compareTo = equals for TreeMap
8. Memory → HashMap is more compact

Summary for Senior

• HashMap = O(1), no order, treeification
• LinkedHashMap = O(1), order, LRU cache
• TreeMap = O(log n), sorting, navigation
• Memory: HashMap < TreeMap < LinkedHashMap
• SequencedMap (Java 21) → putFirst/reversed
• CPU Cache: HashMap > TreeMap
• compareTo ≠ equals → data loss
• LRU = LinkedHashMap(accessOrder=true)

---

🎯 Interview Cheat Sheet

Must know:

• HashMap = O(1), no order, internally bucket array + lists/trees, treeification at > 8 collisions
• LinkedHashMap = O(1) + doubly linked list for insertion order, supports LRU cache (accessOrder=true)
• TreeMap = O(log n), red-black tree, sorting by keys, navigation (floorKey, ceilingKey, subMap)
• HashMap allows one null key, TreeMap does not (without custom Comparator)
• TreeMap uses compareTo for uniqueness, not equals — inconsistency = data loss
• Memory: HashMap (~32 bytes/entry) < TreeMap (~40-56 bytes) < LinkedHashMap (~48 bytes)
• Java 21: SequencedMap API (putFirst, putLast, reversed) for LinkedHashMap and TreeMap
• LRU cache = LinkedHashMap(16, 0.75f, true) + overridden removeEldestEntry

Frequent follow-up questions:

• How does LRU cache work on LinkedHashMap? — accessOrder=true moves the element to the end on every get(). removeEldestEntry() removes the oldest when the limit is exceeded.
• Why doesn’t TreeMap accept null? — Because it needs to call compareTo for sorting, and null has no compareTo method. Workaround: Comparator.nullsFirst().
• What is treeification in HashMap? — At > 8 elements in one bucket, the linked list turns into a red-black tree — protection against O(n) on collisions.
• When is HashMap better than LinkedHashMap? — Always by default, unless iteration order is needed. LinkedHashMap uses +50% memory for the linked list.

Red flags (DO NOT say):

• ❌ “TreeMap uses equals to check keys” — it uses compareTo!
• ❌ “HashMap preserves insertion order” — no, order is not guaranteed
• ❌ “LinkedHashMap is slower for get/put” — same complexity O(1), only more memory
• ❌ “TreeMap is for insertion order” — LinkedHashMap is for that, TreeMap sorts by keys

Related topics:

• [[14. What is Map and what implementations exist]]
• [[16. When to use TreeMap]]
• [[11. What is the difference between HashSet, LinkedHashSet and TreeSet]]
• [[18. What is ConcurrentHashMap]]