> ## Content Index > Fetch the complete content index at: https://www.ggorantala.dev/llms.txt > Use this file to discover other available public pages before exploring further. # How to Use LinkedHashMap in Java: Order and an LRU Cache - URL: https://www.ggorantala.dev/how-to-use-linkedhashmap-java/ - Published: 2026-01-23T06:18:00.000Z - Updated: 2026-10-31T06:31:53.000Z - Description: How to use LinkedHashMap in Java 21: keep insertion order, move entries, and build a small LRU cache with access order, on a library catalogue with 22 checks. - Author: Gopi Gorantala - Tags: how-to-tutorials, java-collections, java-tutorials ## 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: ```log 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 | Tool | Version I used | Check it with | | ----------------- | -------------------------------- | -------------- | | JDK | OpenJDK 21.0.12.1 (Ubuntu build) | java -version | | javac | 21.0.12.1 | javac -version | | Gradle (optional) | 8.14.3, Kotlin DSL | gradle -v | | Container runtime | none needed | | Java 21 matters for a handful of methods. `reversed()`, `putFirst()`, `putLast()`, `firstEntry()` and friends arrived with sequenced collections in Java 21 ([JEP 431](https://openjdk.org/jeps/431?ref=ggorantala.dev)). 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. ```bash mkdir library-catalogue && cd library-catalogue mkdir -p src/main/java/com/example/library ``` The finished layout: ```log 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`: ```kotlin plugins { application } java { sourceCompatibility = JavaVersion.VERSION_21 targetCompatibility = JavaVersion.VERSION_21 } repositories { mavenCentral() } application { mainClass.set("com.example.library.Main") } tasks.register("checks") { classpath = sourceSets["main"].runtimeClasspath mainClass.set("com.example.library.Checks") } ``` `settings.gradle.kts`: ```kotlin 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`: ```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](https://ggorantala.dev/how-to-use-java-records/?ref=ggorantala.dev) 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:** ```bash 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`: ```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 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 find(String isbn) { return Optional.ofNullable(shelf.get(isbn)); } /** Shelf order, oldest first. A copy, so callers can't reorder our shelf. */ public List inShelfOrder() { return List.copyOf(shelf.values()); } /** Java 21: the same list, newest first, without copying into a reversed list by hand. */ public List newestFirst() { return new ArrayList<>(shelf.reversed().values()); } public Optional oldest() { return Optional.ofNullable(shelf.firstEntry()).map(Map.Entry::getValue); } public Optional 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` 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](https://ggorantala.dev/how-to-create-immutable-class-java/?ref=ggorantala.dev). **Checkpoint:** ```bash 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`: ```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 extends LinkedHashMap { 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 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:** ```bash 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`: ```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 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. ```bash 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": ```bash java -cp out com.example.library.Traps ``` ```log 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`: ```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 isbns(List 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 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 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 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 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(0); zeroCap = false; } catch (IllegalArgumentException e) { zeroCap = true; } check("capacity 0 is rejected", zeroCap); RecentLookups 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 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 linked = new LinkedHashMap<>(); linked.put("b", 1); linked.put("a", 2); Map 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 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); } } } ``` ```bash java -cp out com.example.library.Checks ``` ```log 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](#when-a-hand-rolled-lru-is-not-enough), 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`: ```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 three(boolean accessOrder) { LinkedHashMap 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 fifo = new LinkedHashMap<>(16, 0.75f) { @Override protected boolean removeEldestEntry(Map.Entry 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 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 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 ordered = three(false); for (String k : ordered.keySet()) { ordered.get(k); } System.out.println("3a. insertion order: get() inside a loop is fine"); LinkedHashMap 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 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 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 lru = three(true); lru.putFirst("C", 3); System.out.println("4e. putFirst(C) on access-order map -> " + lru.keySet()); SequencedMap view = Collections.unmodifiableSequencedMap(m); try { view.putLast("X", 1); } catch (UnsupportedOperationException e) { System.out.println("4f. unmodifiableSequencedMap.putLast -> UnsupportedOperationException"); } } static void equalsIgnoresOrder() { LinkedHashMap a = new LinkedHashMap<>(); a.put("A", 1); a.put("B", 2); LinkedHashMap 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 safe = Collections.synchronizedMap(new RecentLookups<>(50)); System.out.println("6b. Collections.synchronizedMap around it: " + hammer(safe)); } static String hammer(Map 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 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: ```log 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: ```log 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: ```log 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](https://ggorantala.dev/how-to-use-concurrenthashmap-java/?ref=ggorantala.dev) 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](https://ggorantala.dev/how-to-remove-duplicates-from-list-java/?ref=ggorantala.dev). - **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()](https://ggorantala.dev/how-to-implement-equals-hashcode-java/?ref=ggorantala.dev) 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](https://ggorantala.dev/how-to-iterate-map-java/?ref=ggorantala.dev) and [how to use PriorityQueue and TreeMap](https://ggorantala.dev/how-to-use-priorityqueue-treemap-java/?ref=ggorantala.dev). ## If it won't compile or behaves oddly These are the messages I actually got. **A lint warning on the cache class.** ```log 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`: ```log 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](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/LinkedHashMap.html?ref=ggorantala.dev) (access-order methods, `removeEldestEntry`, synchronization note, `newLinkedHashMap` since 19), observed 2026-10-27. - [JEP 431: Sequenced Collections](https://openjdk.org/jeps/431?ref=ggorantala.dev).