Classe Java LinkedHashSet | W3Docs Learn Java

LinkedHashSet<E> est un HashSet<E> avec une promesse supplémentaire : lors de l'itération, vous obtenez les éléments dans l'ordre où vous les avez insérés pour la première fois. Le mécanisme de table de hachage est identique — mêmes buckets, même facteur de charge, même add, remove, contains en temps quasi-constant — mais chaque entrée porte deux pointeurs supplémentaires (before, after) qui enchaînent les entrées dans une liste doublement chaînée au fur et à mesure de leur ajout. L'itération parcourt cette liste, pas le tableau de buckets.

Si vous souhaitez les performances d'un hash-set et un ordre d'itération déterministe et prévisible, LinkedHashSet est la réponse. C'est presque une mise à niveau gratuite pour les cas où l'ordre non spécifié de HashSet vous a posé problème.

La règle « la première insertion l'emporte »

L'ordre est fixé par la première insertion d'un élément. Réajouter un élément existant ne le déplace pas :

Set<String> s = new LinkedHashSet<>();
s.add("a");
s.add("b");
s.add("c");
s.add("a");   // already present — returns false, order unchanged
System.out.println(s);   // [a, b, c]

Cela en fait le bon outil pour « mémoriser l'ordre d'arrivée des balises » ou « journaliser des événements uniques dans l'ordre chronologique ». Si vous supprimez un élément et le rajoutez, il va en fin de liste — la position était liée à l'insertion courante, et la nouvelle est la seule qui subsiste.

Le coût : des pointeurs et encore des pointeurs

Le mécanisme d'ordonnancement supplémentaire a un coût. Chaque entrée stocke non seulement (hash, key, next-in-bucket) comme HashSet, mais (hash, key, next-in-bucket, before, after). Cela représente deux références supplémentaires par élément — environ 16 octets de plus sur une JVM 64 bits. Pour un ensemble de 10 millions de Long, cela représente environ 160 Mo supplémentaires. Pour la plupart du code applicatif, c'est négligeable ; pour des structures de données de taille cache, cela compte.

En échange, vous obtenez O(1) pour chaque opération (comme HashSet) ainsi qu'un ordre d'itération stable qui ne dépend pas du facteur de charge, du rehash, de la distribution des hachages ou de la version de la JVM.

Le coût d'itération est proportionnel à la taille, pas à la capacité

Il y a un avantage subtil sur HashSet : parcourir un LinkedHashSet suit la liste chaînée, donc il visite exactement size entrées. Itérer sur un HashSet parcourt chaque bucket, donc il visite environ capacity slots — y compris les vides. Pour un ensemble peu peuplé, cela peut faire une différence significative. Si vous construisez un ensemble, l'agrandissez bien au-delà des éléments que vous conserverez, puis itérez souvent, LinkedHashSet peut en réalité itérer plus vite.

Quand le choisir

La logique de décision :

L'ordre importe peu, vous avez juste besoin d'un test d'appartenance rapide → HashSet. Plus petit, plus simple.
Vous voulez mémoriser l'ordre d'insertion → LinkedHashSet. Même vitesse pour add/contains, itération prévisible.
Vous voulez un ordre trié → TreeSet. Algorithme différent, opérations en temps logarithmique.

La raison la plus courante de choisir LinkedHashSet est défensive : vous construisez une API publique qui retourne un Set, et vous ne voulez pas que les appelants dépendent de l'ordre arbitraire de HashSet. Un LinkedHashSet est ce que vous pouvez retourner de plus judicieux — il a le même contrat qu'un Set, mais l'itération est reproductible entre les exécutions et les JVMs, ce qui rend la sortie visible par l'utilisateur stable et les tests plus faciles à écrire.

Un exemple concret : balises uniques dans l'ordre d'arrivée

Le programme ci-dessous construit deux ensembles à partir du même flux d'entrées de balises : un avec HashSet, un avec LinkedHashSet. L'ordre d'itération de HashSet dépend de la JVM (il est stable mais arbitraire pour une JVM donnée) ; l'ordre de LinkedHashSet est exactement l'ordre dans lequel les éléments uniques sont apparus pour la première fois. Il montre ensuite la règle « supprimer et rajouter », et construit enfin un déduplicateur préservant l'ordre en deux lignes.

java— editable, runs on the server

import java.util.*;
import java.util.stream.*;

public class LinkedHashSetShowcase {
  public static void main(String[] args) {
    String[] events = { "login", "view", "purchase", "view", "logout", "login", "view" };

Set<String> hashed = new HashSet<>();
    Set<String> linked = new LinkedHashSet<>();
    for (String e : events) { hashed.add(e); linked.add(e); }

System.out.println("input:    " + Arrays.toString(events));
    System.out.println("HashSet:        " + hashed + "   (order may be anything)");
    System.out.println("LinkedHashSet:  " + linked + "   (first-insertion order)");

// --- The 'first-insertion wins' rule ---
    Set<String> demo = new LinkedHashSet<>();
    demo.add("a"); demo.add("b"); demo.add("c");
    demo.add("a");                 // already there — order unchanged
    System.out.println("\nre-add 'a':       " + demo);
    demo.remove("a"); demo.add("a"); // gone then back — moves to end
    System.out.println("remove+re-add 'a': " + demo);

// --- Order-preserving deduplicator in two lines ---
    List<Integer> noisy = List.of(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5);
    List<Integer> deduped = noisy.stream()
        .collect(Collectors.toCollection(LinkedHashSet::new))
        .stream().toList();
    System.out.println("\nnoisy:    " + noisy);
    System.out.println("deduped:  " + deduped + "   (order preserved)");

// --- Iteration cost: LinkedHashSet visits size entries, not capacity slots ---
    Set<Integer> big = new LinkedHashSet<>(2_000_000); // huge capacity, few elements
    for (int i = 0; i < 10; i++) big.add(i);
    long t0 = System.nanoTime();
    int sum = 0;
    for (int x : big) sum += x;
    long t1 = System.nanoTime();
    System.out.println("\nsum of " + big.size() + " elements in a " + 2_000_000
        + "-bucket set: " + sum + "  in " + (t1 - t0) + " ns");
  }
}

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

Le LinkedHashSet a affiché les événements uniques dans l'ordre où ils sont apparus pour la première fois. Le HashSet les a affichés dans un ordre quelconque — celui dicté par la disposition des buckets.
Réajouter "a" n'a rien changé à l'ordre. Le supprimer puis le rajouter l'a déplacé en fin de liste. C'est la première insertion qui ancre la position.
Le déduplicateur préservant l'ordre tient en une ligne une fois que vous connaissez l'astuce : collecter dans un LinkedHashSet, puis convertir en liste.
Le parcours de 10 éléments dans un LinkedHashSet de 2 000 000 buckets a visité exactement 10 entrées ; un HashSet de même forme aurait scanné chaque bucket vide entre les deux.

La suite

La troisième implémentation standard de Set vous offre quelque chose qu'aucun HashSet ni LinkedHashSet ne peut : une itération triée et la capacité de poser des questions de plage comme « toutes les balises entre a et m ». TreeSet est la prochaine étape.

Pratique

Qu'est-ce que `LinkedHashSet` vous offre qu'un simple `HashSet` n'a pas ?

Une itération dans l'ordre d'insertion des éléments, au prix de deux références supplémentaires par entréeUne itération triée selon l'ordre naturel des élémentsDes opérations thread-safe grâce à des verrous internesUne recherche en O(log n) au lieu de O(1), avec un ordre stable comme effet secondaire