CKTIS / Java
Ein LRU-Cache mit LinkedHashMap
Erstelle in Java SE 21 einen Cache für zwei Einträge und sieh, warum ein Lesezugriff bestimmt, welcher Eintrag beim nächsten Einfügen verdrängt wird.
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 erwartet LinkedHashMap(int, float, boolean) die Anfangskapazität der Hashtabelle, den Lastfaktor und den Ordnungsmodus. Die ersten beiden Argumente begrenzen nicht die Zahl der Einträge. Bei true reicht die Iterationsreihenfolge vom am längsten nicht verwendeten bis zum zuletzt verwendeten Eintrag: Ein erfolgreicher Aufruf von get(key) oder ein put(key, value) setzt den betroffenen Eintrag ans Ende. Bei false gilt die Einfügereihenfolge: Weder das Lesen noch das Ersetzen eines Werts mit put verschiebt einen vorhandenen Eintrag.
Für LRU („least recently used“) überschreibst du in einer Unterklasse die geschützte Methode removeEldestEntry(Map.Entry<K,V> eldest). Nachdem put oder putAll einen neuen Eintrag eingefügt hat, erlaubt size() > 2 der Map, beim dritten Eintrag den ersten zu entfernen. Eine Wertersetzung löst den Aufruf nicht aus. Ändere die Map nicht in der Methode, wenn du true zurückgibst; die Wirkung dieser Kombination ist nicht spezifiziert.
put(K,V) fügt einen Wert ein oder ersetzt ihn, remove(Object) löscht anhand des Schlüssels. Beide geben den vorherigen Wert zurück oder null, wenn die Zuordnung fehlte oder ihr Wert null war. Die Überladung remove(Object,Object) löscht nur bei passendem Wert und gibt einen boolean zurück. Änderungsoperationen sind in Map optional; LinkedHashMap unterstützt sie. size() zählt die Schlüssel-Wert-Zuordnungen.
keySet() liefert eine Menge von Schlüsseln, values() eine Collection, die doppelte Werte enthalten kann. Beide sind direkt mit der Map verbundene Ansichten, keine Kopien: Beim Iterieren gilt die Reihenfolge der Map, ohne Einträge als benutzt zu markieren. Entfernen über eine Ansicht ändert die Map, Hinzufügen wird nicht unterstützt. Begrenzt ist die Anzahl der Einträge, nicht ihre Lebensdauer. Die Map ist nicht synchronisiert; schon get kann die Reihenfolge ändern und einen aktiven Iterator ungültig machen.
Beispiele
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);
}
}Ergebnis
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
Ohne Lesezugriff verdrängt das Einfügen von `C` den Eintrag `A`. Nach `get("A")` lautet die Reihenfolge `[B, A]`; daher verdrängt `C` den Eintrag `B`. Das abschließende `remove("A")` gibt `1` zurück; nur `C` bleibt.
Zugehörige Lektionen
- Java · Lektion 47 · Fortgeschritten · Version: 2