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

CKTIS / Java

Uma cache LRU com LinkedHashMap

Cria uma cache de duas entradas em Java SE 21 e vê por que razão ler uma chave altera a entrada removida na inserção seguinte.

Versão: Java SE 21

Sintaxe

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

Em Java SE 21, LinkedHashMap(int, float, boolean) recebe a capacidade inicial da tabela de dispersão, o fator de carga e o modo de ordenação. Os dois primeiros argumentos não limitam o número de entradas. Com true, a iteração vai da entrada utilizada há mais tempo à utilizada mais recentemente: um get(key) que encontra a chave ou um put(key, value) move a entrada correspondente para o fim. Com false, segue-se a ordem de inserção: ler uma entrada existente ou substituir o seu valor com put não altera a sua posição.

Para remover a entrada utilizada há mais tempo (LRU), redefine o método protegido removeEldestEntry(Map.Entry<K,V> eldest) numa subclasse. Depois de put ou putAll adicionar uma entrada nova, devolver size() > 2 permite ao mapa remover a primeira entrada quando passa a ter três. Substituir um valor não aciona este mecanismo. Não alteres o mapa dentro do método se devolveres true: o efeito de combinar as duas ações não está especificado.

put(K,V) insere ou substitui um valor e remove(Object) remove a associação pela chave. Ambos devolvem o valor anterior, ou null se não havia associação ou se o valor era null. A sobrecarga remove(Object,Object) só remove a associação se o valor corresponder e devolve um boolean. As operações de alteração são opcionais em Map, mas LinkedHashMap suporta-as. size() conta as associações chave-valor.

keySet() devolve um conjunto de chaves; values() devolve uma coleção que pode conter valores repetidos. São vistas ligadas ao mapa, não cópias: a iteração segue a ordem do mapa sem atualizar a ordem de utilização, remover através de uma vista altera o mapa e não é possível adicionar elementos às vistas. O limite aplica-se ao número de entradas, não ao seu tempo de permanência. O mapa não é sincronizado; até get pode alterar a ordem e invalidar um iterador ativo.

Exemplos

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

Resultado

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

Sem leitura, inserir `C` remove `A`. Depois de `get("A")`, a ordem é `[B, A]`, pelo que inserir `C` remove `B`. A última chamada a `remove("A")` devolve `1` e fica apenas `C`.

Lições relacionadas

  • Java · Lição 47 · Avançado · Versão: 2

Fontes