Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / Java

Predmemorija LRU s LinkedHashMap

Izradi predmemoriju za dva unosa u Java SE 21 i provjeri zašto čitanje po ključu mijenja unos koji će se izbaciti pri sljedećem umetanju.

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

U Java SE 21 LinkedHashMap(int, float, boolean) prima početni kapacitet tablice raspršivanja, faktor popunjenosti i način određivanja redoslijeda. Prva dva argumenta ne ograničavaju broj unosa. Uz true iteracija ide od najdavnije korištenog do posljednjeg korištenog unosa: uspješan get(key) ili poziv put(key, value) premješta odgovarajući unos na kraj. Uz false vrijedi redoslijed umetanja: čitanje postojećeg unosa ili zamjena njegove vrijednosti pomoću put ne mijenja njegov položaj.

Za izbacivanje najdavnije korištenog unosa (LRU) u podklasi nadjačaj zaštićenu metodu removeEldestEntry(Map.Entry<K,V> eldest). Nakon što put ili putAll doda novi unos, povrat vrijednosti size() > 2 omogućuje mapi da ukloni prvi unos kad ih ima tri. Zamjena vrijednosti ne pokreće taj mehanizam. Nemoj mijenjati mapu unutar metode ako vraćaš true: učinak te kombinacije nije specificiran.

put(K,V) umeće ili zamjenjuje vrijednost, a remove(Object) uklanja unos prema ključu. Obje metode vraćaju prethodnu vrijednost ili null ako unosa nije bilo ili mu je vrijednost bila null. Preopterećena metoda remove(Object,Object) uklanja unos samo ako se vrijednost podudara i vraća boolean. Operacije izmjene nisu obvezne u Map, ali ih LinkedHashMap podržava. size() broji parove ključ–vrijednost.

keySet() vraća skup ključeva, a values() kolekciju koja može sadržavati ponovljene vrijednosti. To su pogledi povezani s mapom, a ne kopije: iteracija slijedi redoslijed mape bez označavanja unosa kao upravo korištenih, uklanjanje putem pogleda mijenja mapu, a dodavanje nije podržano. Ograničenje se odnosi na broj unosa, ne na njihov vijek trajanja. Mapa nije sinkronizirana; čak i get može promijeniti redoslijed i učiniti aktivni iterator nevaljanim.

Primjeri

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

Bez čitanja umetanje `C` izbacuje `A`. Nakon `get("A")` redoslijed je `[B, A]`, pa umetanje `C` izbacuje `B`. Završni `remove("A")` vraća `1` i ostaje samo `C`.

Povezane lekcije

  • Java · Lekcija 47 · Napredno · Verzija: 2

Izvori