CKTIS / Java
Cache LRU par ordre d’accès
Utilisez une `LinkedHashMap` en ordre d’accès pour évincer, lorsque la limite de taille est dépassée, l’entrée consultée le moins récemment plutôt que la première insérée.
Version : Java SE 21
Syntaxe
new LinkedHashMap<K, V>(initialCapacity, loadFactor, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxEntries; } }LRU (least recently used) évince l’entrée dont le dernier accès est le plus ancien. FIFO (first in, first out) évince l’entrée insérée en premier : la lire ne change pas l’ordre d’éviction. LRU se fonde donc sur le dernier accès, tandis que FIFO se fonde sur l’insertion.
Dans LinkedHashMap, le troisième argument du constructeur, true, active l’ordre d’accès à la place de l’ordre d’insertion par défaut. Avec les opérations de l’exemple, le parcours va de l’entrée dont le dernier accès est le plus ancien à celle dont le dernier accès est le plus récent. Dans Java SE 21, putFirst et putLast placent explicitement une entrée au début ou à la fin sans enregistrer d’accès. L’ordre de parcours peut donc différer de l’ordre des derniers accès. Un get sur une clé présente ou un put qui met à jour une entrée la déplace en fin de parcours, sauf si elle s’y trouve déjà. Un get sur une clé absente et containsKey ne changent pas l’ordre.
L’ordre d’accès ne limite pas à lui seul la taille de la map. Après l’insertion d’une nouvelle entrée par put, la méthode redéfinie removeEldestEntry renvoie true si size() > maxEntries, et la map supprime sa première entrée. initialCapacity désigne la capacité initiale, non le nombre maximal d’entrées ; cette règle ne prévoit pas d’expiration dans le temps.
LinkedHashMap n’est pas synchronisée. Si plusieurs threads partagent ce cache, synchronisez les accès de l’extérieur, y compris les lectures : get peut modifier l’ordre de parcours.
Exemples
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());
}
}Résultat
[B, A] [A, C]
La limite est de deux entrées. `get("A")` déplace `A` après `B` ; l’insertion de `C` évince donc `B`. FIFO évincerait `A`.
Leçons associées
- Java · Leçon 40 · Intermédiaire · Version : 2