WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / Java

LinkedHashMap: Eintragsreihenfolge und LRU-Cache

LinkedHashMap aus java.util speichert Schlüssel-Wert-Zuordnungen. Das Beispiel zeigt einen LRU-Cache, der auf zwei Einträge begrenzt ist.

Version: Java SE 21; repository runtime, production runtime not attested

Syntax

new LinkedHashMap<K, V>(initialCapacity, loadFactor, accessOrder)
protected boolean removeEldestEntry(Map.Entry<K, V> eldest)

java.util.LinkedHashMap verwendet standardmäßig die Einfügungsreihenfolge und sortiert die Schlüssel nicht. LinkedHashMap(int,float,boolean) erwartet Anfangskapazität, Lastfaktor und accessOrder: false wählt die Einfügungsreihenfolge, true die Zugriffsreihenfolge, vom Eintrag mit dem am längsten zurückliegenden Zugriff bis zum zuletzt aufgerufenen Eintrag. Die Kapazität begrenzt nicht die Anzahl der Einträge. In Java 21 lässt sich ein vorhandener Eintrag mit putFirst gezielt an den Anfang und mit putLast ans Ende verschieben, auch im Modus mit Einfügungsreihenfolge.

Ein erfolgreiches get verschiebt den Eintrag im Zugriffsmodus ans Ende; containsKey ändert die Reihenfolge nicht. So lässt sich ein „LRU access-order cache“ umsetzen: Der am längsten nicht verwendete Eintrag wird entfernt.

Überschreibe LinkedHashMap.removeEldestEntry so, dass size() > limit zurückgegeben wird. Nachdem put oder putAll einen neuen Eintrag hinzugefügt hat, führt der Rückgabewert true dazu, dass der erste Eintrag in der aktuellen Reihenfolge entfernt wird; standardmäßig gibt die Methode false zurück.

Die Klasse ist nicht synchronisiert. Greifen mehrere Threads gleichzeitig auf die Map zu und verändert mindestens einer davon ihre Struktur, ist eine externe Synchronisierung erforderlich. Im Modus mit Zugriffsreihenfolge kann selbst get als strukturelle Änderung gelten. Eine sicher veröffentlichte Map mit Einfügungsreihenfolge lässt sich gemeinsam rein lesend nutzen, ohne jeden Zugriff zu synchronisieren. Geltungsbereich: Java SE 21; die Produktionslaufzeit wurde nicht bestätigt.

Beispiele

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

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

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

Ergebnis

[A, B]
[B, A]
{A=1, C=3}

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen