Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / Java

An LRU cache with LinkedHashMap

Build a two-entry cache in Java SE 21 and see why reading a key changes which entry will be evicted on the next insertion.

Version: Java SE 21

Syntax

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
@Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest)
V put(K key, V value)
V get(Object key)
V remove(Object key)
boolean remove(Object key, Object value)
Collection<V> values()
int size()
Set<K> keySet()

In Java SE 21, LinkedHashMap(int, float, boolean) takes an initial hash-table capacity, a load factor, and an ordering mode. The first two arguments do not set an entry limit. With true, iteration goes from least to most recently accessed: a successful get(key) or a put(key, value) moves the affected entry to the end. With false, iteration follows insertion order: reading an existing entry or replacing its value with put does not move it.

For LRU (least recently used) eviction, override the protected removeEldestEntry(Map.Entry<K,V> eldest) method in a subclass. After put or putAll adds a new entry, returning size() > 2 lets the map remove its first entry when the count reaches three. Replacing a value does not trigger this hook. Do not modify the map inside the hook and also return true; the effect of doing both is unspecified.

put(K,V) inserts or replaces a value, and remove(Object) deletes by key. Both return the previous value, or null if the mapping was absent or its value was null. The remove(Object,Object) overload removes a mapping only if its value matches and returns a boolean. Mutation is optional in Map but supported by LinkedHashMap. size() counts key–value mappings.

keySet() returns a set of keys; values() returns a collection that can include duplicates. Both are live views, not copies: iteration follows the map’s order without refreshing entries, removal through a view changes the map, and additions are unsupported. The limit is on entry count, not on how long entries live. The map is not synchronized; even get can reorder entries and invalidate an active iterator.

Examples

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

public class Main {
    private static final class LruCache<K, V> extends LinkedHashMap<K, V> {
        private static final int MAX_ENTRIES = 2;

        LruCache() {
            super(4, 0.75f, true);
        }

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

    private static void show(String label, Map<String, Integer> cache) {
        System.out.println(label + ": keys=" + cache.keySet()
                + ", values=" + cache.values() + ", size=" + cache.size());
    }

    public static void main(String[] args) {
        Map<String, Integer> noRead = new LruCache<>();
        noRead.put("A", 1);
        noRead.put("B", 2);
        noRead.put("C", 3);
        show("No read, after put(C)", noRead);

        Map<String, Integer> withRead = new LruCache<>();
        withRead.put("A", 1);
        withRead.put("B", 2);
        System.out.println("get(A) = " + withRead.get("A"));
        show("With read, before put(C)", withRead);
        withRead.put("C", 3);
        show("With read, after put(C)", withRead);
        System.out.println("remove(A) = " + withRead.remove("A"));
        show("After remove(A)", withRead);
    }
}

Result

No read, after put(C): keys=[B, C], values=[2, 3], size=2
get(A) = 1
With read, before put(C): keys=[B, A], values=[2, 1], size=2
With read, after put(C): keys=[A, C], values=[1, 3], size=2
remove(A) = 1
After remove(A): keys=[C], values=[3], size=1

Without a read, inserting `C` evicts `A`. After `get("A")`, the order is `[B, A]`, so inserting `C` evicts `B`. The final `remove("A")` returns `1`, leaving only `C`.

Related lessons

  • Java · Lesson 47 · Advanced · Version: 2

Sources