Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / Java

Un cache LRU avec LinkedHashMap

Créez un cache de deux entrées en Java SE 21 et voyez pourquoi la lecture d’une clé change l’entrée évincée lors de l’insertion suivante.

Version : Java SE 21

Syntaxe

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

En Java SE 21, LinkedHashMap(int, float, boolean) prend la capacité initiale de la table de hachage, le facteur de charge et le mode d’ordonnancement. Les deux premiers arguments ne fixent pas de limite d’entrées. Avec true, le parcours va de l’entrée la moins récemment utilisée à la plus récente : un get(key) réussi ou un put(key, value) place l’entrée concernée à la fin. Avec false, l’ordre est celui des insertions : ni la lecture d’une entrée existante ni le remplacement de sa valeur par put ne la déplace.

Pour évincer l’entrée la moins récemment utilisée (LRU), redéfinissez la méthode protégée removeEldestEntry(Map.Entry<K,V> eldest) dans une sous-classe. Après l’ajout d’une entrée par put ou putAll, renvoyer size() > 2 permet à la map de supprimer la première entrée quand elle en compte trois. Un remplacement ne déclenche pas ce mécanisme. Ne modifiez pas la map dans cette méthode si vous renvoyez true : l’effet de cette combinaison n’est pas spécifié.

put(K,V) insère ou remplace une valeur et remove(Object) supprime l’association correspondant à une clé. Les deux renvoient la valeur précédente, ou null si l’association était absente ou si sa valeur était null. La surcharge remove(Object,Object) ne supprime l’association que si sa valeur correspond et renvoie un boolean. Les modifications sont facultatives dans Map, mais LinkedHashMap les prend en charge. size() compte les associations clé-valeur.

keySet() renvoie un ensemble de clés ; values() renvoie une collection qui peut contenir des doublons. Ce sont des vues liées à la map, pas des copies : leur parcours suit l’ordre de la map sans actualiser la récence des entrées, une suppression via une vue modifie la map et l’ajout n’est pas pris en charge. La limite porte sur le nombre d’entrées, pas sur leur durée de vie. La map n’est pas synchronisée ; même get peut changer l’ordre et invalider un itérateur actif.

Exemples

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

Résultat

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

Sans lecture, l’insertion de `C` évince `A`. Après `get("A")`, l’ordre est `[B, A]`, donc l’insertion de `C` évince `B`. Le dernier `remove("A")` renvoie `1` et il ne reste que `C`.

Leçons associées

  • Java · Leçon 47 · Avancé · Version : 2

Sources