Java LinkedHashMap

LinkedHashMap<K, V> es un HashMap<K, V> con una lista doblemente enlazada que atraviesa cada entrada. La tabla hash hace su trabajo habitual — put, get, remove en O(1) — y la lista enlazada te proporciona un orden de iteración garantizado y predecible. Por defecto, ese orden es el orden de inserción; activa un indicador en el constructor y se convierte en orden de acceso, el bloque de construcción de una caché LRU (least-recently-used).

Dos ordenaciones, una clase

Los constructores replican HashMap, más uno adicional:

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

Ese tercer boolean es el indicador accessOrder. Con él en false (el valor por defecto), cada put de una clave nueva añade la entrada al final de la lista enlazada, y los put repetidos de una clave existente dejan su posición intacta. Con él en true, cada get, put o getOrDefault que toca una clave mueve esa entrada al final de la lista — la entrada accedida más recientemente siempre es la última; la accedida menos recientemente siempre es la primera.

Ese segundo modo es poco frecuente en el código de aplicaciones, pero el único lugar donde se ve es exactamente donde más se necesita: implementar una caché.

La iteración en orden de inserción es el uso más común

El 90% de las veces se recurre a LinkedHashMap porque se desea una salida estable. Ejemplos:

• Devolver un Map<String, Object> desde un endpoint que serializa JSON y querer que los campos aparezcan en el orden en que se insertaron.
• Registrar el contenido de un mapa en un orden determinista para comparaciones.
• Construir configuraciones donde el orden importa (por ejemplo: cadena de middleware, orden de cabeceras, pipeline de validación).
• Devolver un Map desde una API pública sin que los consumidores dependan del orden arbitrario de HashMap.

El coste respecto a HashMap son dos referencias adicionales por entrada (los punteros before y after). Para mapas de tamaño de configuración no importa; en bucles ajustados sobre mapas muy grandes podrías preferir un HashMap si puedes.

La iteración es proporcional al tamaño

Un beneficio secundario: iterar un LinkedHashMap recorre la lista enlazada, que contiene exactamente size entradas. Iterar un HashMap recorre todos los slots de los cubos, incluidos los vacíos. Para un mapa escasamente poblado la diferencia es significativa.

Construir una caché LRU

La característica estrella del orden de acceso es el gancho protegido removeEldestEntry. Se invoca después de cada put, y si devuelve true, el mapa elimina su primera entrada (la más antigua). Combinando los dos:

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

Doce líneas para una caché LRU completamente funcional (aunque no segura para hilos). Cada get reordena la entrada al final; cada put llama a removeEldestEntry; en cuanto el tamaño supera max, la entrada al frente (la accedida menos recientemente) es desalojada.

Para una LRU segura para hilos se puede envolver con Collections.synchronizedMap o — mejor — usar una biblioteca de caché real (Caffeine), ya que las actualizaciones del orden de acceso convierten cada get en una escritura internamente y el simple wrapper sincronizado serializa todas las lecturas. Pero para código monohilo, este es el truco clásico que vale la pena conocer.

Nulos y el resto de las reglas

Igual que HashMap: una clave null, cualquier número de valores null. No es seguro para hilos. La igualdad es la igualdad estructural que define Map — un LinkedHashMap y un HashMap con las mismas entradas son equals. El orden de iteración no forma parte de la igualdad; es simplemente lo que obtienes al iterar.

Un ejemplo práctico: orden de inserción, orden de acceso y una caché LRU

El programa siguiente construye una pequeña cadena de middleware en orden de inserción, contrasta la iteración de HashMap frente a LinkedHashMap con los mismos datos, luego implementa una pequeña caché LRU y observa cómo desaloja entradas.

Lo que se puede extraer de la ejecución:

• El pipeline itera en el orden log → auth → rateLimit → handler — exactamente el orden en que se insertó. Un HashMap simple seguiría teniendo las cuatro entradas, pero el orden sería arbitrario.
• HashMap y LinkedHashMap con los mismos datos se imprimen en órdenes distintos; el LinkedHashMap coincide con keys y el HashMap no.
• La caché LRU reordenó cuando se llamó a get(\"a\") — a pasó al final de la lista, convirtiendo a b en el nuevo más antiguo. El siguiente put(\"d\", \"D\") desencadenó el desalojo de b, no de a. Esa es la regla del orden de acceso en acción.

Qué sigue

La tercera implementación estándar de Map te ofrece algo que ninguna de las basadas en hash puede: iteración ordenada por clave y consultas de rango (subMap, headMap, tailMap, firstKey, lastKey). TreeMap es lo siguiente; la estructura es idéntica a TreeSet por dentro — literalmente es el mismo código de árbol rojo-negro.

Práctica