LRU-Cache in Java: Zugriffsreihenfolge mit LinkedHashMap

Ein LRU-Cache verdrängt den Eintrag, auf den am längsten nicht zugegriffen wurde. In Java verschiebt ein zugriffsgeordnetes LinkedHashMap benutzte Einträge ans zuletzt verwendete Ende. So lassen sich Treffer und Kosten in Anfragereihenfolge berechnen.

Die Programmers-Cache-Aufgabe vergleicht englische Städtenamen ohne Groß-/Kleinschreibung und vergibt Kosten 1 für einen Treffer und 5 für einen Cache-Miss. Die Kapazität reicht von 0 bis 30, mit höchstens 100.000 Anfragen. Dies sind Aufgabenkosten, keine gemessenen Datenbankantwortzeiten.

Ablauf

Kapazität null liefert sofort das Ergebnis. Sonst aktualisieren get/put die Zugriffsreihenfolge; bei Überlauf wird der am längsten unbenutzte Schlüssel verdrängt.

Reihenfolge beim Zugriff aktualisieren

Speichern Sie die vollständige Klasse als Solution.java. Sie benötigt Java 11 oder neuer; die lokale Ausführung des Ausgangsartikels kompilierte für Java 11 mit JDK 17. Die Methode setzt Eingaben innerhalb der Aufgabenbedingungen voraus.

import java.util.LinkedHashMap;
import java.util.Locale;

public class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) return 5 * cities.length;
        var cache = new LinkedHashMap<String, Boolean>(16, 0.75f, true);
        int cost = 0;
        for (String city : cities) {
            String key = city.toLowerCase(Locale.ROOT);
            cost += cache.get(key) == null ? 5 : 1;
            cache.put(key, Boolean.TRUE);
            if (cache.size() > cacheSize) {
                String oldest = cache.keySet().iterator().next();
                cache.remove(oldest);
            }
        }
        return cost;
    }
}

Das letzte Konstruktorargument true ist entscheidend. Anders als die standardmäßige Einfügereihenfolge aktualisiert ein zugriffsgeordnetes LinkedHashMap die Reihenfolge bei Zugriffen einschließlich get und put. Da diese Implementierung keine null-Werte speichert, erkennt get(key) == null einen Cache-Miss.

Bei Kapazitätsüberschreitung entfernen Sie den ersten Schlüssel der Iterationsreihenfolge: den am längsten unbenutzten Eintrag. Das unterscheidet sich von LFU, das nach Zugriffshäufigkeit auswählt. Locale.ROOT macht die englische Normalisierung unabhängig von der Standard-Locale des Rechners.

Warum ein Treffer die Verdrängung ändert

Bei Kapazität 2 kosten diese Anfragen insgesamt 21. Der Cache wird mit dem ältesten Eintrag zuerst dargestellt.

Anfrage	Ergebnis	Cache nach Anfrage	Gesamtkosten
Jeju	Cache-Miss	jeju	5
Pangyo	Cache-Miss	jeju, pangyo	10
Jeju	Treffer	pangyo, jeju	11
Seoul	Cache-Miss	jeju, seoul	16
Pangyo	Cache-Miss	seoul, pangyo	21

Aktualisiert die dritte Anfrage die Position von Jeju nicht, ändert sich die nächste Verdrängung. Kapazität 0 kann keinen Eintrag halten, daher liefert die Methode sofort 5 * cities.length. Auch Jeju und JEJU müssen zum selben Schlüssel normalisiert werden.

Bei durchschnittlich konstanten Hashoperationen benötigen M Anfragen mit Namenslänge L und Kapazität C einschließlich Normalisierung O(M×L) Zeit und O(C×L) Speicher. Beachten Sie die Aufgabengrenzen für L und C. Diese Implementierung belegt weder Verhalten bei Nebenläufigkeit noch gemessene Cacheleistung.

Für numerische Grenzen siehe Java-Skalarprodukte und int-Grenzen, für geordnete Zeichenkettenumformungen die ID-Normalisierung.