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