LinkedHashMap in Java

LinkedHashMap in Java: A Deep Dive

The LinkedHashMap is a highly versatile class in the Java Collections Framework (java.util.LinkedHashMap). It provides the perfect middle ground between the blazing-fast lookup of a HashMap and the predictable ordering of a LinkedList.

The Core Idea:
HashMap → Stores data using hashing.
LinkedHashMap → Stores data using hashing + remembers insertion order.

LinkedHashMap<Integer, String> map = new LinkedHashMap<>();

map.put(3, "C");
map.put(1, "A");
map.put(2, "B");

System.out.println(map);
// Output: {3=C, 1=A, 2=B} (Exact order is preserved!)

1. Internal Architecture & Node Structure

Under the hood, a LinkedHashMap maintains a Hash Table (an array of buckets) mapped perfectly over a Doubly Linked List. Because it inherits directly from HashMap, it uses the exact same hashing math, but it wraps its nodes with extra pointers.

The Custom Node Structure

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before;
    Entry<K,V> after;
}

Every single entry stored in the map tracks its chronological predecessor (before) and successor (after), weaving a contiguous chain through the scattered memory buckets.

[ Bucket Array ] [ Doubly Linked List ] -------------- ---------------------- 0 1 → Node(A) Node(C) ⇄ Node(A) ⇄ Node(B) 2 → Node(B) (Inserted First) (Inserted Last) 3 → Node(C) 4 --------------

---

2. Backend Working: Step-by-Step

Let's trace what happens internally when you execute: map.put(10, "A");

• STEP 1 — Hash Calculation: Java calculates hash(10).
• STEP 2 — Bucket Index: It computes the bucket location using hash & (array.length - 1). Let's assume this maps to bucket 2.
• STEP 3 — Store Node: The Node[10, A] is physically stored inside bucket 2, handling any collisions just like a standard HashMap.
• STEP 4 — Linked List Connection: Because it must maintain order, Java updates the internal head and tail pointers of the doubly linked list. The new node is appended to the tail.

Why is Iteration Faster than HashMap?

In a standard HashMap, iterating requires the JVM to scan the entire bucket array. If you have an array capacity of 64 but only 3 elements, Java still checks 64 empty buckets.

In a LinkedHashMap, iteration completely ignores the bucket array. It simply starts at the head pointer of the linked list and follows the after pointers: 10 ⇄ 20 ⇄ 30. This zero-waste iteration often makes it practically faster for traversals.

---

3. The Secret Weapon: Access Order Mode

By default, LinkedHashMap maintains insertion order. However, by passing a third boolean parameter into its constructor, you activate Access Order Mode.

// capacity: 16, loadFactor: 0.75, accessOrder: true
LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);

map.put(1, "A");
map.put(2, "B");
map.put(3, "C");

map.get(1); // We access element 1

System.out.println(map);
// Output: {2=B, 3=C, 1=A}

Notice how 1=A jumped to the end! When a get() occurs, Java physically unlinks the node from its current position in the list and moves it to the tail. This is the exact underlying mechanic required for an LRU (Least Recently Used) Cache.

Building an LRU Cache in Java

Java designed LinkedHashMap specifically to make building an LRU Cache effortless by overriding the removeEldestEntry method:

class LRUCache<K,V> extends LinkedHashMap<K,V> { private final int capacity; LRUCache(int capacity) { super(capacity, 0.75f, true); this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return size() > capacity; } }

---

4. HashMap vs. LinkedHashMap

Feature	HashMap	LinkedHashMap
Order Preserved	No	Yes (Insertion or Access)
Speed	Maximum optimization	Slightly slower (must update list)
Memory Usage	Standard	Higher (due to before/after pointers)
Iteration Style	Bucket Array Scan	Doubly Linked List Traversal
Time Complexity	$O(1)$	$O(1)$
Worst Case (Collisions)	$O(\log n)$ (Treeification)	$O(\log n)$ (Treeification)

The Real-Life Analogy

• HashMap is like a massive locker room. You can find your specific locker instantly based on your key number, but if asked to list everyone in the order they arrived, you have absolutely no idea.
• LinkedHashMap is a locker room where every person also holds hands with the person who arrived before them and the person who arrived after them. You get instant locker lookup, and you can perfectly trace the arrival queue.

The Final Internal Flow Checklist

For put(key, value):

1. Calculate hash & find bucket index.
2. Insert node into the hash table.
3. Connect node to the doubly linked list.
4. Update internal head / tail tracking.

For get(key):

1. Find bucket & traverse the chain/tree to match the key.
2. Return value.
3. If accessOrder=true: Sever node's current before/after links and reconnect it directly to the tail.