LinkedHashSet/LinkedHashMap

1. ¿Qué son LinkedHashSet y LinkedHashMap?

En la biblioteca estándar de Java hay varias implementaciones de las colecciones Set y Map. Las más conocidas son HashSet y HashMap. Estas estructuras proporcionan acceso rápido a los elementos mediante hash, pero no garantizan ningún orden al iterarlos. Cuando importa el orden de recorrido, entran en juego LinkedHashSet y LinkedHashMap.

• LinkedHashSet es un Set que recuerda el orden de inserción de los elementos.
• LinkedHashMap es un Map que recuerda el orden de inserción de los pares clave–valor (o, si se desea, el orden de acceso).

Están implementados como «normales» HashSet/HashMap, pero se complementan con una lista doblemente enlazada para mantener el orden de los elementos.

2. Orden de inserción y orden de acceso

Orden de inserción

De forma predeterminada, LinkedHashSet y LinkedHashMap garantizan que al iterar los elementos se devuelvan en el orden en que fueron añadidos (for-each/iterador).

Set<String> set = new LinkedHashSet<>();
set.add("A");
set.add("B");
set.add("C");
for (String s : set) {
    System.out.println(s);
}
// Imprimirá: 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));
}
// Imprimirá: 1 -> one, 2 -> two, 3 -> three

Orden de acceso (solo para LinkedHashMap)

LinkedHashMap tiene un modo de orden por último acceso (access order). Si al crear el mapa se pasa true como tercer parámetro del constructor, cada vez que se accede a un elemento (get/put) este se mueve al final de la lista.

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); // Acceso a la clave 2

for (Integer key : lruMap.keySet()) {
    System.out.println(key);
}
// Imprimirá: 1 3 2 (2 es el último porque se accedió a él)

Caché LRU mediante removeEldestEntry

La principal característica de LinkedHashMap es la sencilla implementación de un caché LRU (Least Recently Used, «el menos usado recientemente»). Basta con sobrescribir el método removeEldestEntry(Map.Entry<K,V> eldest): si devuelve true, el elemento más «antiguo» se elimina al añadir uno nuevo.

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

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // true: orden por acceso
        this.maxSize = maxSize;
    }

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

// Uso:
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1); // Hacemos que 1 sea el más "reciente"
cache.put(4, "four"); // Se eliminará 2 (el más antiguo)
System.out.println(cache.keySet()); // [3, 1, 4]

3. Coste en memoria y rendimiento: LinkedHashSet/LinkedHashMap vs HashSet/HashMap

Cómo funciona

Internamente son casi como los «normales» HashSet/HashMap, pero cada elemento también se guarda en una lista doblemente enlazada. Esta estructura adicional «recuerda» el orden de inserción/acceso.

Coste de memoria

Debido a las referencias prev/next en cada nodo, se necesita más memoria. Con millones de elementos es apreciable; para tareas típicas, es un precio razonable por obtener un orden determinista.

Coste en rendimiento

Las operaciones básicas de inserción/búsqueda/eliminación siguen siendo amortizado O(1). La iteración es un poco más lenta debido al recorrido de la lista, pero en la mayoría de los casos la diferencia es mínima. Y el escenario «elimina el más antiguo» (LRU) se implementa de forma muy eficiente, ya que el elemento «más viejo» siempre está en la cabeza de la lista.

En resumen: si el orden es importante, elige LinkedHashSet/LinkedHashMap. Si necesitas ahorrar memoria y el orden no importa, basta con HashSet/HashMap.

4. Caché, salida determinista, pruebas estables

Caché (LRU)

LinkedHashMap es una base ideal para cachés con límite de tamaño y eliminación automática de elementos «antiguos». Se usa en bibliotecas/frameworks, al trabajar con archivos, imágenes y resultados de cómputo.

Salida determinista

Para informes, exportación y serialización, donde es crítico un formato de datos predecible, utiliza LinkedHashSet/LinkedHashMap. Es especialmente importante para las pruebas: el orden no «baila» de una ejecución a otra.

Pruebas estables

En las pruebas unitarias a menudo se comparan colecciones esperadas con las obtenidas. Si el orden no está garantizado, las pruebas pueden fluctuar. Con las implementaciones «linked», el determinismo aporta estabilidad.

Ejemplo: comparación de HashMap y 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());   // ¡El orden puede ser cualquiera!
System.out.println(linkedMap.keySet()); // Siempre 1, 2, 3, 4, 5

5. LinkedList vs ArrayDeque para colas

LinkedList

• Implementa las interfaces List, Deque, Queue.
• Lista doblemente enlazada: inserciones/eliminaciones rápidas al inicio y al final.
• Puede usarse como cola (FIFO), pila (LIFO) y cola de doble extremo.

ArrayDeque

• Implementa Deque, Queue (pero no List).
• Basado en un array; se expande automáticamente.
• A menudo es más rápido que LinkedList para operaciones de cola/pila; tiene menos sobrecarga.
• No admite el elemento null.

¿Cuándo usar cada uno?

• Colas y pilas: casi siempre ArrayDeque.
• Muchas inserciones/eliminaciones en el medio y además necesitas lista — LinkedList.
• Set/Map con orden — LinkedHashSet/LinkedHashMap.

Ejemplo: cola de tareas

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

Ejemplo: pila

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

Conclusión:
— Para colas y pilas — ArrayDeque.
— Para una lista con inserciones frecuentes en el medio — LinkedList.
— Para Set/Map con orden — LinkedHashSet/LinkedHashMap.

6. Errores típicos al trabajar con LinkedHashSet/LinkedHashMap

Error n.º 1: esperar que HashSet/HashMap conserven el orden.
HashSet/HashMap no garantizan el orden. Si es importante — utiliza LinkedHashSet/LinkedHashMap.

Error n.º 2: usar LinkedHashMap para caché sin sobrescribir removeEldestEntry.
Para LRU hay que sobrescribir removeEldestEntry; de lo contrario, el mapa crecerá sin límites.

Error n.º 3: usar LinkedList para colas/pilas sin necesidad.
En la mayoría de los casos, ArrayDeque es más rápida y eficiente.

Error n.º 4: esperar ordenación de LinkedHashMap.
LinkedHashMap conserva el orden de inserción/acceso, pero no ordena por clave. Para ordenar — TreeMap.

Error n.º 5: añadir null a ArrayDeque.
ArrayDeque no admite elementos null — lanzará NullPointerException.

Error n.º 6: comparar colecciones sin tener en cuenta el orden.
Al comparar LinkedHashSet/LinkedHashMap con HashSet/HashMap normales, ten en cuenta las diferencias en el orden de los elementos.