Definition
- Insertion order: default mode; iteration returns entries in the order they were put into the map
- Access order:
new LinkedHashMap<>(capacity, loadFactor, true)– entries move to the end on get or put of existing key - LRU cache: combine access order with
removeEldestEntry()override to auto-evict the least recently used entry - Same performance: O(1) get/put, same hash-based lookup as HashMap
- Memory: ~8 bytes more per entry for the before/after linked-list pointers
HashMap is like tossing receipts into a shoebox – fast but no order. LinkedHashMap is like placing receipts in a binder with plastic sleeves, one after another – same speed but you can flip through them in the exact order you filed them. For LRU mode, the most recently accessed receipt moves to the back, and when the binder is full, the front receipt (oldest unused) is removed.
Understanding the Concepts
When should you use LinkedHashMap over HashMap?
LinkedHashMap is the right choice when the order of entries matters. Here are the specific scenarios:
Scenario 1: Preserving insertion order for serialization
package com.bank.service;
import java.util.*;
public class JsonOrderDemo {
public static void main(String[] args) {
// HashMap: field order is unpredictable in JSON output
Map<String, Object> hashResponse = new HashMap<>();
hashResponse.put("status", "SUCCESS");
hashResponse.put("accountId", "SAV2001");
hashResponse.put("balance", 150000);
System.out.println("HashMap: " + hashResponse);
// LinkedHashMap: fields appear in insertion order
Map<String, Object> linkedResponse = new LinkedHashMap<>();
linkedResponse.put("status", "SUCCESS");
linkedResponse.put("accountId", "SAV2001");
linkedResponse.put("balance", 150000);
System.out.println("LinkedHashMap: " + linkedResponse);
}
}
HashMap: {balance=150000, accountId=SAV2001, status=SUCCESS}
LinkedHashMap: {status=SUCCESS, accountId=SAV2001, balance=150000}
Scenario 2: Building an LRU cache
package com.bank.service;
import java.math.BigDecimal;
import java.util.*;
public class BalanceCacheService {
private final Map<String, BigDecimal> cache;
public BalanceCacheService(int maxSize) {
this.cache = new LinkedHashMap<>(maxSize * 4 / 3 + 1, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, BigDecimal> eldest) {
boolean shouldEvict = size() > maxSize;
if (shouldEvict) {
System.out.println("Evicting: " + eldest.getKey());
}
return shouldEvict;
}
};
}
public BigDecimal getBalance(String accountId) {
return cache.get(accountId); // moves to end in access-order mode
}
public void updateBalance(String accountId, BigDecimal balance) {
cache.put(accountId, balance);
}
public static void main(String[] args) {
BalanceCacheService service = new BalanceCacheService(3);
service.updateBalance("SAV2001", new BigDecimal("150000"));
service.updateBalance("CUR3001", new BigDecimal("75000"));
service.updateBalance("FD4001", new BigDecimal("500000"));
// Access SAV2001 – moves to end (most recently used)
service.getBalance("SAV2001");
// Add new entry – evicts CUR3001 (least recently used)
service.updateBalance("LON5001", new BigDecimal("200000"));
}
}
Evicting: CUR3001
Scenario 3: Deterministic testing
// HashMap: iteration order may differ between JVM runs
// This makes test assertions fragile
Map<String, String> hashMap = new HashMap<>();
hashMap.put("A", "1"); hashMap.put("B", "2");
// hashMap.toString() might be "{A=1, B=2}" or "{B=2, A=1}"
// LinkedHashMap: always the same order
Map<String, String> linkedMap = new LinkedHashMap<>();
linkedMap.put("A", "1"); linkedMap.put("B", "2");
// linkedMap.toString() is always "{A=1, B=2}"
How does access-order mode work internally?
In access-order mode, every get() or put() on an existing key moves the entry to the tail of the doubly-linked list. The head of the list is the least recently used entry. This is the foundation of LRU behavior.
Internally, each entry has before and after pointers. On access, the entry is unlinked from its current position and re-linked at the tail. This is O(1) because it only updates 4-6 pointers.
What are common mistakes?
Mistake: Iterating a LinkedHashMap in access-order mode causes ConcurrentModificationException
Map<String, String> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("A", "1"); map.put("B", "2"); map.put("C", "3");
// WRONG: get() during iteration modifies the linked list (structural change)
try {
for (var entry : map.entrySet()) {
map.get(entry.getKey()); // moves entry → ConcurrentModificationException!
}
} catch (ConcurrentModificationException e) {
System.out.println("CME: get() in access-order mode is structural");
}
What should a senior engineer know?
- Access-order get() is a structural modification. In access-order mode, get() moves the entry in the linked list. This counts as a structural modification, so get() during iteration throws CME. In insertion-order mode, get() does not modify the list.
- LinkedHashMap is not thread-safe. For a concurrent LRU cache, use ConcurrentHashMap with manual eviction or a library like Caffeine or Guava's CacheBuilder.
- removeEldestEntry is called after every put. If it returns true, the eldest entry (head of linked list) is removed. The method receives the eldest entry as a parameter so you can log or process it before eviction.
What are common interview follow-up questions?
- "How do you implement an LRU cache in Java?" – LinkedHashMap with accessOrder=true + removeEldestEntry.
- "What is the memory overhead of LinkedHashMap?" – ~8 bytes per entry for before/after pointers.
- "Is get() safe during iteration in access-order mode?" – No, it throws CME because it is a structural modification.
Visual Overview
LinkedHashMap modes Insertion order (default): put(A), put(B), put(C), get(A) Iteration: A → B → C (get does not change order) Access order (accessOrder=true): put(A), put(B), put(C), get(A) Iteration: B → C → A (get moves A to end) LRU cache (access order + removeEldestEntry): [eldest/LRU] ← B ← C ← A → [most recent] put(D) → evict B (eldest) [eldest/LRU] ← C ← A ← D → [most recent]
Key Takeaway
LinkedHashMap is HashMap with predictable iteration order. In insertion-order mode (default), it is perfect for JSON serialization, config file processing, and deterministic test output. In access-order mode, it becomes an O(1) LRU cache: the least recently used entry is always at the head, and the removeEldestEntry hook automatically evicts it when the cache exceeds its size limit.
In the National Bank of India system, Rajesh uses LinkedHashMap for API responses so that JSON fields always appear in a consistent, readable order (status first, then account details, then balance). For the session balance cache, he uses access-order LinkedHashMap capped at 10,000 entries – when a new account is looked up, the least recently accessed balance is evicted.
Remember one sentence: use LinkedHashMap when iteration order must match insertion order, or when you need an O(1) LRU cache with automatic eviction.
---