How to Use LinkedHashMap in Java: Order and an LRU Cache

Four books on a shelf, and a cache that forgets

A library keeps its catalogue in the order books arrived, and it keeps a short "recently looked up" list that quietly drops whatever nobody has asked about lately. Both of those are one class from the standard library, and this is what the finished program prints for them:

Shelf order: [Effective Java (978-0134685991), Java Concurrency in Practice (978-1617297571), Head First Design Patterns (978-0596009205), Designing Data-Intensive Applications (978-1491950357)]
After editing the 2nd book: [Effective Java (978-0134685991), Java Concurrency in Practice (2nd printing) (978-1617297571), Head First Design Patterns (978-0596009205), Designing Data-Intensive Applications (978-1491950357)]
After moving Effective Java to the end: [Java Concurrency in Practice (2nd printing) (978-1617297571), Head First Design Patterns (978-0596009205), Designing Data-Intensive Applications (978-1491950357), Effective Java (978-0134685991)]
Newest first: [Effective Java (978-0134685991), Designing Data-Intensive Applications (978-1491950357), Head First Design Patterns (978-0596009205), Java Concurrency in Practice (2nd printing) (978-1617297571)]
Oldest: Java Concurrency in Practice (2nd printing) (978-1617297571), newest: Effective Java (978-0134685991)

Cache after 4 puts (capacity 3): [Head First Design Patterns (978-0596009205), Designing Data-Intensive Applications (978-1491950357), Effective Java (978-0134685991)]
After get(Head First): [Designing Data-Intensive Applications (978-1491950357), Effective Java (978-0134685991), Head First Design Patterns (978-0596009205)]
After adding Clean Code: [Effective Java (978-0134685991), Head First Design Patterns (978-0596009205), Clean Code (978-0000000001)]
Evictions so far: 2

The first four lines are a LinkedHashMap doing the plain job: iteration order is insertion order, editing a book doesn't move it, and moving it takes an explicit remove and put. The last four lines are the same class with one constructor flag flipped. It's now ordered by last access, and with a five-line override it becomes an LRU cache that evicts the entry nobody has touched.

If you searched for how to use LinkedHashMap in Java, you probably want one of those two things. I'll build both on a small library catalogue, then force the surprises that catch people: reads that reorder the map, loops that throw because of a get(), an "LRU" that's secretly FIFO, and a shared cache that doesn't throw when it breaks. It's written for someone who knows Map and HashMap already. There's no library to install.

Before you start

Java 21 matters for a handful of methods. reversed(), putFirst(), putLast(), firstEntry() and friends arrived with sequenced collections in Java 21 (JEP 431). The LRU cache class itself uses nothing newer than LinkedHashMap's three-argument constructor, and I confirmed it compiles with --release 17. The project as a whole needs 21 (records need 16, Traps uses arrow-style switch, Catalogue uses SequencedMap). I show what 17 says about the rest in the troubleshooting section.

I built and ran everything from the shell, then once more through Gradle with --offline. Maven Central wasn't reachable from my build machine, so there's no JUnit: the tests are 22 plain checks in a main method that exit with status 1 when one fails. The IDE steps below come from the vendors' documentation and I didn't click through them. Nearly all the time went on the threaded demo near the end, which I expected to throw an exception and which corrupted the map without a sound instead.

Put the library project together

I'm using the plain shell as the primary path this time, because the project is six files and no dependencies.

mkdir library-catalogue && cd library-catalogue
mkdir -p src/main/java/com/example/library

The finished layout:

library-catalogue/
├── build.gradle.kts          (optional, for Gradle)
├── settings.gradle.kts       (optional, for Gradle)
└── src/main/java/com/example/library/
    ├── Book.java
    ├── Catalogue.java
    ├── RecentLookups.java
    ├── Main.java
    ├── Traps.java
    └── Checks.java

In IntelliJ IDEA

Choose File → New → Project…, pick Java on the left, set the build system to IntelliJ (or Gradle if you want the files below), and select a JDK 21 in the JDK field. Name the project library-catalogue, then create the com.example.library package under src and add the six classes. Right-click a class with a main method and choose Run. Menu labels shift between releases, so treat these as a guide and check the New Project help page for your version.

In Eclipse

Choose File → New → Java Project, enter library-catalogue, and under JRE choose an execution environment of JavaSE-21 (Window → Preferences → Java → Installed JREs if it isn't listed). Create the package, paste in the classes, then use Run → Run As → Java Application on Main.

With Gradle

build.gradle.kts:

plugins {
    application
}

java {
    sourceCompatibility = JavaVersion.VERSION_21
    targetCompatibility = JavaVersion.VERSION_21
}

repositories {
    mavenCentral()
}

application {
    mainClass.set("com.example.library.Main")
}

tasks.register<JavaExec>("checks") {
    classpath = sourceSets["main"].runtimeClasspath
    mainClass.set("com.example.library.Checks")
}

settings.gradle.kts:

rootProject.name = "library-catalogue"

gradle run starts Main and gradle checks runs the checks, both of which I ran with --offline. Everything below uses plain javac so the commands are the same on every machine. I didn't test Windows. If a *.java glob doesn't expand in your shell, list the files by name or put them in a text file and run javac @sources.txt.

How to use LinkedHashMap in Java, from shelf order to LRU

Four steps. Each one compiles on its own, so run the checkpoint before moving on.

Step 1: Describe a book

Goal: a small value type to use as the map's value.

src/main/java/com/example/library/Book.java:

package com.example.library;

/** One catalogue entry. A record gives us equals(), hashCode() and toString() for free. */
public record Book(String isbn, String title, String author) {

    public Book {
        if (isbn == null || isbn.isBlank()) {
            throw new IllegalArgumentException("isbn is required");
        }
    }

    @Override
    public String toString() {
        return title + " (" + isbn + ")";
    }
}

A record gives you equals(), hashCode() and accessors without writing them; see how to use Java records if that's new. The constructor guards the ISBN because it's the map key, and a blank key would be a bug that only shows up later. The toString() override keeps the console output short.

Checkpoint:

mkdir -p out
javac -Xlint:all -d out src/main/java/com/example/library/Book.java

No output means it compiled cleanly.

Step 2: Keep the shelf in insertion order

Goal: a catalogue that remembers the order books were added, can move one to the end, and can read both ends.

src/main/java/com/example/library/Catalogue.java:

package com.example.library;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.SequencedMap;

/** The shelf order of the library: books come out in the order they were added. */
public class Catalogue {

    private final SequencedMap<String, Book> shelf = new LinkedHashMap<>();

    /** Adds a book, or replaces the details of one we already have. Replacing keeps its place on the shelf. */
    public void add(Book book) {
        shelf.put(book.isbn(), book);
    }

    /** Moves an existing book to the end of the shelf. Re-putting is not enough, so remove first. */
    public boolean moveToEnd(String isbn) {
        Book book = shelf.remove(isbn);
        if (book == null) {
            return false;
        }
        shelf.put(isbn, book);
        return true;
    }

    public Optional<Book> find(String isbn) {
        return Optional.ofNullable(shelf.get(isbn));
    }

    /** Shelf order, oldest first. A copy, so callers can't reorder our shelf. */
    public List<Book> inShelfOrder() {
        return List.copyOf(shelf.values());
    }

    /** Java 21: the same list, newest first, without copying into a reversed list by hand. */
    public List<Book> newestFirst() {
        return new ArrayList<>(shelf.reversed().values());
    }

    public Optional<Book> oldest() {
        return Optional.ofNullable(shelf.firstEntry()).map(Map.Entry::getValue);
    }

    public Optional<Book> newest() {
        return Optional.ofNullable(shelf.lastEntry()).map(Map.Entry::getValue);
    }

    public int size() {
        return shelf.size();
    }
}

Three things in there are worth a second look.

The field is declared as SequencedMap<String, Book> but built as new LinkedHashMap<>(). A LinkedHashMap is an ordinary HashMap plus a doubly linked list through its entries, and the list is what remembers order. Declaring the field as the Java 21 interface gives you reversed(), firstEntry() and lastEntry() without a cast. If you need to stay on Java 17 or earlier, declare it as Map and drop those three methods.

add() uses plain put. In an insertion-ordered map, putting a key that's already there replaces the value and leaves the entry exactly where it was. That's the behaviour you want for "update the details of a book", and it surprises people who expect re-adding to move it. When you do want to move it, moveToEnd() removes and puts again. I check both behaviours below.

inShelfOrder() returns List.copyOf(shelf.values()). Handing out shelf.values() directly would give callers a live view that can remove books from your catalogue. Compare that with the same copy-on-exit habit in how to create an immutable class in Java.

Checkpoint:

javac -Xlint:all -d out src/main/java/com/example/library/Book.java src/main/java/com/example/library/Catalogue.java

Still silent.

Step 3: Turn the map into an LRU cache

Goal: a "recent lookups" cache that holds at most N entries and evicts the least recently used one.

src/main/java/com/example/library/RecentLookups.java:

package com.example.library;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * A small least-recently-used cache. The third constructor argument (true) switches the map
 * from insertion order to access order, and removeEldestEntry says when to evict.
 */
public class RecentLookups<K, V> extends LinkedHashMap<K, V> {

    private static final long serialVersionUID = 1L;

    private final int capacity;
    private int evictions;

    public RecentLookups(int capacity) {
        super(16, 0.75f, true);
        if (capacity < 1) {
            throw new IllegalArgumentException("capacity must be at least 1: " + capacity);
        }
        this.capacity = capacity;
    }

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

    public int evictions() {
        return evictions;
    }
}

Two details make this work. The constructor calls super(16, 0.75f, true). The first two numbers are the default capacity and load factor, which you can leave at those values. The third is accessOrder, and true means "order by last access instead of insertion". Forget it and you get a first-in, first-out cache, which I demonstrate below because I'd bet it's the most common bug in hand-written Java caches.

The second is removeEldestEntry. put() calls it after inserting a new entry, passing the eldest one, which in an access-ordered map is the least recently used. Return true and the map removes it. The Javadoc advises against changing the map inside this method and letting the return value do the removal, so I only count evictions there.

serialVersionUID is there because LinkedHashMap is serializable, and -Xlint:all will warn about its absence on a subclass. I hit that warning on my first compile; it's in the troubleshooting section.

Checkpoint:

javac -Xlint:all -d out src/main/java/com/example/library/*.java

Wait until Step 4 to run it; Main doesn't exist yet.

Step 4: Try both from a main method

Goal: see the order change, one call at a time.

src/main/java/com/example/library/Main.java:

package com.example.library;

public class Main {

    public static void main(String[] args) {
        Catalogue catalogue = new Catalogue();
        catalogue.add(new Book("978-0134685991", "Effective Java", "Joshua Bloch"));
        catalogue.add(new Book("978-1617297571", "Java Concurrency in Practice", "Brian Goetz"));
        catalogue.add(new Book("978-0596009205", "Head First Design Patterns", "Eric Freeman"));
        catalogue.add(new Book("978-1491950357", "Designing Data-Intensive Applications", "Martin Kleppmann"));

        System.out.println("Shelf order: " + catalogue.inShelfOrder());

        catalogue.add(new Book("978-1617297571", "Java Concurrency in Practice (2nd printing)", "Brian Goetz"));
        System.out.println("After editing the 2nd book: " + catalogue.inShelfOrder());

        catalogue.moveToEnd("978-0134685991");
        System.out.println("After moving Effective Java to the end: " + catalogue.inShelfOrder());
        System.out.println("Newest first: " + catalogue.newestFirst());
        System.out.println("Oldest: " + catalogue.oldest().orElseThrow() + ", newest: " + catalogue.newest().orElseThrow());

        System.out.println();
        RecentLookups<String, Book> recent = new RecentLookups<>(3);
        for (Book b : catalogue.inShelfOrder()) {
            recent.put(b.isbn(), b);
        }
        System.out.println("Cache after 4 puts (capacity 3): " + recent.values());
        recent.get("978-0596009205");
        System.out.println("After get(Head First): " + recent.values());
        recent.put("978-0000000001", new Book("978-0000000001", "Clean Code", "Robert Martin"));
        System.out.println("After adding Clean Code: " + recent.values());
        System.out.println("Evictions so far: " + recent.evictions());
    }
}

Checkpoint: compile everything and run it.

javac -Xlint:all -d out src/main/java/com/example/library/*.java
java -cp out com.example.library.Main

You should see the output at the top of this article. If you do, the hard part's done. The spots to read closely: after editing the second book, it's still second; after moveToEnd, Effective Java jumps from first to last; and in the cache, get(Head First) moved that book from the front to the back, so adding Clean Code evicted Effective Java rather than Head First Design Patterns.

Run it and watch the order change

Reading code to work out order is slow, so here's a more direct view. Traps prints one line per experiment. First, which calls on an access-ordered map count as "use":

java -cp out com.example.library.Traps

2. get                          -> [B, C, A]  A moved to the end
3. getOrDefault                 -> [B, C, A]  A moved to the end
4. containsKey                  -> [A, B, C]  A stayed first
5. put (existing)               -> [B, C, A]  A moved to the end
6. putIfAbsent (existing)       -> [B, C, A]  A moved to the end
7. computeIfAbsent (existing)   -> [B, C, A]  A moved to the end
8. merge                        -> [B, C, A]  A moved to the end
9. replace                      -> [B, C, A]  A moved to the end
10. keySet().iterator()          -> [A, B, C]  A stayed first
11. entrySet() loop              -> [A, B, C]  A stayed first

get, getOrDefault, put on an existing key, putIfAbsent, computeIfAbsent, merge and replace all move the entry to the end. containsKey and plain iteration don't. That matches the class documentation, which lists put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent and merge, and says replace counts when it actually replaces a value. The practical consequence: if you want to check whether something is cached without protecting it from eviction, use containsKey. And a method that looks read-only to you, like getOrDefault, is a write as far as the map's internals are concerned.

Pin the behaviour with 22 checks

src/main/java/com/example/library/Checks.java:

package com.example.library;

import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/** Plain checks, no test library needed. Exits with status 1 if any check fails. */
public class Checks {

    private static int passed;
    private static int failed;

    private static void check(String name, boolean ok) {
        if (ok) {
            passed++;
            System.out.println("PASS  " + name);
        } else {
            failed++;
            System.out.println("FAIL  " + name);
        }
    }

    private static Book book(String isbn) {
        return new Book(isbn, "Title " + isbn, "Author");
    }

    private static Catalogue threeBooks() {
        Catalogue c = new Catalogue();
        c.add(book("1"));
        c.add(book("2"));
        c.add(book("3"));
        return c;
    }

    private static List<String> isbns(List<Book> books) {
        return books.stream().map(Book::isbn).toList();
    }

    public static void main(String[] args) {
        Catalogue c = threeBooks();
        check("shelf keeps the order books were added", isbns(c.inShelfOrder()).equals(List.of("1", "2", "3")));

        c.add(new Book("2", "Second edition", "Author"));
        check("re-adding a book keeps its place", isbns(c.inShelfOrder()).equals(List.of("1", "2", "3")));
        check("re-adding a book updates the details", c.find("2").orElseThrow().title().equals("Second edition"));

        check("moveToEnd moves an existing book", c.moveToEnd("1") && isbns(c.inShelfOrder()).equals(List.of("2", "3", "1")));
        check("moveToEnd on an unknown isbn returns false", !c.moveToEnd("99"));
        check("newestFirst is the reverse of shelf order", isbns(c.newestFirst()).equals(List.of("1", "3", "2")));
        check("oldest and newest", c.oldest().orElseThrow().isbn().equals("2") && c.newest().orElseThrow().isbn().equals("1"));
        check("empty catalogue has no oldest", new Catalogue().oldest().isEmpty());
        boolean copyBlocked;
        try {
            c.inShelfOrder().add(book("9"));
            copyBlocked = false;
        } catch (UnsupportedOperationException e) {
            copyBlocked = true;
        }
        check("inShelfOrder() hands out an unmodifiable copy", copyBlocked);
        boolean nullIsbn;
        try {
            new Book(null, "x", "y");
            nullIsbn = false;
        } catch (IllegalArgumentException e) {
            nullIsbn = true;
        }
        check("Book rejects a null isbn", nullIsbn);

        RecentLookups<String, Integer> lru = new RecentLookups<>(3);
        lru.put("a", 1); lru.put("b", 2); lru.put("c", 3);
        lru.put("d", 4);
        check("LRU drops the eldest when over capacity", List.copyOf(lru.keySet()).equals(List.of("b", "c", "d")));
        check("LRU counts the eviction", lru.evictions() == 1);

        lru.get("b");
        lru.put("e", 5);
        check("get() protects an entry from the next eviction", List.copyOf(lru.keySet()).equals(List.of("d", "b", "e")));

        RecentLookups<String, Integer> peek = new RecentLookups<>(3);
        peek.put("a", 1); peek.put("b", 2); peek.put("c", 3);
        peek.containsKey("a");
        peek.put("d", 4);
        check("containsKey() does not protect an entry", !peek.containsKey("a"));

        RecentLookups<String, Integer> same = new RecentLookups<>(2);
        same.put("a", 1); same.put("b", 2);
        same.put("a", 10);
        check("overwriting an existing key never evicts", same.size() == 2 && same.evictions() == 0);
        check("overwriting an existing key refreshes it", List.copyOf(same.keySet()).equals(List.of("b", "a")));

        RecentLookups<String, Integer> one = new RecentLookups<>(1);
        one.put("a", 1); one.put("b", 2);
        check("capacity 1 keeps only the newest", List.copyOf(one.keySet()).equals(List.of("b")));

        boolean zeroCap;
        try {
            new RecentLookups<String, Integer>(0);
            zeroCap = false;
        } catch (IllegalArgumentException e) {
            zeroCap = true;
        }
        check("capacity 0 is rejected", zeroCap);

        RecentLookups<String, Integer> miss = new RecentLookups<>(3);
        miss.put("a", 1); miss.put("b", 2);
        miss.getOrDefault("zzz", 0);
        check("getOrDefault on a missing key inserts nothing", miss.size() == 2 && !miss.containsKey("zzz"));

        RecentLookups<String, Integer> poll = new RecentLookups<>(3);
        poll.put("a", 1); poll.put("b", 2); poll.get("a");
        check("pollFirstEntry takes the least recently used", poll.pollFirstEntry().getKey().equals("b"));

        Map<String, Integer> linked = new LinkedHashMap<>();
        linked.put("b", 1); linked.put("a", 2);
        Map<String, Integer> sorted = new TreeMap<>(linked);
        check("LinkedHashMap keeps insertion order, TreeMap sorts",
                List.copyOf(linked.keySet()).equals(List.of("b", "a")) && List.copyOf(sorted.keySet()).equals(List.of("a", "b")));

        Map<String, Integer> sized = LinkedHashMap.newLinkedHashMap(100);
        for (int i = 0; i < 100; i++) sized.put("k" + i, i);
        check("newLinkedHashMap(100) holds 100 entries", sized.size() == 100);

        System.out.println();
        System.out.println(passed + " passed, " + failed + " failed");
        if (failed > 0) {
            System.exit(1);
        }
    }
}

java -cp out com.example.library.Checks

PASS  shelf keeps the order books were added
PASS  re-adding a book keeps its place
PASS  re-adding a book updates the details
PASS  moveToEnd moves an existing book
PASS  moveToEnd on an unknown isbn returns false
PASS  newestFirst is the reverse of shelf order
PASS  oldest and newest
PASS  empty catalogue has no oldest
PASS  inShelfOrder() hands out an unmodifiable copy
PASS  Book rejects a null isbn
PASS  LRU drops the eldest when over capacity
PASS  LRU counts the eviction
PASS  get() protects an entry from the next eviction
PASS  containsKey() does not protect an entry
PASS  overwriting an existing key never evicts
PASS  overwriting an existing key refreshes it
PASS  capacity 1 keeps only the newest
PASS  capacity 0 is rejected
PASS  getOrDefault on a missing key inserts nothing
PASS  pollFirstEntry takes the least recently used
PASS  LinkedHashMap keeps insertion order, TreeMap sorts
PASS  newLinkedHashMap(100) holds 100 entries

22 passed, 0 failed

Three of these are my favourites. "re-adding a book keeps its place" is the one that stops someone "fixing" add() into a remove-then-put. "containsKey() does not protect an entry" pins the access rule from the table above. And "overwriting an existing key never evicts" covers the off-by-one that you get if you write size() >= capacity in removeEldestEntry. With >, as here, an overwrite at full capacity is harmless.

What the linked list does inside the map

A HashMap finds a key by hashing it to a bucket. Iteration walks the buckets, so the order depends on hash codes and table size, and Java promises nothing about it. LinkedHashMap keeps that same table for lookups and adds a second structure: every entry also has a before and after pointer, forming one doubly linked list. Iteration walks that list instead of the buckets, which is why order is stable and also why iteration time depends on the number of entries rather than the table's capacity.

In insertion-order mode the list only changes when a new key goes on the tail, or when you remove one. In access-order mode, every "access" unlinks the entry and relinks it at the tail. That's cheap, constant time, but it's a structural change: it bumps the same modification counter that put and remove do. That single fact explains the next two surprises, the exception when you call get() inside a loop and the thread-safety problem.

removeEldestEntry is a hook the base class calls after an insert. The "eldest" is the head of the list: the oldest insertion, or the least recently used in access-order mode. So an LRU cache here is the list order plus one boolean. If you want sorted order instead, that's a different structure; see the forward-looking note on TreeMap in going further, and note that a LinkedHashMap never sorts by key. My checks include one that proves it.

Traps, forced one at a time

Everything here is from Traps.java, which I'll show in full so you can run it yourself.

src/main/java/com/example/library/Traps.java:

package com.example.library;

import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.SequencedMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.atomic.AtomicInteger;

/** Each method forces one surprise and prints what happened. */
public class Traps {

    static LinkedHashMap<String, Integer> three(boolean accessOrder) {
        LinkedHashMap<String, Integer> m = new LinkedHashMap<>(16, 0.75f, accessOrder);
        m.put("A", 1);
        m.put("B", 2);
        m.put("C", 3);
        return m;
    }

    public static void main(String[] args) throws Exception {
        forgotTheTrue();
        whichCallsCountAsAccess();
        getWhileIterating();
        sequencedMethods();
        equalsIgnoresOrder();
        threads();
    }

    static void forgotTheTrue() {
        LinkedHashMap<String, Integer> fifo = new LinkedHashMap<>(16, 0.75f) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, Integer> e) {
                return size() > 3;
            }
        };
        fifo.put("A", 1); fifo.put("B", 2); fifo.put("C", 3);
        fifo.get("A");
        fifo.put("D", 4);
        System.out.println("1. forgot accessOrder=true -> A was just read, still evicted: " + fifo.keySet());
    }

    static void whichCallsCountAsAccess() {
        String[] names = {"get", "getOrDefault", "containsKey", "put (existing)", "putIfAbsent (existing)",
                "computeIfAbsent (existing)", "merge", "replace", "keySet().iterator()", "entrySet() loop"};
        for (String name : names) {
            LinkedHashMap<String, Integer> m = three(true);
            switch (name) {
                case "get" -> m.get("A");
                case "getOrDefault" -> m.getOrDefault("A", 0);
                case "containsKey" -> m.containsKey("A");
                case "put (existing)" -> m.put("A", 10);
                case "putIfAbsent (existing)" -> m.putIfAbsent("A", 10);
                case "computeIfAbsent (existing)" -> m.computeIfAbsent("A", k -> 10);
                case "merge" -> m.merge("A", 1, Integer::sum);
                case "replace" -> m.replace("A", 10);
                case "keySet().iterator()" -> { for (String k : m.keySet()) { /* just iterate */ } }
                case "entrySet() loop" -> { for (Map.Entry<String, Integer> e : m.entrySet()) { e.getValue(); } }
                default -> throw new IllegalStateException(name);
            }
            boolean moved = !m.keySet().iterator().next().equals("A");
            System.out.printf("2. %-28s -> %s  A %s%n", name, m.keySet(), moved ? "moved to the end" : "stayed first");
        }
    }

    static void getWhileIterating() {
        LinkedHashMap<String, Integer> ordered = three(false);
        for (String k : ordered.keySet()) {
            ordered.get(k);
        }
        System.out.println("3a. insertion order: get() inside a loop is fine");

        LinkedHashMap<String, Integer> lru = three(true);
        try {
            for (String k : lru.keySet()) {
                lru.get(k);
            }
            System.out.println("3b. access order: no exception");
        } catch (ConcurrentModificationException e) {
            System.out.println("3b. access order: get() inside a loop -> " + e.getClass().getSimpleName());
        }
        LinkedHashMap<String, Integer> lru2 = three(true);
        for (String k : List.copyOf(lru2.keySet())) {
            lru2.get(k);
        }
        System.out.println("3c. iterate over a copy of the keys instead -> " + lru2.keySet());
    }

    static void sequencedMethods() {
        LinkedHashMap<String, Integer> m = three(false);
        m.putFirst("Z", 0);
        m.putLast("A", 1);
        System.out.println("4a. putFirst(Z), putLast(A) on insertion-order map -> " + m.keySet());
        System.out.println("4b. pollFirstEntry -> " + m.pollFirstEntry() + ", left " + m.keySet());
        System.out.println("4c. reversed() -> " + m.reversed().keySet());
        m.reversed().put("Q", 9);
        System.out.println("4d. reversed().put(Q) writes through -> " + m.keySet());

        LinkedHashMap<String, Integer> lru = three(true);
        lru.putFirst("C", 3);
        System.out.println("4e. putFirst(C) on access-order map -> " + lru.keySet());
        SequencedMap<String, Integer> view = Collections.unmodifiableSequencedMap(m);
        try {
            view.putLast("X", 1);
        } catch (UnsupportedOperationException e) {
            System.out.println("4f. unmodifiableSequencedMap.putLast -> UnsupportedOperationException");
        }
    }

    static void equalsIgnoresOrder() {
        LinkedHashMap<String, Integer> a = new LinkedHashMap<>();
        a.put("A", 1); a.put("B", 2);
        LinkedHashMap<String, Integer> b = new LinkedHashMap<>();
        b.put("B", 2); b.put("A", 1);
        System.out.println("5. equals() ignores order: " + a.equals(b) + ", but keySet().toString() differs: "
                + a.keySet() + " vs " + b.keySet());
    }

    static void threads() throws Exception {
        System.out.println("6a. unsynchronised access-order map, 8 threads, get-then-put: " + hammer(new RecentLookups<>(50)));
        Map<Integer, Integer> safe = Collections.synchronizedMap(new RecentLookups<>(50));
        System.out.println("6b. Collections.synchronizedMap around it:            " + hammer(safe));
    }

    static String hammer(Map<Integer, Integer> map) throws Exception {
        AtomicInteger errors = new AtomicInteger();
        CountDownLatch go = new CountDownLatch(1);
        Thread[] ts = new Thread[8];
        for (int t = 0; t < ts.length; t++) {
            final int seed = t;
            ts[t] = new Thread(() -> {
                try {
                    go.await();
                    for (int i = 0; i < 300_000; i++) {
                        int key = (i * 31 + seed * 17) % 120;
                        if (map.get(key) == null) {
                            map.put(key, key);
                        }
                    }
                } catch (Throwable e) {
                    if (errors.incrementAndGet() == 1) {
                        System.out.println("     first failure: " + e);
                    }
                }
            });
            ts[t].start();
        }
        go.countDown();
        for (Thread t : ts) t.join();
        int reported;
        int walked = 0;
        java.util.Set<Integer> distinct = new java.util.HashSet<>();
        synchronized (map) {
            reported = map.size();
            for (Integer k : map.keySet()) {
                distinct.add(k);
                if (++walked > 10_000) break;
            }
        }
        return "failed threads=" + errors.get() + ", size()=" + reported + ", entries walked=" + walked
                + ", distinct=" + distinct.size();
    }
}

Here's the rest of its output, after the access table above:

1. forgot accessOrder=true -> A was just read, still evicted: [B, C, D]
3a. insertion order: get() inside a loop is fine
3b. access order: get() inside a loop -> ConcurrentModificationException
3c. iterate over a copy of the keys instead -> [A, B, C]
4a. putFirst(Z), putLast(A) on insertion-order map -> [Z, B, C, A]
4b. pollFirstEntry -> Z=0, left [B, C, A]
4c. reversed() -> [A, C, B]
4d. reversed().put(Q) writes through -> [B, C, A, Q]
4e. putFirst(C) on access-order map -> [C, A, B]
4f. unmodifiableSequencedMap.putLast -> UnsupportedOperationException
2. equals() ignores order: true, but keySet().toString() differs: [A, B] vs [B, A]
6a. unsynchronised access-order map, 8 threads, get-then-put: failed threads=0, size()=120, entries walked=0, distinct=0
6b. Collections.synchronizedMap around it:            failed threads=0, size()=50, entries walked=50, distinct=50

Forgot the true. Output line 1 shows an "LRU" where A was read and then evicted anyway. Without accessOrder=true it's an insertion-order map with a size limit, which is FIFO. Cause: the two-argument constructor new LinkedHashMap<>(16, 0.75f) compiles happily. Fix: pass true as the third argument. The RecentLookups class does it once, in one place, which is the reason to wrap it.

get() inside a loop. Lines 3a to 3c. On an insertion-ordered map, calling get while iterating is fine. On an access-ordered one it throws:

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.LinkedHashMap$LinkedHashIterator.nextNode(LinkedHashMap.java:1023)
	at java.base/java.util.LinkedHashMap$LinkedKeyIterator.next(LinkedHashMap.java:1046)
	at Cme.main(Cme.java:2)

Cause: get reordered the list under the iterator. Fix: iterate over List.copyOf(map.keySet()), or collect what you need first and read after the loop. Be aware that 3c prints [A, B, C] because touching every key once, in order, puts them back in the same order.

Java 21's new methods. Lines 4a to 4f. putFirst and putLast reposition an entry on an insertion-ordered map, pollFirstEntry removes and returns the head, reversed() is a live view, and Collections.unmodifiableSequencedMap blocks writes. Two details from my run that I didn't expect. Writing through reversed() with a new key (4d) added it at the end of the original map, not the front, so Q came last in the underlying order. And on an access-ordered map, putFirst("C", 3) (4e) put C first, as asked, but it doesn't count as an access.

equals() ignores order. Line 5. Two maps with the same entries in different orders are equal, so don't use equals() to test that two catalogues are in the same shelf order. Compare List.copyOf(keySet()).

Threads. Lines 6a and 6b are the ones I spent the most time on. The class documentation says LinkedHashMap isn't synchronized, and that in access-ordered mode even get counts as a structural change. I expected a ConcurrentModificationException or a crash. What I got, across three runs of eight threads doing get-then-put on 120 keys through a capacity-50 cache:

6a. unsynchronised access-order map, 8 threads, get-then-put: failed threads=0, size()=127, entries walked=69, distinct=69
6a. unsynchronised access-order map, 8 threads, get-then-put: failed threads=0, size()=167, entries walked=0, distinct=0
6a. unsynchronised access-order map, 8 threads, get-then-put: failed threads=0, size()=118, entries walked=1, distinct=1

No exceptions anywhere. The cache broke: a map capped at 50 reports a size over a hundred, and walking it finds 69, 0, or 1 entries. Your logs would say nothing. Wrapping it in Collections.synchronizedMap gave size()=50, entries walked=50, distinct=50 in all three runs. If you iterate a synchronized map, hold its lock for the whole loop, as hammer() does with synchronized (map). Your numbers will differ from mine, since it's a race, but the shape should be the same.

When a hand-rolled LRU is not enough

• Share it across threads carefully. Collections.synchronizedMap(new RecentLookups<>(n)) is correct and fine for modest traffic, because every call takes one lock. If threads fight over it, use a purpose-built cache library with its own eviction policy and statistics. How to use ConcurrentHashMap explains why you can't just swap in a concurrent map here: it has no access order.
• Eviction by count isn't eviction by cost. My removeEldestEntry compares size() to a number. If values vary a lot in size, evict by total weight instead, and keep a running total outside the hook.
• Time-based expiry isn't in this class at all. If entries should disappear after a few minutes, you need timestamps or a cache library; a TTL cache is a separate tutorial.
• Initial sizing: the number you pass to new LinkedHashMap<>(n) is a table capacity, not an entry count, and a table only fills to three quarters before it grows. If you know you'll hold 10,000 entries, LinkedHashMap.newLinkedHashMap(10_000) (Java 19+) takes the entry count and does that arithmetic for you.
• Sorted or by-priority order is TreeMap or PriorityQueue, not this. And if you only need to de-duplicate while keeping order, a LinkedHashSet is simpler; see how to remove duplicates from a list in Java.
• Keys need equals() and hashCode(), the same as any hash map. Use immutable keys, like the ISBN string here; how to implement equals() and hashCode() has the rules.
• Version note: on Java 17 and earlier there is no SequencedMap, reversed(), putFirst() or firstEntry() on LinkedHashMap. Next in this series: how to iterate over a Map correctly and how to use PriorityQueue and TreeMap.

If it won't compile or behaves oddly

These are the messages I actually got.

A lint warning on the cache class.

src/main/java/com/example/library/RecentLookups.java:10: warning: [serial] serializable class RecentLookups has no definition of serialVersionUID

Cause: LinkedHashMap is Serializable, so subclasses are too. Fix: add private static final long serialVersionUID = 1L;, as the final class does.

Compiling for an older release. Building the whole project with javac --release 17:

src/main/java/com/example/library/Catalogue.java:8: error: cannot find symbol
import java.util.SequencedMap;
                ^
  symbol:   class SequencedMap
  location: package java.util

Cause: SequencedMap is Java 21. Fix: either stay on 21, or change Catalogue to use Map, replace reversed() with a manual reverse of the values list, and replace firstEntry() and lastEntry() with values().iterator().next() and a loop. RecentLookups alone compiled with --release 17.

ConcurrentModificationException from a loop that only reads. See "get() inside a loop" above.

An LRU that evicts the wrong thing. Check the constructor's third argument first, then check you aren't calling containsKey where you meant get.

A cache that's too big, or empty, under load. Shared access without a lock. See the threads section.

What you did

• Used new LinkedHashMap<>() when you need predictable iteration order that follows insertion, and remembered that re-putting a key doesn't move it.
• Moved an entry to the end with remove then put, and read both ends with the Java 21 sequenced methods.
• Built an LRU cache with new LinkedHashMap<>(16, 0.75f, true) plus removeEldestEntry, and checked eviction with 22 assertions.
• Learned that get, getOrDefault, put, putIfAbsent, computeIfAbsent, merge and replace count as use, and containsKey doesn't.
• Kept it out of loops that call get() and out of shared use without a lock.

Questions about LinkedHashMap people search for

What is the difference between HashMap and LinkedHashMap?
Both give you constant-time lookups on average. HashMap makes no promise about iteration order. LinkedHashMap adds a linked list through its entries so iteration follows insertion order, or last-access order if you ask for it, at the cost of a little extra memory per entry.

How do I make a LinkedHashMap an LRU cache?
Construct it with accessOrder set to true and override removeEldestEntry to return true when size() exceeds your limit. RecentLookups above is a complete version in thirty lines.

Does LinkedHashMap sort its keys?
No. It keeps insertion order, or access order, and never sorts. Use a TreeMap for sorted keys.

Is LinkedHashMap thread-safe?
No. It needs external synchronization, and in access-order mode even get modifies its structure, so unsynchronised readers can corrupt it. Wrap it with Collections.synchronizedMap or guard it with your own lock.

How do I get the first or last entry of a LinkedHashMap?
On Java 21 and later, call firstEntry() or lastEntry(); pollFirstEntry() removes and returns the first. On earlier versions, use entrySet().iterator().next() for the first and loop for the last.

References

• LinkedHashMap, Java SE 21 API (access-order methods, removeEldestEntry, synchronization note, newLinkedHashMap since 19), observed 2026-10-27.
• JEP 431: Sequenced Collections.