LinkedHashMap

#Introduction

LinkedHashMap is essentially HashMap + predictable ordering.

It gives you the fast average lookup characteristics of HashMap while maintaining a predictable iteration order.

The two modes you must know for interviews are:

1. Insertion order
2. Access order

The second one leads directly to the classic LRU Cache interview problem.

#What is LinkedHashMap?

Package:

java.util.LinkedHashMap

#Why Does LinkedHashMap Exist?

Map<Integer, String> map = new HashMap<>();

You cannot rely on HashMap iteration order. If you need "give me entries in the order they were inserted", use:

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

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

3 → C
1 → A
2 → B

#Internal Structure

This is the most important internal concept. A normal HashMap has table → bucket → Node → Node. LinkedHashMap additionally maintains links between entries: hash table + doubly linked list.

Each entry participates in:

1. The hash table structure
2. The linked ordering structure

LinkedHashMap Entry

HashMap's basic node contains hash, key, value, next. LinkedHashMap adds ordering links before and after:

• next is associated with the hash bucket.
• before and after maintain the linked ordering.

Two Structures at the Same Time

This is the key to understanding LinkedHashMap.

map.put(10, "A");
map.put(20, "B");
map.put(30, "C");

#Insertion Order

The default constructor uses insertion-order behaviour:

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

map.put(10, "A");
map.put(20, "B");
map.put(30, "C");

Iteration: 10, 20, 30.

Updating an Existing Key

Important interview detail:

map.put(10, "A");
map.put(20, "B");
map.put(30, "C");
map.put(20, "Updated");

Does 20 move to the end? No, in normal insertion-order mode. The result is still 10, 20, 30 — only the value changes.

Why Doesn't Updating Move It?

Because the key already exists. In insertion-order mode:

The ordering represents the order in which entries were inserted, not the order in which values were updated.

So map.put(existingKey, newValue); doesn't normally change its position.

#Access Order

LinkedHashMap has another mode: accessOrder = true.

LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);

Insertion Order vs Access Order

The accessed entry moves to the end. This is the foundation of LRU caches.

What Counts as an Access?

In access-order mode, several Map operations can count as an access, including get(), getOrDefault(), putIfAbsent(), replace(), compute(), computeIfAbsent(), computeIfPresent() and merge() — depending on whether the operation actually accesses/replaces an existing mapping according to the API semantics.

get() Can Modify LinkedHashMap

This surprises many candidates. With accessOrder = true, calling map.get(key); can move the accessed entry to the tail. Therefore, unlike an ordinary HashMap lookup:

A get() can cause a structural ordering change in an access-order LinkedHashMap.

This matters during iteration.

Access Order Example

LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);

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

#LRU Cache

LRU means Least Recently Used. Suppose the cache capacity is 3:

LinkedHashMap's access-order mode makes this pattern extremely convenient.

Building an LRU Cache

Classic implementation:

class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

Usage:

LRUCache<Integer, String> cache = new LRUCache<>(3);

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

cache.get(1);

cache.put(4, "D");

The least recently used entry (2) is automatically removed.

removeEldestEntry()

This method is the key to the LRU implementation:

protected boolean removeEldestEntry(Map.Entry<K,V> eldest)

If it returns true, the eldest entry is removed after an insertion. For an LRU cache: return size() > capacity;

Why removeEldestEntry() Is Useful

Without it, you'd need: insert → check capacity → find least-recently-used entry → remove it. LinkedHashMap already maintains the ordering, so access-order + removeEldestEntry() gives you a simple LRU cache.

LRU Logic

With access order: Head = Least Recently Used … Most Recently Used = Tail. So the eldest = least recently used entry when the map is being used as an LRU cache.

LRU Example Step-by-Step

Capacity 3:

removeEldestEntry() Subtlety

The method is called after a new mapping has been inserted. Therefore the common condition return size() > capacity; works naturally: with capacity = 3, inserting the 4th entry makes size = 4, 4 > 3, so the eldest is removed.

Is an LRU Cache O(1)?

The standard LinkedHashMap-based implementation provides approximately:

This makes it a very attractive implementation for an in-memory LRU cache. The actual performance still depends on hashing and implementation details.

Is LinkedHashMap a Thread-Safe LRU Cache?

#Comparisons

LinkedHashMap vs HashMap

The trade-off: predictable ordering ↔ additional memory / bookkeeping.

LinkedHashMap vs TreeMap

Choose based on the required ordering semantics.

When to Use Which?

• Use HashMap when ordering doesn't matter.
• Use LinkedHashMap when you need predictable insertion order or access order — e.g. an API response that must preserve insertion order.

#Iteration and Views

entrySet()

Iteration is predictable because the linked structure controls traversal:

for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

The iteration follows the LinkedHashMap's ordering mode.

keySet() and values()

These views also reflect the map's ordering. After put(3, "C"), put(1, "A"), put(2, "B"), keySet() iterates 3, 1, 2 and values() follows the same entry ordering.

Does LinkedHashMap Sort Keys?

No. This is an important distinction.

map.put(30, "C");
map.put(10, "A");
map.put(20, "B");

LinkedHashMap gives 30, 10, 20 — not 10, 20, 30. If you need sorted keys, use TreeMap.

#Null, Capacity and Constructors

Null Keys and Values

LinkedHashMap inherits HashMap's basic null behaviour: one null key and multiple null values.

map.put(null, "A");
map.put(null, "B");

Final mapping: null → B.

Capacity and Load Factor

LinkedHashMap supports the same capacity/load-factor configuration as HashMap:

new LinkedHashMap<>(100, 0.75f);

The linked structure adds ordering information, but the underlying hash-table capacity/load-factor concepts remain relevant.

Access-Order Constructor

Memorize this constructor:

new LinkedHashMap<>(initialCapacity, loadFactor, accessOrder);

new LinkedHashMap<>(16, 0.75f, true);

With new LinkedHashMap<>(), the default is accessOrder = false, so insertion order is the default.

#Decision Framework

For concurrent access, use ConcurrentHashMap.

HashMap vs LinkedHashMap vs TreeMap

Final Mental Model