LinkedHashMap in Java

LinkedHashMap in Java is a class that extends HashMap and keeps its entries in a predictable order. By default, the order is insertion order: entries come out in the order their keys were first added. It can also be switched to access order, where every read moves an entry to the end. Inside, it is a HashMap plus a doubly linked list running through all the entries. In this lesson, you will learn how to use LinkedHashMap and how to build an LRU cache with it, a classic interview problem.

Declaration

public class LinkedHashMap<K, V> extends HashMap<K, V>
        implements SequencedMap<K, V>

Features of LinkedHashMap

• Ordered: insertion order by default, or access order if requested.
• Fast: the same O(1) average operations as HashMap.
• One null key and many null values.
• Putting an existing key again doesn't change its position in insertion-order mode.
• Sequenced (Java 21): firstEntry, lastEntry, pollFirstEntry, reversed and more.
• Not synchronized.

Constructors

Example: Insertion Order

Let's see an example comparing it with the order rules.

import java.util.LinkedHashMap;
import java.util.Map;
 
public class LinkedOrder {
    public static void main(String[] args) {
        Map<String, Integer> marks = new LinkedHashMap<>();
        marks.put("Srihitha", 78);
        marks.put("Navika", 91);
        marks.put("Advitha", 85);
        System.out.println(marks);
 
        marks.put("Srihitha", 88);
        System.out.println(marks);
    }
}

{Srihitha=78, Navika=91, Advitha=85}
{Srihitha=88, Navika=91, Advitha=85}

Explanation: Entries print in the order they were added. Updating Srihitha's mark changes the value but keeps Srihitha in first place.

Access Order

With accessOrder = true, every get or put of a key moves that entry to the end. The first entry is then always the least recently used one:

import java.util.LinkedHashMap;
import java.util.Map;
 
public class AccessOrder {
    public static void main(String[] args) {
        Map<String, Integer> m = new LinkedHashMap<>(16, 0.75f, true);
        m.put("Navika", 1);
        m.put("Srihitha", 2);
        m.put("Advitha", 3);
        System.out.println(m);
 
        m.get("Navika");
        System.out.println(m);
    }
}

{Navika=1, Srihitha=2, Advitha=3}
{Srihitha=2, Advitha=3, Navika=1}

Explanation: Reading Navika moved that entry to the end. Srihitha, untouched for longest, is now first.

The Checkpoint: An LRU Cache

An LRU (least recently used) cache holds a fixed number of entries. When it is full and a new entry arrives, it removes the entry that was used longest ago. LinkedHashMap makes this almost free: use access order, and override removeEldestEntry, which the map calls after every put.

import java.util.LinkedHashMap;
import java.util.Map;
 
public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
 
    public LruCache(int capacity) {
        super(16, 0.75f, true);
        this.capacity = capacity;
    }
 
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
 
    public static void main(String[] args) {
        LruCache<String, String> cache = new LruCache<>(3);
        cache.put("A", "page A");
        cache.put("B", "page B");
        cache.put("C", "page C");
        System.out.println(cache.keySet());
 
        cache.get("A");
        System.out.println("after get(A): " + cache.keySet());
 
        cache.put("D", "page D");
        System.out.println("after put(D): " + cache.keySet());
    }
}

[A, B, C]
after get(A): [B, C, A]
after put(D): [C, A, D]

Explanation: super(16, 0.75f, true) turns on access order. Reading A moved it to the end, so B became the least recently used. When D was added, the size became 4, removeEldestEntry returned true, and the map removed B, its eldest entry.

Common Mistakes

Forgetting the third constructor argument. Without true, the map stays in insertion order and the "LRU" cache evicts the oldest inserted entry instead.

Expecting put of an existing key to move it in insertion-order mode. Only access-order mode moves entries.

Iterating an access-order map with get calls inside the loop. Each get reorders the map and throws ConcurrentModificationException.

Interview Corner

Practice

1. Easy: Store the first five countries a user enters in a LinkedHashMap from country to capital, and print them in input order.
2. Harder: Change the LRU cache so it prints a message naming the evicted key every time an entry is removed.

Key Takeaways