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