LinkedHashSet/LinkedHashMap

1. Qu’est-ce que LinkedHashSet et LinkedHashMap ?

Dans la bibliothèque standard de Java, il existe plusieurs implémentations des collections Set et Map. Les plus connues — ce sont HashSet et HashMap. Ces structures offrent un accès rapide aux éléments via le hachage, mais ne garantissent aucun ordre lors de l’itération. Lorsque l’ordre de parcours est important — LinkedHashSet et LinkedHashMap viennent à la rescousse.

• LinkedHashSet — c’est un Set qui mémorise l’ordre d’ajout des éléments.
• LinkedHashMap — c’est une Map qui mémorise l’ordre d’ajout des paires clé–valeur (ou, au choix, l’ordre d’accès).

Elles sont implémentées comme des HashSet/HashMap « classiques », mais enrichies d’une liste doublement chaînée pour conserver l’ordre des éléments.

2. Ordre d’insertion et ordre d’accès

Ordre d’insertion

Par défaut, LinkedHashSet et LinkedHashMap garantissent qu’à l’itération les éléments sont renvoyés dans l’ordre où ils ont été ajoutés (for-each/itérateur).

Set<String> set = new LinkedHashSet<>();
set.add("A");
set.add("B");
set.add("C");
for (String s : set) {
    System.out.println(s);
}
// Affiche : A B C

Map<Integer, String> map = new LinkedHashMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
for (Integer key : map.keySet()) {
    System.out.println(key + " -> " + map.get(key));
}
// Affiche : 1 -> one, 2 -> two, 3 -> three

Ordre d’accès (uniquement pour LinkedHashMap)

LinkedHashMap propose un mode d’ordre par dernier accès (access order). Si, lors de la création de la map, vous passez true comme troisième paramètre du constructeur, alors à chaque accès à un élément (get/put) celui-ci est déplacé en fin de liste.

Map<Integer, String> lruMap = new LinkedHashMap<>(16, 0.75f, true);
lruMap.put(1, "one");
lruMap.put(2, "two");
lruMap.put(3, "three");

lruMap.get(2); // Accès à la clé 2

for (Integer key : lruMap.keySet()) {
    System.out.println(key);
}
// Affiche : 1 3 2 (2 est en dernier, car on y a accédé)

Cache LRU via removeEldestEntry

Le principal « atout » de LinkedHashMap — une mise en œuvre simple d’un cache LRU (Least Recently Used, « le moins récemment utilisé »). Il suffit de redéfinir la méthode removeEldestEntry(Map.Entry<K,V> eldest) : si elle renvoie true, l’élément le plus « ancien » est supprimé lors de l’ajout d’un nouveau.

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // true — ordre par accès
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

// Utilisation :
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1); // On rend 1 le plus « récent »
cache.put(4, "four"); // 2 sera supprimé (le plus ancien)
System.out.println(cache.keySet()); // [3, 1, 4]

3. Coût en mémoire et en performance : LinkedHashSet/LinkedHashMap vs HashSet/HashMap

Comment c’est conçu

En interne — presque comme des HashSet/HashMap, mais chaque élément est également stocké dans une liste doublement chaînée. Cette structure supplémentaire « mémorise » l’ordre d’ajout/d’accès.

Coût mémoire

À cause des références prev/next sur chaque maillon, davantage de mémoire est nécessaire. Pour des millions d’éléments, cela se remarque ; pour des cas typiques — c’est un prix justifié pour obtenir un ordre déterministe.

Coût en performance

Les opérations de base d’ajout/recherche/suppression restent amorties O(1). L’itération est un peu plus lente à cause du parcours de la liste, mais dans la majorité des cas la différence est minime. Quant au scénario « supprimer le plus ancien » (LRU), il est très efficace, puisque l’élément le plus « âgé » se trouve toujours en tête de liste.

En résumé : si l’ordre est important — choisissez LinkedHashSet/LinkedHashMap. Si vous devez économiser de la mémoire et que l’ordre n’est pas nécessaire — HashSet/HashMap suffisent.

4. Mise en cache, sortie déterministe, tests stables

Mise en cache (LRU)

LinkedHashMap — une base idéale pour des caches avec limite de taille et suppression automatique des éléments « anciens ». On l’utilise dans des bibliothèques/frameworks, pour la gestion de fichiers, d’images et de résultats de calcul.

Sortie déterministe

Pour les rapports, l’export, la sérialisation, où une représentation des données prévisible est cruciale, utilisez LinkedHashSet/LinkedHashMap. C’est particulièrement important pour les tests — l’ordre ne « danse » pas d’une exécution à l’autre.

Tests stables

Dans les tests unitaires, on compare souvent des collections attendues avec celles obtenues. Si l’ordre n’est pas garanti, les tests peuvent « flapper ». Avec les implémentations « linked », le caractère déterministe assure la stabilité.

Exemple : comparaison entre HashMap et LinkedHashMap

Map<Integer, String> hashMap = new HashMap<>();
Map<Integer, String> linkedMap = new LinkedHashMap<>();

for (int i = 1; i <= 5; i++) {
    hashMap.put(i, "val" + i);
    linkedMap.put(i, "val" + i);
}

System.out.println(hashMap.keySet());   // L'ordre peut être quelconque !
System.out.println(linkedMap.keySet()); // Toujours 1, 2, 3, 4, 5

5. LinkedList vs ArrayDeque pour les files

LinkedList

• Implémente les interfaces List, Deque, Queue.
• Liste doublement chaînée : insertions/suppressions rapides au début et à la fin.
• Peut être utilisée comme file (FIFO), pile (LIFO), file double.

ArrayDeque

• Implémente Deque, Queue (mais pas List).
• Basée sur un tableau, s’agrandit automatiquement.
• Souvent plus rapide que LinkedList pour les opérations de file/pile ; moins de surcoûts.
• Ne prend pas en charge l’élément null.

Quand utiliser quoi ?

• Files et piles — presque toujours ArrayDeque.
• Beaucoup d’insertions/suppressions au milieu et besoin d’une liste — LinkedList.
• Set/Map avec ordre — LinkedHashSet/LinkedHashMap.

Exemple : file de tâches

Queue<String> queue = new ArrayDeque<>();
queue.add("task1");
queue.add("task2");
System.out.println(queue.poll()); // task1

Exemple : pile

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
System.out.println(stack.pop()); // second

Conclusion :
— Pour les files et les piles — ArrayDeque.
— Pour une liste avec des insertions fréquentes au milieu — LinkedList.
— Pour un Set/Map avec ordre — LinkedHashSet/LinkedHashMap.

6. Erreurs typiques avec LinkedHashSet/LinkedHashMap

Erreur n° 1 : Attendre que HashSet/HashMap conservent l’ordre.
HashSet/HashMap ne garantissent pas l’ordre. S’il est important — utilisez LinkedHashSet/LinkedHashMap.

Erreur n° 2 : LinkedHashMap pour un cache sans redéfinir removeEldestEntry.
Pour un LRU, vous devez redéfinir removeEldestEntry, sinon la map grandira sans limite.

Erreur n° 3 : Utiliser LinkedList pour des files/piles sans nécessité.
Dans la plupart des cas, ArrayDeque est plus rapide et plus économe.

Erreur n° 4 : Attendre un tri de LinkedHashMap.
LinkedHashMap conserve l’ordre d’ajout/d’accès, mais ne trie pas par clé. Pour trier — TreeMap.

Erreur n° 5 : Ajouter null dans ArrayDeque.
ArrayDeque ne prend pas en charge les éléments null — cela provoquera une NullPointerException.

Erreur n° 6 : Comparer des collections sans tenir compte de l’ordre.
En comparant LinkedHashSet/LinkedHashMap à des HashSet/HashMap ordinaires, tenez compte des différences d’ordre des éléments.