LinkedHashMap a été introduit dans Java 1.4 comme une structure de données hybride combinant la recherche moyenne O(1) de HashMap avec une liste doublement liée qui fournit un ordre d'itération déterministe, soit par ordre d'insertion, soit par ordre d'accès. Son design a introduit la méthode modèle removeEldestEntry, permettant aux sous-classes de mettre en œuvre des politiques d'éviction LRU (Least Recently Used) en retournant true lorsque la carte dépasse une taille désirée. Cependant, son implémentation n'a jamais été conçue pour une utilisation concurrente ; elle hérite de la nature non sécurisée de HashMap et ajoute la complexité de maintenir les pointeurs before et after bi-directionnels à travers toutes les entrées, y compris celles à l'intérieur des seaux transformés en arbres.
Lors d'une modification structurelle concurrente — comme un thread insérant pendant qu'un autre supprime ou redimensionne — les pointeurs de la liste liée peuvent être mis à jour de manière non atomique, menant à une structure graphique corrompue où les entrées forment des références circulaires ou deviennent orphelines de la chaîne principale. Par exemple, si le Thread A met à jour le pointeur after d'une entrée pour pointer vers l'Entrée B, mais que le Thread B supprime l'Entrée B et met à jour son pointeur before en même temps, la liste peut finir par faire pointer A vers B alors que B pointe vers C, ignorant effectivement A ou créant un cycle. Cette corruption fait que les itérateurs tournent indéfiniment (consommant 100 % du CPU) ou ignorent silencieusement des entrées valides, rendant la politique removeEldestEntry peu fiable car le pointeur "eldest" peut ne plus refléter la vraie tête de la liste.
Pour utiliser LinkedHashMap en toute sécurité dans des contextes multithreadés, vous devez synchroniser toutes les opérations à l'extérieur. Pour les caches avec accessOrder=true, même get() est une modification structurelle (il réorganise la liste liée), donc les optimisations standard de ReadWriteLock pour les opérations en lecture gratuite sont invalides ; vous devez traiter toutes les opérations comme des écritures ou utiliser un mutex global. L'approche la plus sûre est Collections.synchronizedMap, bien que vous deviez vous synchroniser manuellement sur la carte lors de l'itération. Cependant, pour les systèmes de production, remplacez LinkedHashMap par Caffeine ou le CacheBuilder de Guava, qui fournissent des algorithmes d'éviction sans contention globale.
public class SafeLRUCache<K, V> { private final Map<K, V> map; public SafeLRUCache(int maxSize) { // LinkedHashMap n'est PAS thread-safe ; synchronisez à l'extérieur this.map = Collections.synchronizedMap(new LinkedHashMap<>(16, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxSize; } }); } // Toutes les méthodes doivent se synchroniser sur la carte public V get(K key) { synchronized (map) { return map.get(key); } } public void put(K key, V value) { synchronized (map) { map.put(key, value); } } // L'itération nécessite une synchronisation explicite public void forEach(BiConsumer<K, V> action) { synchronized (map) { map.forEach(action); } } }
Un service backend pour une plateforme de commerce électronique nécessitait un cache en mémoire pour les données de tarification des produits afin de réduire la charge de la base de données. L'implémentation initiale utilisait LinkedHashMap avec accessOrder=true et surchargeait removeEldestEntry pour imposer une limite de 1 000 éléments, supposant que la carte supprimerait simplement automatiquement de vieilles entrées. Lors des tests à faible charge, cela fonctionnait correctement ; cependant, sous le trafic de production avec quarante threads concurrents gérant des ventes flash, le service a connu des pics intermittents de CPU à 100 % et une eventual starvation des threads.
Les dumps de threads ont révélé que plusieurs threads étaient bloqués à l'intérieur des itérateurs de LinkedHashMap, traversant des références circulaires dans la liste doublement liée causées par des modifications concurrentes. En particulier, un thread redimensionnait la table interne pendant qu'un autre mettait à jour l'ordre d'accès d'une entrée, provoquant un pointeur after d'un nœud Entry pour se référencer lui-même, créant une boucle infinie pendant l'itération. De plus, le callback removeEldestEntry supprimait parfois la mauvaise entrée car le pointeur "eldest" avait été corrompu par un réordonnancement concurrent, entraînant une invalidation de cache où les éléments récemment accédés étaient évincés au lieu de ceux obsolètes.
L'équipe a d'abord envisagé d'envelopper la carte avec Collections.synchronizedMap. Avantages : Cela nécessite un minimum de modifications de code et assure l'atomicité des opérations individuelles en les enveloppant dans des méthodes synchronized. Inconvénients : Cela introduit un moniteur global, sérialisant toutes les lectures et écritures, ce qui réduit le débit d'une attente de 20 000 opérations par seconde à moins de 3 000 sous contention. De plus, les itérateurs nécessitaient toujours des blocs synchronized(map) explicites, que les développeurs oubliaient parfois, entraînant une ConcurrentModificationException.
Ensuite, ils ont évalué l'utilisation de ConcurrentHashMap associé à une ConcurrentLinkedQueue pour suivre la récence et un thread de nettoyage en arrière-plan. Avantages : Cela offre une haute concurrence pour les lectures et les écritures. Inconvénients : La mise en œuvre correcte de LRU est sujette à erreurs ; la suppression de l'entrée la plus ancienne n'est pas atomique avec l'insertion, permettant au cache de dépasser temporairement sa limite de taille de manière significative sous une forte charge. De plus, la mise à jour de la queue à chaque get() nécessite une opération d'écriture, créant des points de contention similaires et de la complexité à maintenir la cohérence entre la queue et la carte.
Enfin, ils ont évalué Caffeine, une bibliothèque de mise en cache hautes performances. Avantages : Elle utilise un BoundedLocalCache avec striping de verrou et un tampon d'écriture pour les évictions, permettant des lectures concurrentes sans verrouillage et des écritures à haut débit. Elle gère l'éviction LRU/W-TinyLFU de manière atomique sans synchronisation explicite. Inconvénients : Elle ajoute une dépendance externe et nécessite d'apprendre une nouvelle API (par exemple, CacheLoader).
L'équipe a sélectionné Caffeine après des tests de charge démontrant qu'elle soutenait plus de 80 000 opérations par seconde avec une latence p99 inférieure à 1 ms, tandis que le LinkedHashMap synchronisé se retrouvait bloqué à 5k ops/sec avec des pics p99 atteignant 500 ms. La migration impliquait de remplacer la carte par Caffeine.newBuilder().maximumSize(1000).build() et d'enregistrer un auditeur de suppression pour la logique de nettoyage.
La surveillance post-déploiement a montré une utilisation stable du CPU et zéro blocage de thread. Le taux de réussite du cache s'est amélioré de 85 % à 94 % car l'éviction est devenue déterministe et sans condition de course. L'incident a révélé que LinkedHashMap est une structure de données monothreaded inadaptée pour les caches LRU concurrents malgré son API pratique.
Comment LinkedHashMap maintient-il l'ordre LRU pour les entrées qui ont été déplacées dans des seaux transformés en arbres (arbres rouge-noir) en raison de fortes collisions de hachage ?
LinkedHashMap utilise une classe interne spécialisée Entry qui étend HashMap.Node et inclut des pointeurs before et after. Lorsqu'un seau se transforme en arbre, LinkedHashMap surcharge newTreeNode pour créer des instances TreeNode qui héritent toujours de LinkedHashMap.Entry (via LinkedHashMap.TreeNode). Par conséquent, même lorsque les entrées sont stockées dans une structure d'arbre pour la résolution des collisions O(log n), elles restent des nœuds dans la liste doublement liée globale. La méthode afterNodeAccess met à jour ces pointeurs après chaque accès, garantissant que la chaîne LRU traverse les entrées peu importe si elles résident dans des listes liées ou des arbres dans la table de hachage.
Pourquoi appeler get() sur un LinkedHashMap avec accessOrder=true déclenche-t-il une ConcurrentModificationException s'il est effectué pendant l'itération, alors que la même opération sur un standard HashMap ne le fait pas ?
En mode accessOrder, LinkedHashMap traite get() comme une modification structurelle car il déplace l'entrée accédée à la fin de la liste doublement liée, incrémentant modCount. L'itérateur fail-fast vérifie ce compteur et lance immédiatement une exception en détectant le changement. En revanche, un standard HashMap n'incrémente modCount que lors des insertions, suppressions et redimensionnements ; get() est en lecture seule par rapport à la structure de la table. Cette distinction signifie que même les opérations logiques « en lecture seule » peuvent invalider les itérateurs dans LinkedHashMap, rendant nécessaire la synchronisation pour toutes les opérations y compris les lectures lors de l'itération de manière concurrente.
Quelle corruption spécifique de pointeur se produit lors du redimensionnement concurrent (rehashing) dans LinkedHashMap qui est impossible dans un standard HashMap ?
Lors du redimensionnement, HashMap transfère les nœuds vers un nouveau tableau, risquant des boucles infinies dans les seaux s'il est effectué de manière concurrente. LinkedHashMap risque également de corrompre les pointeurs before et after qui forment la liste liée auxiliaire. Si le Thread A relie à nouveau les entrées pour préserver l'ordre dans le nouveau tableau pendant que le Thread B modifie la liste (par exemple via remove), le Thread A peut lier une entrée à un successeur que le Thread B a déjà dissocié, créant une référence pendante ou un cycle. En particulier, le pointeur after du nœud d'en-tête pourrait pointer vers une entrée dont le pointeur before a été annulé par un autre thread, brisant l'invariance de la liste et provoquant des itérateurs se tournant indéfiniment lorsque next() suit la chaîne brisée.