Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / Java

Una cache LRU con LinkedHashMap

Crea una cache da due voci in Java SE 21 e osserva perché leggere una chiave cambia la voce che verrà rimossa all’inserimento successivo.

Versione: Java SE 21

Sintassi

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()

In Java SE 21, LinkedHashMap(int, float, boolean) accetta la capacità iniziale della tabella hash, il fattore di carico e la modalità di ordinamento. I primi due argomenti non impongono un limite al numero di voci. Con true, l’iterazione va dalla voce usata meno di recente a quella usata più di recente: una chiamata a get(key) che trova la chiave o una chiamata a put(key, value) sposta la voce interessata in fondo. Con false, vale l’ordine di inserimento: leggere una voce esistente o sostituirne il valore con put non la sposta.

Per rimuovere la voce usata meno di recente (LRU), ridefinisci il metodo protetto removeEldestEntry(Map.Entry<K,V> eldest) in una sottoclasse. Dopo che put o putAll ha aggiunto una nuova voce, restituire size() > 2 permette alla mappa di eliminare la prima voce quando ne contiene tre. Sostituire un valore non attiva questo meccanismo. Non modificare la mappa nel metodo se restituisci true: l’effetto delle due azioni insieme non è specificato.

put(K,V) inserisce o sostituisce un valore, mentre remove(Object) rimuove in base alla chiave. Entrambi restituiscono il valore precedente, oppure null se l’associazione mancava o se il suo valore era null. L’overload remove(Object,Object) rimuove l’associazione solo se il valore corrisponde e restituisce un boolean. Le modifiche sono facoltative in Map, ma LinkedHashMap le supporta. size() conta le associazioni chiave-valore.

keySet() restituisce un insieme di chiavi; values() restituisce una collezione che può contenere duplicati. Sono viste collegate alla mappa, non copie: l’iterazione segue l’ordine della mappa senza aggiornare l’ordine d’uso, la rimozione tramite una vista modifica la mappa e le aggiunte non sono supportate. Il limite riguarda il numero di voci, non la loro durata. La mappa non è sincronizzata: anche get può cambiare l’ordine e invalidare un iteratore attivo.

Esempi

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);
    }
}

Risultato

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

Senza lettura, inserire `C` elimina `A`. Dopo `get("A")`, l’ordine è `[B, A]`, quindi inserire `C` elimina `B`. L’ultima chiamata a `remove("A")` restituisce `1` e rimane solo `C`.

Lezioni correlate

  • Java · Lezione 47 · Avanzato · Versione: 2

Fonti