LRU-Cache

Kurz: Ein LRU-Cache („Least Recently Used”) speichert nur eine begrenzte Zahl Einträge und wirft bei Platzmangel den am längsten unbenutzten Eintrag hinaus.

Genauer: Die Idee: Wer kürzlich gebraucht wurde, wird wahrscheinlich bald wieder gebraucht. Für schnelle Operationen kombiniert man eine Hash-Tabelle (Zugriff in O(1)) mit einer doppelt verketteten Liste (Reihenfolge der Nutzung).

Im Detail

• Lesen: Eintrag über die Hash-Tabelle finden und in der Liste an den Anfang („zuletzt benutzt”) schieben.
• Schreiben: Neuer Eintrag kommt an den Anfang. Ist die Kapazität überschritten, wird das Listenende entfernt.
• Alternativen: LFU (am seltensten benutzt), FIFO (am ältesten), zufälliges Verdrängen.
• Einsatz: Browser-Cache, Datenbank-Puffer, Betriebssystem-Seitencache, lru_cache in Python.
• Fallstrick: Ein einmaliger großer Scan kann den ganzen Cache verdrängen („Cache-Verschmutzung”).

Siehe auch: Caching-Strategien und Cache-Invalidierung