📦 Section 4 · Question #15

What is the difference between HashMap, LinkedHashMap and TreeMap

While LinkedHashMap incurs a minor overhead during put() to manage linked pointers, iterating through a LinkedHashMap is often significantly faster than iterating through a Hash...

📦 Collections 📄 Source Markdown

🟢 Junior Level

1. Comparative Overview

HashMap, LinkedHashMap, and TreeMap are the three primary implementations of the java.util.Map interface in Java. Their distinctions lie in their underlying data structures, iteration ordering, time complexity, and memory overhead:

Characteristic HashMap LinkedHashMap TreeMap
Encounter Order Non-deterministic / Chaotic Insertion-Order (or Access-Order) Sorted Order (Natural or Comparator)
Underlying Data Structure Hash Table (Buckets + Treeification) Hash Table + Global Doubly-Linked List Self-Balancing Red-Black Search Tree
Lookup / Put Complexity $O(1)$ average $O(1)$ average $O(\log N)$ guaranteed
Iteration Complexity $O(\text{capacity} + N)$ $O(N)$ $O(N)$
null Key Support ✅ Allowed (maximum 1 null key) ✅ Allowed (maximum 1 null key) ❌ Prohibited (NullPointerException)
Interfaces Implemented Map Map, SequencedMap (Java 21+) Map, NavigableMap, SequencedMap
Primary Use Case Default general-purpose map Predictable traversal, LRU cache Range searches, sorted key output

2. Ordering Demonstration

// 1. HashMap: Order is non-deterministic and can shift across JVMs and resizes
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("Zulu", 1); hashMap.put("Alpha", 2); hashMap.put("Mike", 3);
System.out.println(hashMap.keySet()); // e.g. [Alpha, Zulu, Mike] (dictated by bucket indices)

// 2. LinkedHashMap: Strictly preserves insertion sequence
Map<String, Integer> linkedMap = new LinkedHashMap<>();
linkedMap.put("Zulu", 1); linkedMap.put("Alpha", 2); linkedMap.put("Mike", 3);
System.out.println(linkedMap.keySet()); // GUARANTEED: [Zulu, Alpha, Mike]

// 3. TreeMap: Naturally sorted lexicographically
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Zulu", 1); treeMap.put("Alpha", 2); treeMap.put("Mike", 3);
System.out.println(treeMap.keySet()); // GUARANTEED: [Alpha, Mike, Zulu]

🟡 Middle Level

1. Underlying Data Structure Mechanics

HashMap:
  table[] ──► [0] ──► Node(k,v) ──► Node(k,v) (Singly-linked list or TreeNode)
              [1] ──► null
              [2] ──► Node(k,v)

LinkedHashMap:
  table[] ──► [0] ──► Entry(k,v) ──► Entry(k,v)  (Hash table for O(1) key indexing)
                         │   ▲
                         ▼   │ before / after pointers
  head ─────────────► [Entry1] ◄────► [Entry2] ◄────► [Entry3] ◄─── tail (Doubly-linked list)

TreeMap:
              [ Root: Entry(k,v) ]
                 /            \
       [ Left: Entry ]     [ Right: Entry ]  (Red-Black Tree, O(log N))
  • HashMap routes keys via (capacity - 1) & hash(key). Collisions are chained into singly-linked lists that convert to balanced Red-Black Trees (TreeNode) when bucket count reaches $\ge 8$ and capacity $\ge 64$.
  • LinkedHashMap extends HashMap, but overrides node creation to instantiate LinkedHashMap.Entry<K,V>, which adds before and after pointers. Every insertion links the node into a global doubly-linked list spanning the entire map.
  • TreeMap bypasses hashing completely. Nodes maintain left, right, and parent references, self-balancing via rotations and recoloring to satisfy Red-Black invariants.

2. The Iteration Performance Paradox: HashMap vs. LinkedHashMap

While LinkedHashMap incurs a minor overhead during put() to manage linked pointers, iterating through a LinkedHashMap is often significantly faster than iterating through a HashMap:

  • In HashMap, the iterator must linearly inspect every slot in the table[] array of size capacity. In a sparse table (e.g., pre-allocated capacity = 1_000_000 holding only 50 entries), HashMap iterates over all 1,000,000 slots ($O(\text{capacity} + N)$), causing severe CPU cache misses.
  • In LinkedHashMap, the iterator walks directly along the after pointers from head to tail. It executes exactly $N$ iterations ($O(N)$), completely ignoring empty hash buckets.

3. Access-Order Mode and In-Memory LRU Caching

LinkedHashMap provides a constructor with an accessOrder configuration:

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
  • accessOrder = false (default): Entries are traversed in insertion order.
  • accessOrder = true: Entries are traversed in access order (least-recently-accessed to most-recently-accessed). Invoking get(), getOrDefault(), or put() moves the referenced node to the tail of the doubly-linked list.

This enables building a lightweight Least Recently Used (LRU) Cache by overriding removeEldestEntry:

public class SimpleLruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;

    public SimpleLruCache(int maxCapacity) {
        super(maxCapacity, 0.75f, true); // accessOrder = true
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxCapacity; // Evicts the head (oldest accessed entry) when full
    }
}

🔴 Senior Level

1. Memory Footprint Breakdown (Compressed OOPs)

On a 64-bit JVM with Compressed OOPs (-XX:+UseCompressedOops):

  1. HashMap.Node<K,V>:
    • Object Header (12 bytes) + int hash (4 bytes) + 3 references (key, value, next @ 4 bytes each = 12 bytes) + alignment padding (4 bytes) = 32 bytes.
  2. LinkedHashMap.Entry<K,V>:
    • Inherits HashMap.Node (32 bytes) + 2 references (before, after @ 4 bytes each = 8 bytes) = 40 bytes.
  3. TreeMap.Entry<K,V>:
    • Object Header (12 bytes) + 5 references (key, value, left, right, parent @ 4 bytes each = 20 bytes) + boolean color (1 byte) + alignment padding (7 bytes) = 40 bytes.
Metric HashMap LinkedHashMap TreeMap
Node Size (Compressed OOPs) 32 bytes 40 bytes 40 bytes
Bucket Array (table[]) Yes (4 bytes/slot) Yes (4 bytes/slot) None (Root reference only)
CPU Cache Locality Moderate Low (Pointer chasing) Very Low (Heap-scattered tree)
Approximate Memory per $10^6$ Entries $\approx 36\text{ MB}$ $\approx 44\text{ MB}$ $\approx 40\text{ MB}$

2. Java 21 SequencedMap Integration (JEP 431)

Java 21 introduced SequencedMap to unify ordered mapping abstractions:

SequencedMap<String, Integer> seqMap = new LinkedHashMap<>();
seqMap.putFirst("First", 1);
seqMap.putLast("Last", 99);

// Zero-copy live reverse view in O(1):
SequencedMap<String, Integer> reversed = seqMap.reversed();

Critical Divergence Between LinkedHashMap and TreeMap:

  • In LinkedHashMap, putFirst() and putLast() are fully supported, repositioning or inserting entries at the head or tail of the doubly-linked list.
  • In TreeMap, putFirst() and putLast() always throw UnsupportedOperationException, because entry position in a binary search tree is strictly determined by key comparison and cannot be dictated manually.

3. Key Equality Contract Disparity

  • HashMap and LinkedHashMap evaluate key equality strictly through: k1.hashCode() == k2.hashCode() && (k1 == k2 || (k1 != null && k1.equals(k2)))
  • TreeMap never invokes hashCode() or equals(). It relies exclusively on: comparator.compare(k1, k2) == 0 or ((Comparable) k1).compareTo(k2) == 0

If a class’s compareTo() is not consistent with equals() (such as BigDecimal("1.0") and BigDecimal("1.00")):

  • HashMap stores both entries (scale differs, equals() returns false).
  • TreeMap considers them duplicates (compareTo() == 0) and overwrites the value of the first with the second!

4 Tricky Questions

1. Why can invoking get(key) on a LinkedHashMap with accessOrder = true cause an infinite CPU loop or ConcurrentModificationException under concurrency?

Answer: When accessOrder = true, get() is not a read-only operation; it is a structural modification. The invoked method unlinks the accessed Entry from its current position in the doubly-linked list and reattaches it to the tail. This mutation:

  1. Increments modCount, causing concurrent active iterators to fail-fast with ConcurrentModificationException.
  2. Without synchronization, concurrent pointer updates (before and after references) can produce circular pointer loops. A subsequent traversal will enter an infinite loop, consuming 100% of a CPU core.

2. In what scenario does iterating over a LinkedHashMap dramatically outperform iterating over a HashMap with the same size?

Answer: In a sparse map scenario, where initial capacity is significantly larger than the number of stored elements (e.g., new HashMap<>(1_000_000) populated with only 1,000 entries). The HashMap iterator must scan all 1,000,000 slots of the table[] array looking for non-null bucket heads ($O(\text{capacity} + N)$), causing massive L1/L2 CPU cache misses. LinkedHashMap iterates strictly over the continuous doubly-linked list using after references, taking exactly 1,000 steps ($O(N)$) and completely ignoring the empty bucket array.

3. Why does TreeMap reject null keys with NullPointerException, while HashMap permits one null key?

Answer: HashMap includes special handling for null: when key == null, it forces the hash to 0 and stores the entry deterministically in table[0]. In TreeMap, placing an entry requires navigating the Red-Black Tree by comparing the candidate key against existing node keys via comparator.compare(k1, k2) or k1.compareTo(k2). Invoking compareTo() on a null reference or passing null to a standard comparator triggers a NullPointerException. (The only exception is if TreeMap is provided an explicit null-handling comparator like Comparator.nullsFirst(...)).

4. What happens when calling putFirst() or putLast() on a TreeMap in Java 21?

Answer: Both methods throw UnsupportedOperationException. Although TreeMap implements SequencedMap (which declares putFirst and putLast), a sorted map cannot permit caller-defined positional placement. The position of every node in a Red-Black Tree is strictly defined by the ordering invariants of its keys. Allowing putFirst("Z", val) when keys "A" through "Y" exist would corrupt the binary search tree invariants.

🎯 Interview Cheat Sheet

30-Second Elevator Pitch

“HashMap is the standard hash-table map providing average $O(1)$ lookup and insertion with non-deterministic iteration order. LinkedHashMap extends HashMap by maintaining a doubly-linked list across all entries, providing deterministic insertion-order or access-order (for LRU caching) at the cost of 8 additional bytes per entry. TreeMap is backed by a self-balancing Red-Black Tree, offering guaranteed $O(\log N)$ performance and sorted navigation (NavigableMap), but rejects null keys and determines key equality strictly via compareTo() == 0, ignoring equals(). In Java 21, LinkedHashMap and TreeMap implement SequencedMap.”

High-Impact Architectural Facts

  • Memory Footprint: HashMap.Node is 32 bytes; LinkedHashMap.Entry and TreeMap.Entry are both 40 bytes under Compressed OOPs.
  • Iteration Bound: HashMap iteration is $O(\text{capacity} + N)$; LinkedHashMap and TreeMap iteration is strictly $O(N)$.
  • LRU Pitfall: LinkedHashMap with accessOrder = true turns get() into a structural mutation; concurrent unsynchronized reads corrupt pointers and throw ConcurrentModificationException.
  • Equality Law: HashMap and LinkedHashMap require both hashCode() and equals(); TreeMap relies exclusively on Comparable.compareTo() or Comparator.compare().
  • Java 21 JEP 431: LinkedHashMap supports putFirst() / putLast(); TreeMap throws UnsupportedOperationException.

Common Pitfalls & Red Flags

  • ❌ Assuming TreeMap is faster than HashMap: TreeMap operates in $O(\log N)$ and incurs frequent CPU cache misses; HashMap operates in average $O(1)$ and is significantly faster.
  • ❌ Using LinkedHashMap to sort entries by key: LinkedHashMap only maintains insertion or access order; sorting by key requires TreeMap.
  • ❌ Ignoring compareTo() consistency with equals() in TreeMap: If compareTo() returns 0 for logically distinct objects, TreeMap silently overwrites or ignores entries.
  • ❌ Assuming LinkedHashMap(cap, factor, true) is thread-safe for reads: Reads modify the internal linked list; multi-threaded caching requires synchronization or Caffeine.