Java LinkedHashMap

LinkedHashMap<K, V> est un HashMap<K, V> auquel une liste doublement chaînée est ajoutée à travers chaque entrée. La table de hachage fait son travail habituel — O(1) pour put, get, remove — et la liste chaînée vous garantit un ordre d'itération prévisible et garanti. Par défaut, cet ordre est l'ordre d'insertion ; activez un seul indicateur de constructeur et il devient l'ordre d'accès, la brique de base d'un cache LRU (least-recently-used).

Deux ordres, une seule classe

Les constructeurs reprennent ceux de HashMap, avec un supplémentaire :

new LinkedHashMap<>();                              // insertion order
new LinkedHashMap<>(16, 0.75f, false);              // insertion order, explicit
new LinkedHashMap<>(16, 0.75f, true);               // ACCESS order

Ce troisième boolean est l'indicateur accessOrder. Avec la valeur false (par défaut), chaque put d'une nouvelle clé ajoute l'entrée en fin de liste chaînée, et un put d'une clé existante laisse sa position inchangée. Avec la valeur true, chaque get, put ou getOrDefault qui touche une clé déplace cette entrée à la fin de la liste — l'entrée la plus récemment accédée est toujours en dernier ; la moins récemment accédée est toujours en premier.

Ce second mode est rare dans le code applicatif courant, mais le seul endroit où vous le verrez est précisément là où vous en avez le plus besoin : l'implémentation d'un cache.

L'itération par ordre d'insertion est l'usage courant

90 % du temps, vous utilisez LinkedHashMap parce que vous souhaitez une sortie stable. Exemples :

• Renvoyer un Map<String, Object> depuis un endpoint de sérialisation JSON en voulant que les champs apparaissent dans l'ordre d'insertion.
• Journaliser le contenu d'une map dans un ordre déterministe pour les diffs.
• Construire une configuration où l'ordre compte (par exemple : chaîne de middleware, ordre des en-têtes, pipeline de validation).
• Renvoyer un Map depuis une API publique sans que les appelants dépendent de l'ordre arbitraire de HashMap.

Le coût par rapport à HashMap représente deux références supplémentaires par entrée (les pointeurs before et after). Pour des maps de taille configuration, cela n'a pas d'importance ; dans des boucles serrées sur de très grandes maps, vous pourrez préférer un HashMap si vous le pouvez.

L'itération est proportionnelle à la taille

Avantage annexe : itérer sur un LinkedHashMap parcourt la liste chaînée, qui contient exactement size entrées. Itérer sur un HashMap parcourt chaque case de bucket — y compris les cases vides. Pour une map peu peuplée, la différence est significative.

Construction d'un cache LRU

La fonctionnalité phare de l'ordre d'accès est le hook protégé removeEldestEntry. Il est appelé après chaque put, et s'il retourne true, la map supprime sa première entrée (la plus ancienne). En combinant les deux :

class LruCache<K, V> extends LinkedHashMap<K, V> {
  private final int max;
  LruCache(int max) { super(16, 0.75f, true); this.max = max; }
  @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > max;
  }
}

Douze lignes pour un cache LRU non thread-safe mais pleinement fonctionnel. Chaque get repositionne l'entrée en fin de liste ; chaque put appelle removeEldestEntry ; dès que la taille dépasse max, l'entrée en tête (la moins récemment accédée) est évincée.

Pour un LRU thread-safe, vous l'enveloppez avec Collections.synchronizedMap — ou mieux — utilisez une vraie bibliothèque de cache (Caffeine), car les mises à jour de l'ordre d'accès font de chaque get une écriture en interne, et le simple wrapper synchronisé sérialise toutes les lectures. Mais pour du code mono-thread, c'est l'astuce classique et elle mérite d'être connue.

Les valeurs nulles et autres règles

Identiques à HashMap : une clé null, un nombre quelconque de valeurs null. Pas thread-safe. L'égalité est l'égalité structurelle définie par Map — un LinkedHashMap et un HashMap contenant les mêmes entrées sont equals. L'ordre d'itération ne fait pas partie de l'égalité ; c'est simplement ce que vous obtenez en itérant.

Exemple complet : ordre d'insertion, ordre d'accès et cache LRU

Le programme ci-dessous construit une petite chaîne de middleware par ordre d'insertion, compare l'itération de HashMap et LinkedHashMap sur les mêmes données, puis implémente un petit cache LRU et observe les évictions.

Ce qu'il faut retenir de l'exécution :

• Le pipeline itère dans l'ordre log → auth → rateLimit → handler — exactement l'ordre d'insertion. Un HashMap classique aurait toujours les quatre entrées mais dans un ordre arbitraire.
• HashMap et LinkedHashMap contenant les mêmes données s'affichent dans des ordres différents ; le LinkedHashMap correspond à keys et le HashMap non.
• Le cache LRU a réordonné lors de l'appel à get("a") — a est passé en fin de liste, faisant de b le nouvel aîné. Le put("d", "D") suivant a déclenché l'éviction de b, pas de a. C'est la règle de l'ordre d'accès en action.

La suite

La troisième implémentation standard de Map vous offre quelque chose qu'aucune des deux basées sur le hachage ne peut faire : une itération triée par clé et des requêtes par plage (subMap, headMap, tailMap, firstKey, lastKey). TreeMap est le prochain chapitre ; la structure est identique à celle de TreeSet en dessous — ce sont littéralement les mêmes lignes de code d'arbre rouge-noir.

Pratique