Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / Java

Cache LRU por ordem de acesso

Usa um `LinkedHashMap` ordenado por acesso para remover, ao ultrapassar o limite de tamanho, a entrada a que se acedeu há mais tempo, e não a primeira a ser inserida.

Versão: Java SE 21

Sintaxe

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

LRU (least recently used) remove a entrada cujo último acesso ocorreu há mais tempo. FIFO (first in, first out) remove a entrada inserida primeiro: lê-la não altera a ordem de remoção. LRU baseia-se, portanto, no último acesso, enquanto FIFO se baseia na inserção.

Em LinkedHashMap, o terceiro argumento do construtor, true, ativa a ordem de acesso em vez da ordem de inserção predefinida. Com as operações do exemplo, a iteração vai do acesso menos recente ao mais recente. Em Java SE 21, putFirst e putLast colocam explicitamente uma entrada no início ou no fim sem registar um acesso, pelo que a ordem de iteração pode diferir da ordem dos últimos acessos. Um get com uma chave presente ou um put que atualiza uma entrada existente move essa entrada para o fim, caso ainda não esteja lá. Um get com uma chave ausente e containsKey não alteram a ordem.

A ordem de acesso, por si só, não limita o tamanho do mapa. Depois de put inserir uma nova entrada, o método redefinido removeEldestEntry devolve true se size() > maxEntries, e o mapa remove a primeira entrada. initialCapacity é a capacidade inicial, não um limite de entradas; esta regra não faz as entradas expirar com o tempo.

LinkedHashMap não é sincronizado. Se várias threads partilharem esta cache, sincroniza os acessos externamente, incluindo as leituras: get pode alterar a ordem de iteração.

Exemplos

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

Resultado

[B, A]
[A, C]

O limite é de duas entradas. `get("A")` move `A` para depois de `B`, pelo que inserir `C` remove `B`. FIFO removeria `A`.

Lições relacionadas

  • Java · Lição 40 · Intermédio · Versão: 2

Fontes