Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / Java

Predpomnilnik LRU z LinkedHashMap

V Java SE 21 ustvari predpomnilnik za dva vnosa in preveri, zakaj branje po ključu spremeni, kateri vnos se ob naslednjem vstavljanju odstrani.

Različica: Java SE 21

Sintaksa

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 LinkedHashMap(int, float, boolean) sprejme začetno kapaciteto razpršene tabele, faktor zasedenosti in način urejanja. Prva dva argumenta ne omejujeta števila vnosov. Pri true poteka iteracija od najdlje neuporabljenega do nazadnje uporabljenega vnosa: uspešen get(key) ali klic put(key, value) premakne ustrezni vnos na konec. Pri false velja vrstni red vstavljanja: branje obstoječega vnosa ali zamenjava njegove vrednosti z put ne spremeni njegovega mesta.

Za odstranjevanje najdlje neuporabljenega vnosa (LRU) v podrazredu prepiši zaščiteno metodo removeEldestEntry(Map.Entry<K,V> eldest). Ko put ali putAll doda nov vnos, vrnjena vrednost size() > 2 omogoči preslikavi, da odstrani prvi vnos, ko so v njej trije. Zamenjava vrednosti tega mehanizma ne sproži. Ne spreminjaj preslikave znotraj metode, če vrneš true: učinek te kombinacije ni določen.

put(K,V) vstavi ali zamenja vrednost, remove(Object) pa odstrani vnos po ključu. Obe metodi vrneta prejšnjo vrednost ali null, če vnosa ni bilo ali je bila njegova vrednost null. Preobremenjena metoda remove(Object,Object) odstrani vnos le, če se vrednost ujema, in vrne boolean. Operacije spreminjanja so v Map neobvezne, vendar jih LinkedHashMap podpira. size() prešteje pare ključ–vrednost.

keySet() vrne množico ključev, values() pa zbirko, ki lahko vsebuje podvojene vrednosti. To sta pogleda, povezana s preslikavo, in ne kopiji: iteracija sledi vrstnemu redu preslikave, ne da bi vnose označila kot pravkar uporabljene, odstranjevanje prek pogleda spremeni preslikavo, dodajanje pa ni podprto. Omejitev velja za število vnosov, ne za njihovo življenjsko dobo. Preslikava ni sinhronizirana; že get lahko spremeni vrstni red in razveljavi aktivni iterator.

Primeri

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

Rezultat

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

Brez branja vstavljanje `C` odstrani `A`. Po `get("A")` je vrstni red `[B, A]`, zato vstavljanje `C` odstrani `B`. Zadnji `remove("A")` vrne `1` in ostane samo `C`.

Povezane lekcije

  • Java · Lekcija 47 · Napredna · Različica: 2

Viri