Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / Java

LRU cache through access order

Use an access-ordered `LinkedHashMap` to evict the least recently accessed entry when the cache exceeds its size limit, rather than evicting the first entry inserted.

Version: Java SE 21

Syntax

new LinkedHashMap<K, V>(initialCapacity, loadFactor, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxEntries; } }

An LRU cache through access order evicts the entry whose last access was longest ago. FIFO (first in, first out) evicts the earliest inserted entry: reading it does not change which entry leaves next. LRU (least recently used) therefore tracks last access, while FIFO tracks insertion.

In LinkedHashMap, the third constructor argument, true, selects access order instead of the default insertion order. With the operations shown in the example, iteration runs from least recently accessed to most recently accessed. In Java SE 21, putFirst and putLast explicitly place an entry at the beginning or end without recording an access, so iteration order can differ from the order of last access. A get hit or a put that updates an existing entry moves that entry to the end if it is not already there. A get miss and containsKey leave the order unchanged.

Access order alone does not bound the map. After put inserts a new entry, the overridden removeEldestEntry returns true if size() > maxEntries, and the map removes its first entry. initialCapacity is a starting capacity, not an entry limit; this policy does not expire entries by time.

LinkedHashMap is not synchronized. If multiple threads share this cache, synchronize access externally, including reads: get can change iteration order.

Examples

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

public class LruDemo {
    public static void main(String[] args) {
        int maxEntries = 2;
        Map<String, Integer> cache = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
                return size() > maxEntries;
            }
        };

        cache.put("A", 1);
        cache.put("B", 2);
        cache.get("A");
        System.out.println(cache.keySet());

        cache.put("C", 3);
        System.out.println(cache.keySet());
    }
}

Result

[B, A]
[A, C]

The limit is two entries. `get("A")` moves `A` behind `B`, so inserting `C` evicts `B`. FIFO would evict `A`.

Related lessons

  • Java · Lesson 40 · Intermediate · Version: 2

Sources