Cache LRU en Java : l’ordre d’accès de LinkedHashMap

Un cache LRU évince l’entrée dont le dernier accès est le plus ancien. En Java, un LinkedHashMap ordonné par accès déplace les entrées consultées vers l’extrémité récente, ce qui permet de calculer succès et coûts dans l’ordre des requêtes.

L’exercice de cache Programmers compare les noms de villes anglais sans distinction de casse et attribue un coût de 1 à un succès et de 5 à un défaut de cache. La capacité va de 0 à 30, avec au plus 100 000 requêtes. Ce sont des coûts d’exercice, pas des temps de réponse mesurés d’une base de données.

Déroulement

Une capacité nulle renvoie immédiatement le résultat. Sinon get/put actualisent la récence et un dépassement évince la clé accédée le moins récemment.

Actualiser l’ordre lors des accès

Enregistrez la classe complète dans Solution.java. Elle cible Java 11 ou ultérieur ; l’exécution locale de l’article source a compilé pour Java 11 avec JDK 17. La méthode suppose des entrées conformes aux limites de l’exercice.

import java.util.LinkedHashMap;
import java.util.Locale;

public class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) return 5 * cities.length;
        var cache = new LinkedHashMap<String, Boolean>(16, 0.75f, true);
        int cost = 0;
        for (String city : cities) {
            String key = city.toLowerCase(Locale.ROOT);
            cost += cache.get(key) == null ? 5 : 1;
            cache.put(key, Boolean.TRUE);
            if (cache.size() > cacheSize) {
                String oldest = cache.keySet().iterator().next();
                cache.remove(oldest);
            }
        }
        return cost;
    }
}

Le dernier argument true du constructeur est important. Contrairement à l’ordre d’insertion par défaut, un LinkedHashMap ordonné par accès actualise l’ordre lors d’accès dont get et put. Comme cette implémentation ne stocke jamais de valeurs null, get(key) == null permet d’identifier un défaut de cache.

Quand la capacité est dépassée, retirez la première clé dans l’ordre d’itération : l’entrée dont l’accès est le plus ancien. Cela diffère de LFU, qui choisit selon la fréquence d’accès. Locale.ROOT rend la normalisation de casse anglaise indépendante de la locale par défaut de la machine.

Pourquoi un succès change l’éviction

Avec une capacité de 2, ces requêtes coûtent 21 au total. Le contenu du cache est affiché du plus ancien au plus récent.

Requête	Résultat	Cache après requête	Coût total
Jeju	défaut	jeju	5
Pangyo	défaut	jeju, pangyo	10
Jeju	succès	pangyo, jeju	11
Seoul	défaut	jeju, seoul	16
Pangyo	défaut	seoul, pangyo	21

Si la troisième requête ne rafraîchit pas la position de Jeju, l’éviction suivante change. Une capacité de 0 ne peut retenir d’entrée : la méthode renvoie immédiatement 5 * cities.length. Jeju et JEJU doivent aussi être normalisés vers la même clé.

Avec des opérations de hachage constantes en moyenne, M requêtes de longueur de nom L et de capacité C prennent O(M×L), normalisation comprise, et O(C×L) de stockage. Gardez les limites de L et C de l’exercice à l’esprit. Cette implémentation ne démontre ni le comportement concurrent ni une performance mesurée du cache.

Poursuivez avec les produits scalaires Java et les bornes de int pour les limites numériques, ou la normalisation d’ID pour les transformations ordonnées.