База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / Java

LRU кеш с LinkedHashMap

Създай кеш за два записа в Java SE 21 и виж защо прочитането на запис по ключ променя кой запис ще отпадне при следващото добавяне.

Версия: Java SE 21

Синтаксис

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

В Java SE 21 LinkedHashMap(int, float, boolean) приема начален капацитет на хеш таблицата, коефициент на запълване и режим на подреждане. Първите два аргумента не ограничават броя на записите. При true обхождането е от най-отдавна използвания към последно използвания запис: успешно извикване на get(key) или извикване на put(key, value) премества съответния запис в края. При false се запазва редът на добавяне: прочитането на съществуващ запис или замяната на стойността му чрез put не променя позицията му.

За да премахваш най-отдавна използвания запис (LRU), предефинирай защитения метод removeEldestEntry(Map.Entry<K,V> eldest) в подклас. След като put или putAll добави нов запис, връщането на size() > 2 позволява на речника да премахне първия запис, щом записите станат три. Замяната на стойност не задейства този механизъм. Не променяй речника в метода, ако връщаш true: ефектът от тази комбинация не е специфициран.

put(K,V) добавя или заменя стойност, а remove(Object) премахва запис по ключ. И двата метода връщат предишната стойност или null, ако не е имало запис или стойността му е била null. Претовареният метод remove(Object,Object) премахва записа само при съвпадение на стойността и връща boolean. Операциите за промяна не са задължителни в Map, но LinkedHashMap ги поддържа. size() брои двойките ключ–стойност.

keySet() връща множество от ключове, а values() — колекция, която може да съдържа повтарящи се стойности. Това са изгледи, свързани с речника, а не копия: обхождането следва реда му, без да отбелязва записите като току-що използвани, премахването през изглед променя речника, а добавянето не се поддържа. Ограничението е за броя записи, не за срока им на съхранение. Речникът не е синхронизиран; дори get може да промени реда и да направи активен итератор невалиден.

Примери

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

Резултат

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

Без прочитане добавянето на `C` премахва `A`. След `get("A")` редът е `[B, A]`, затова добавянето на `C` премахва `B`. Последното `remove("A")` връща `1` и остава само `C`.

Свързани уроци

  • Java · Урок 47 · Напреднало · Версия: 2

Източници