CKTIS / Java
Pamięć podręczna LRU z kolejnością dostępu
Użyj `LinkedHashMap` w trybie kolejności dostępu, aby po przekroczeniu limitu usuwać wpis używany najdawniej, a nie wpis dodany najwcześniej.
Wersja: Java SE 21
Składnia
new LinkedHashMap<K, V>(initialCapacity, loadFactor, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxEntries; } }LRU (least recently used) usuwa wpis, do którego najdawniej uzyskano dostęp. FIFO (first in, first out) usuwa wpis dodany najwcześniej: jego odczyt nie zmienia kolejności usuwania. LRU bierze więc pod uwagę ostatni dostęp, a FIFO moment dodania.
W LinkedHashMap trzeci argument konstruktora, true, włącza kolejność dostępu zamiast domyślnej kolejności wstawiania. Przy operacjach pokazanych w przykładzie iteracja przebiega od wpisu używanego najdawniej do używanego ostatnio. W Java SE 21 metody putFirst i putLast umieszczają wpis odpowiednio na początku lub na końcu bez odnotowania dostępu, więc kolejność iteracji może nie odzwierciedlać kolejności ostatnich dostępów. get dla istniejącego klucza i put aktualizujące istniejący wpis przesuwają go na koniec, jeśli jeszcze tam nie jest. get dla nieobecnego klucza i containsKey nie zmieniają kolejności.
Sama kolejność dostępu nie ogranicza rozmiaru mapy. Przy wstawieniu nowego wpisu przez put nadpisana metoda removeEldestEntry zwraca true, gdy size() > maxEntries, a mapa usuwa pierwszy wpis. initialCapacity to pojemność początkowa, a nie limit wpisów; ta reguła nie ustala czasu ich ważności.
LinkedHashMap nie jest synchronizowana. Jeśli wiele wątków współdzieli tę pamięć podręczną, synchronizuj dostęp z zewnątrz, także przy odczytach: get może zmienić kolejność iteracji.
Przykłady
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());
}
}Wynik
[B, A] [A, C]
Limit wynosi dwa wpisy. `get("A")` przesuwa `A` za `B`, więc dodanie `C` usuwa `B`. Przy FIFO usunięto by `A`.
Powiązane lekcje
- Java · Lekcja 40 · Średniozaawansowany · Wersja: 2