Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / Java

Vyrovnávacia pamäť LRU s LinkedHashMap

Vytvorte v Java SE 21 vyrovnávaciu pamäť pre dve položky a zistite, prečo načítanie kľúča zmení položku vyradenú pri ďalšom vložení.

Verzia: Java SE 21

Syntax

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

V Java SE 21 prijíma LinkedHashMap(int, float, boolean) počiatočnú kapacitu hašovacej tabuľky, faktor zaplnenia a režim usporiadania. Prvé dva argumenty neobmedzujú počet položiek. Pri true prebieha iterácia od najdlhšie nepoužitej položky po naposledy použitú: úspešné get(key) alebo volanie put(key, value) presunie príslušnú položku na koniec. Pri false platí poradie vloženia: načítanie existujúcej položky ani nahradenie jej hodnoty pomocou put nemení jej pozíciu.

Ak chcete vyraďovať najdlhšie nepoužitú položku (LRU), prepíšte v podtriede chránenú metódu removeEldestEntry(Map.Entry<K,V> eldest). Po pridaní novej položky cez put alebo putAll umožní návrat hodnoty size() > 2 mape odstrániť prvú položku, len čo sú v nej tri. Nahradenie hodnoty tento mechanizmus nespustí. Nemeňte mapu vnútri metódy, ak vraciate true: účinok tejto kombinácie nie je špecifikovaný.

put(K,V) vloží alebo nahradí hodnotu a remove(Object) odstráni položku podľa kľúča. Obe metódy vracajú predchádzajúcu hodnotu alebo null, ak položka neexistovala alebo mala hodnotu null. Preťažená metóda remove(Object,Object) odstráni položku len pri zhode hodnoty a vráti boolean. Operácie meniace mapu sú v Map voliteľné, ale LinkedHashMap ich podporuje. size() počíta dvojice kľúč–hodnota.

keySet() vracia množinu kľúčov; values() vracia kolekciu, ktorá môže obsahovať rovnaké hodnoty viackrát. Sú to pohľady prepojené s mapou, nie kópie: iterácia dodržiava poradie mapy bez toho, aby označila položky za práve použité, odstránenie cez pohľad mení mapu a pridávanie nie je podporované. Limit sa týka počtu položiek, nie ich životnosti. Mapa nie je synchronizovaná; aj get môže zmeniť poradie a zneplatniť aktívny iterátor.

Príklady

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

Výsledok

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 načítania vyradí vloženie `C` položku `A`. Po `get("A")` je poradie `[B, A]`, takže vloženie `C` vyradí `B`. Posledné `remove("A")` vráti `1` a zostane len `C`.

Súvisiace lekcie

  • Java · Lekcia 47 · Pokročilá · Verzia: 2

Zdroje