Clase Java LinkedHashSet | W3Docs Learn Java

LinkedHashSet<E> es HashSet<E> con una promesa adicional: al iterar, obtienes los elementos en el orden en que los insertaste por primera vez. El mecanismo de tabla hash es idéntico — mismos cubos, mismo factor de carga, mismo add, remove y contains en tiempo casi constante — pero cada entrada lleva dos punteros extra (before, after) que enlazan las entradas en una lista doblemente enlazada a medida que se agregan. La iteración recorre esa lista, no el array de cubos.

Si quieres el rendimiento de un hash-set y un orden de iteración determinista y predecible, LinkedHashSet es la respuesta. Es casi una mejora gratuita para los casos en que el orden no especificado de HashSet te ha causado problemas.

La regla "gana la primera inserción"

El orden lo fija la primera vez que se inserta un elemento. Volver a agregar un elemento existente no lo mueve:

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]

Eso lo convierte en la herramienta adecuada para "recordar el orden en que llegaron las etiquetas" o "registrar eventos únicos en orden cronológico." Si eliminas un elemento y lo vuelves a agregar, va al final de la lista — la posición estaba ligada a la inserción anterior, y la nueva es la única que queda.

El costo: punteros y más punteros

El mecanismo de ordenación adicional tiene un costo. Cada entrada almacena no solo (hash, key, next-in-bucket) como HashSet, sino (hash, key, next-in-bucket, before, after). Son dos referencias extra por elemento — aproximadamente 16 bytes adicionales en una JVM de 64 bits. Para un conjunto de 10 millones de Longs, eso equivale a unos 160 MB extra. Para la mayoría del código de aplicación es insignificante; para estructuras de datos con tamaño de caché, importa.

A cambio, obtienes O(1) en cada operación (igual que HashSet) más un orden de iteración estable que no depende del factor de carga, el rehash, la distribución de hash ni la versión de la JVM.

El costo de iteración es proporcional al tamaño, no a la capacidad

Hay una ventaja sutil sobre HashSet: recorrer un LinkedHashSet sigue la lista enlazada, por lo que visita exactamente size entradas. Iterar un HashSet recorre todos los cubos, visitando aproximadamente capacity ranuras — incluyendo las vacías. Para un conjunto escasamente poblado, eso puede ser una diferencia significativa. Si construyes un conjunto, lo expandes mucho más allá de los elementos que vas a conservar y luego iteras frecuentemente, LinkedHashSet puede iterar de manera más rápida.

Cuándo elegirlo

El flujo de decisión:

El orden no importa, solo necesitas pertenencia rápida → HashSet. Más pequeño, más simple.
Quieres recordar el orden de inserción → LinkedHashSet. Misma velocidad para add/contains, iteración predecible.
Quieres orden ordenado → TreeSet. Algoritmo diferente, operaciones en tiempo logarítmico.

La razón más común para elegir LinkedHashSet es defensiva: estás construyendo una API pública que devuelve un Set, y no quieres que los llamadores dependan del orden arbitrario de HashSet. Un LinkedHashSet es lo más conveniente que puedes devolver — tiene el mismo contrato que un Set, pero la iteración es reproducible entre ejecuciones y JVMs, lo que hace que la salida visible para el usuario sea estable y los tests más fáciles de escribir.

Un ejemplo práctico: etiquetas únicas en orden de llegada

El programa siguiente construye dos conjuntos a partir del mismo flujo de entradas de etiquetas: uno con HashSet y otro con LinkedHashSet. El orden de iteración de HashSet depende de la JVM (es estable pero arbitrario para una JVM dada); el orden de LinkedHashSet es exactamente el orden en que los elementos únicos aparecieron por primera vez. Luego muestra la regla "eliminar y volver a agregar", y finalmente construye un deduplicador que preserva el orden en tan solo dos líneas.

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

Lo que se puede extraer de la ejecución:

El LinkedHashSet imprimió los eventos únicos en el orden en que aparecieron por primera vez. El HashSet los imprimió en un orden completamente diferente — el que dictó la disposición de los cubos.
Volver a agregar "a" no cambió el orden. Eliminarlo y volver a agregarlo lo movió al final. La primera inserción es la que ancla la posición.
El deduplicador que preserva el orden es una sola línea una vez que conoces el truco: recolectar en un LinkedHashSet y luego convertirlo de nuevo a una lista.
El recorrido de 10 elementos a través de un LinkedHashSet con 2 000 000 cubos visitó exactamente 10 entradas; un HashSet de la misma forma habría escaneado todos los cubos vacíos intermedios.

Qué viene a continuación

La tercera implementación estándar de Set te ofrece algo que ni HashSet ni LinkedHashSet pueden: iteración ordenada y la capacidad de hacer preguntas de rango como "todas las etiquetas entre a y m." TreeSet es el siguiente.

Práctica

¿Qué ofrece `LinkedHashSet` que el `HashSet` simple no tiene?

Iteración en el orden en que los elementos fueron insertados por primera vez, con el costo de dos referencias extra por entradaIteración ordenada mediante el orden natural del elementoOperaciones seguras para hilos mediante bloqueos internosBúsqueda en O(log n) en lugar de O(1), con orden estable como efecto secundario