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

CKTIS / Java

Predpomnilnik LRU z vrstnim redom dostopov

Uporabi `LinkedHashMap` v vrstnem redu dostopov, da se ob prekoračitvi omejitve odstrani najdlje neuporabljen vnos, ne pa vnos, ki je bil vstavljen prvi.

Različica: Java SE 21

Sintaksa

new LinkedHashMap<K, V>(initialCapacity, loadFactor, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxEntries; } }

LRU (least recently used) odstrani vnos, od zadnjega dostopa do katerega je minilo največ časa. FIFO (first in, first out) odstrani najprej vstavljeni vnos: branje tega vnosa ne spremeni vrstnega reda odstranjevanja. LRU torej upošteva zadnji dostop, FIFO pa vstavitev.

V LinkedHashMap tretji argument konstruktorja, true, namesto privzetega vrstnega reda vstavljanja vključi vrstni red dostopov. Pri operacijah iz primera iteracija teče od najdlje neuporabljenega do nazadnje uporabljenega vnosa. V Java SE 21 metodi putFirst in putLast postavita vnos neposredno na začetek oziroma na konec, ne da bi zabeležili dostop. Vrstni red iteracije se zato lahko razlikuje od vrstnega reda zadnjih dostopov. get za obstoječi ključ ali put, ki posodobi obstoječi vnos, premakne ta vnos na konec, če še ni tam. get za manjkajoči ključ in containsKey vrstnega reda ne spremenita.

Vrstni red dostopov sam po sebi ne omejuje velikosti preslikave. Ko put vstavi nov vnos, prepisana metoda removeEldestEntry vrne true, če velja size() > maxEntries, preslikava pa odstrani prvi vnos. initialCapacity je začetna zmogljivost, ne največje število vnosov; vnosi po tem pravilu ne potečejo po določenem času.

LinkedHashMap ni sinhroniziran. Če si ta predpomnilnik deli več niti, dostope sinhroniziraj od zunaj, tudi pri branju: get lahko spremeni vrstni red iteracije.

Primeri

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

Rezultat

[B, A]
[A, C]

Omejitev sta dva vnosa. `get("A")` premakne `A` za `B`, zato vstavljanje `C` odstrani `B`. FIFO bi odstranil `A`.

Povezane lekcije

  • Java · Lekcija 40 · Srednja · Različica: 2

Viri