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

CKTIS / Java

LRU кеш с подредба по достъп

Използвай `LinkedHashMap` с подредба по достъп, за да премахваш при надхвърляне на лимита записа, до който най-отдавна е имало достъп, а не първия добавен запис.

Версия: Java SE 21

Синтаксис

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

LRU (least recently used) премахва записа, до който най-отдавна е имало достъп. FIFO (first in, first out) премахва първия добавен запис: прочитането му не променя реда на премахване. Затова LRU се определя от последния достъп, а FIFO — от добавянето.

В LinkedHashMap третият аргумент на конструктора, true, включва подредба по достъп вместо стандартната подредба по добавяне. При операциите от примера обхождането започва от записа, до който най-отдавна е имало достъп, и завършва с последно достъпения запис. В Java SE 21 методите putFirst и putLast поставят запис съответно в началото или в края, без да отчитат достъп. Затова редът на обхождане може да се различава от реда на последните достъпи. get за наличен ключ или put, който обновява съществуващ запис, премества този запис накрая, ако вече не е там. get за липсващ ключ и containsKey не променят подредбата.

Подредбата по достъп сама по себе си не ограничава размера на речника. След като put добави нов запис, предефинираният метод removeEldestEntry връща true, ако size() > maxEntries, и речникът премахва първия запис. initialCapacity е началният капацитет, а не ограничение за броя на записите; това правило не задава срок на валидност.

LinkedHashMap не е синхронизиран. Ако няколко нишки споделят този кеш, синхронизирай достъпа отвън, включително при четене: get може да промени реда на обхождане.

Примери

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

Резултат

[B, A]
[A, C]

Лимитът е два записа. `get("A")` премества `A` след `B`, затова добавянето на `C` премахва `B`. При FIFO ще бъде премахнат `A`.

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

  • Java · Урок 40 · Средно · Версия: 2

Източници