CKTIS / Java
LRU-Cache mit Zugriffsreihenfolge
Mit einer `LinkedHashMap` in Zugriffsreihenfolge wird beim Überschreiten der Größenbegrenzung der am längsten nicht verwendete Eintrag entfernt, nicht der zuerst eingefügte.
Version: Java SE 21
Syntax
new LinkedHashMap<K, V>(initialCapacity, loadFactor, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxEntries; } }LRU (least recently used) entfernt den Eintrag, dessen letzter Zugriff am längsten zurückliegt. FIFO (first in, first out) entfernt den zuerst eingefügten Eintrag: Ein Lesezugriff ändert die Reihenfolge beim Entfernen nicht. Für LRU zählt also der letzte Zugriff, für FIFO das Einfügen.
Bei LinkedHashMap aktiviert true als drittes Konstruktorargument die Zugriffsreihenfolge statt der standardmäßigen Einfügereihenfolge. Bei den im Beispiel gezeigten Operationen beginnt die Iteration beim Eintrag, dessen letzter Zugriff am längsten zurückliegt, und endet beim zuletzt verwendeten Eintrag. In Java SE 21 setzen putFirst und putLast einen Eintrag gezielt an den Anfang bzw. ans Ende, ohne einen Zugriff zu vermerken. Daher kann die Iterationsreihenfolge von der Reihenfolge der letzten Zugriffe abweichen. Ein erfolgreiches get oder ein put, das einen vorhandenen Eintrag aktualisiert, verschiebt ihn ans Ende, sofern er nicht schon dort steht. Ein get für einen fehlenden Schlüssel und containsKey ändern die Reihenfolge nicht.
Die Zugriffsreihenfolge allein begrenzt die Map nicht. Nachdem put einen neuen Eintrag eingefügt hat, liefert die überschriebene Methode removeEldestEntry bei size() > maxEntries den Wert true, und die Map entfernt den ersten Eintrag. initialCapacity ist die Anfangskapazität, keine Obergrenze für die Eintragszahl; Einträge laufen nach dieser Regel nicht zeitgesteuert ab.
LinkedHashMap ist nicht synchronisiert. Teilen sich mehrere Threads diesen Cache, müssen Zugriffe von außen synchronisiert werden, auch beim Lesen: get kann die Iterationsreihenfolge ändern.
Beispiele
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());
}
}Ergebnis
[B, A] [A, C]
Der Cache ist auf zwei Einträge begrenzt. `get("A")` verschiebt `A` hinter `B`, daher verdrängt das Einfügen von `C` den Eintrag `B`. FIFO würde `A` entfernen.
Zugehörige Lektionen
- Java · Lektion 40 · Mittlere Stufe · Version: 2