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