Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / Java

Pamięć podręczna LRU z LinkedHashMap

Zbuduj w Java SE 21 pamięć podręczną na dwa wpisy i sprawdź, dlaczego odczyt klucza zmienia to, który wpis zostanie usunięty jako następny.

Wersja: Java SE 21

Składnia

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
@Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest)
V put(K key, V value)
V get(Object key)
V remove(Object key)
boolean remove(Object key, Object value)
Collection<V> values()
int size()
Set<K> keySet()

W Java SE 21 konstruktor LinkedHashMap(int, float, boolean) przyjmuje początkową pojemność tablicy haszującej, współczynnik zapełnienia i tryb porządkowania. Pierwsze dwa argumenty nie wyznaczają limitu wpisów. Przy true iteracja przebiega od najdawniej do ostatnio używanego wpisu: get(key) dla istniejącego klucza i put(key, value) przesuwają dany wpis na koniec. Przy false obowiązuje kolejność wstawiania: odczyt ani zastąpienie wartości przez put nie zmienia pozycji istniejącego wpisu.

Aby uzyskać LRU, czyli usuwać najdawniej używany wpis, przesłoń w podklasie chronioną metodę removeEldestEntry(Map.Entry<K,V> eldest). Po dodaniu nowego wpisu przez put lub putAll metoda zwracająca size() > 2 pozwala mapie usunąć pierwszy wpis, gdy jest ich już trzy. Zastąpienie wartości nie uruchamia tego mechanizmu. Nie modyfikuj mapy w tej metodzie, jeśli zwracasz true: skutek takiego połączenia jest nieokreślony.

put(K,V) wstawia lub zastępuje wartość, a remove(Object) usuwa wpis według klucza. Obie metody zwracają poprzednią wartość lub null, jeśli wpisu nie było albo jego wartością było null. Przeciążenie remove(Object,Object) usuwa wpis tylko wtedy, gdy wartość pasuje, i zwraca boolean. Modyfikacje są opcjonalne w Map, ale LinkedHashMap je obsługuje. size() liczy pary klucz–wartość.

keySet() zwraca zbiór kluczy, a values() kolekcję wartości, w której mogą występować powtórzenia. To widoki powiązane z mapą, nie kopie: iterują w jej kolejności bez odświeżania wpisów, usuwanie przez widok zmienia mapę, a dodawanie nie jest obsługiwane. Limit dotyczy liczby wpisów, nie czasu ich przechowywania. Mapa nie jest synchronizowana; nawet get może zmienić kolejność i unieważnić aktywny iterator.

Przykłady

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

public class Main {
    private static final class LruCache<K, V> extends LinkedHashMap<K, V> {
        private static final int MAX_ENTRIES = 2;

        LruCache() {
            super(4, 0.75f, true);
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > MAX_ENTRIES;
        }
    }

    private static void show(String label, Map<String, Integer> cache) {
        System.out.println(label + ": keys=" + cache.keySet()
                + ", values=" + cache.values() + ", size=" + cache.size());
    }

    public static void main(String[] args) {
        Map<String, Integer> noRead = new LruCache<>();
        noRead.put("A", 1);
        noRead.put("B", 2);
        noRead.put("C", 3);
        show("No read, after put(C)", noRead);

        Map<String, Integer> withRead = new LruCache<>();
        withRead.put("A", 1);
        withRead.put("B", 2);
        System.out.println("get(A) = " + withRead.get("A"));
        show("With read, before put(C)", withRead);
        withRead.put("C", 3);
        show("With read, after put(C)", withRead);
        System.out.println("remove(A) = " + withRead.remove("A"));
        show("After remove(A)", withRead);
    }
}

Wynik

No read, after put(C): keys=[B, C], values=[2, 3], size=2
get(A) = 1
With read, before put(C): keys=[B, A], values=[2, 1], size=2
With read, after put(C): keys=[A, C], values=[1, 3], size=2
remove(A) = 1
After remove(A): keys=[C], values=[3], size=1

Bez odczytu wstawienie `C` usuwa `A`. Po `get("A")` kolejność to `[B, A]`, więc wstawienie `C` usuwa `B`. Końcowe `remove("A")` zwraca `1`; pozostaje tylko `C`.

Powiązane lekcje

  • Java · Lekcja 47 · Zaawansowany · Wersja: 2

Źródła