Variantes de Map: LinkedHashMap y TreeMap

Tres implementaciones de Map

La interfaz Map<K, V> asocia claves únicas a valores. Igual que Set, el JDK ofrece tres implementaciones principales con distintos compromisos:

| Clase | Orden | Complejidad | |-------|-------|-------------| | HashMap | Ninguno | O(1) operaciones | | LinkedHashMap | Inserción o acceso | O(1) operaciones | | TreeMap | Orden natural de claves o Comparator | O(log n) operaciones |

HashMap: el más rápido

HashMap es la implementación por defecto. Usa una tabla hash interna. Ideal para lookups por clave cuando el orden es irrelevante.

Map<String, Integer> edades = new HashMap<>();
edades.put("Ana", 30);
edades.put("Bob", 25);
edades.put("Carmen", 28);
edades.get("Bob"); // 25

Características:

• Orden de iteración impredecible.
• Permite un único null como clave y valores null.
• No thread-safe.
• O(1) amortizado para operaciones.

LinkedHashMap: orden de inserción

LinkedHashMap combina una tabla hash (como HashMap) con una lista doblemente enlazada que preserva el orden de inserción. Operaciones igual de rápidas; extra coste mínimo en memoria.

Map<String, Integer> orden = new LinkedHashMap<>();
orden.put("tercero", 3);
orden.put("primero", 1);
orden.put("segundo", 2);

orden.forEach((k, v) -> System.out.println(k + "=" + v));
// tercero=3, primero=1, segundo=2 (orden de inserción)

Orden de acceso (cache-friendly)

El constructor LinkedHashMap(initialCapacity, loadFactor, accessOrder) con accessOrder = true hace que la iteración siga el orden de acceso (más recientemente usado al final). Esto es la base del patrón cache LRU:

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

    public LRUCache(int capacidad) {
        super(capacidad, 0.75f, true); // accessOrder = true
        this.capacidad = capacidad;
    }

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

// Uso
LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("a", "1");
cache.put("b", "2");
cache.put("c", "3");
cache.get("a"); // ahora "a" es el más reciente
cache.put("d", "4"); // elimina "b" (el más antiguo según acceso)

Implementa SequencedMap (Java 21+)

LinkedHashMap<String, Integer> mapa = new LinkedHashMap<>();
mapa.put("b", 2);
mapa.putFirst("a", 1);
mapa.putLast("c", 3);

Map.Entry<String, Integer> primera = mapa.firstEntry();
Map.Entry<String, Integer> ultima = mapa.lastEntry();

mapa.reversed().forEach((k, v) -> System.out.println(k + "=" + v));

TreeMap: mapa ordenado por claves

TreeMap mantiene las claves ordenadas (por orden natural o Comparator). Usa un árbol binario balanceado (red-black tree) internamente. Operaciones O(log n).

TreeMap<String, Integer> alfabetico = new TreeMap<>();
alfabetico.put("pera", 3);
alfabetico.put("manzana", 5);
alfabetico.put("uva", 8);

alfabetico.forEach((k, v) -> System.out.println(k + "=" + v));
// manzana=5, pera=3, uva=8 (orden alfabético)

API NavigableMap

TreeMap implementa NavigableMap (extiende SortedMap) con métodos utiles:

| Método | Qué hace | |--------|----------| | firstKey() / lastKey() | Menor / mayor clave | | firstEntry() / lastEntry() | Entrada mínima / máxima | | ceilingKey(k) / floorKey(k) | Clave ≥ k / ≤ k | | higherKey(k) / lowerKey(k) | Clave > k / < k | | headMap(k) | Subvista con claves < k | | tailMap(k) | Subvista con claves ≥ k | | subMap(from, to) | Subvista con claves [from, to) | | descendingMap() | Vista con orden inverso | | pollFirstEntry() / pollLastEntry() | Extrae y devuelve |

NavigableMap<Integer, String> historico = new TreeMap<>();
historico.put(1990, "inicio");
historico.put(2000, "crisis");
historico.put(2010, "recuperación");
historico.put(2020, "pandemia");

historico.ceilingKey(1995); // 2000
historico.floorKey(2015); // 2010
historico.subMap(2000, 2020); // {2000=crisis, 2010=recuperación}
historico.descendingMap(); // recorrido del más reciente al más antiguo

Ideal para series temporales, rangos de precios, indices ordenados, etc.

Null en TreeMap

TreeMap no permite claves null si usas orden natural (la comparación lanzaría NPE). Los valores sí pueden ser null.

Rendimiento práctico

• HashMap y LinkedHashMap: O(1) promedio. En casos patológicos (muchas colisiones con claves adversariales), Java 8+ usa árboles rojo-negro internos, garantizando O(log n) en peor caso.
• TreeMap: O(log n) garantizado, pero constantes algo mayores.
• HashMap suele ser 2-3x más rápido que TreeMap en operaciones típicas.

EnumMap

Recordatorio importante: si la clave es un enum, usa EnumMap:

EnumMap<DayOfWeek, List<String>> agenda = new EnumMap<>(DayOfWeek.class);
agenda.put(DayOfWeek.MONDAY, List.of("reunión"));

Internamente usa un array indexado por ordinal: más rápido y compacto que HashMap<DayOfWeek, ...>.

Thread-safety

Ninguna de estas clases es thread-safe. Alternativas:

• ConcurrentHashMap: alta concurrencia, O(1) amortizado, recomendado en código concurrente.
• Collections.synchronizedMap(new HashMap<>()): envoltorio sincronizado (bloqueo global, lento).
• ConcurrentSkipListMap: equivalente concurrente de TreeMap.

ConcurrentHashMap es el más usado en producción: implementa Map y permite operaciones concurrentes de alta performance con bloqueos finos.

Cómo elegir

| Necesitas... | Usa | |--------------|-----| | Lookup rápido por clave, orden irrelevante | HashMap | | Preservar orden de inserción | LinkedHashMap | | Cache LRU o LRU-like | LinkedHashMap con accessOrder=true | | Claves ordenadas o operaciones de rango | TreeMap | | Claves enum | EnumMap | | Concurrente de alto rendimiento | ConcurrentHashMap | | Concurrente ordenado | ConcurrentSkipListMap | | Inmutable pequeño | Map.of(...) |

Métodos útiles introducidos en Java 8+

• getOrDefault(key, defaultValue): valor o defecto
• putIfAbsent(key, value): solo si no existe
• computeIfAbsent(key, k -> value): calcular y guardar si no existe
• computeIfPresent(key, (k, v) -> nuevoValor): transformar si existe
• merge(key, value, BiFunction): combinar con valor existente
• forEach(BiConsumer): iterar limpio

Ejemplo de computeIfAbsent para agrupar:

Map<String, List<Producto>> porCategoria = new HashMap<>();
for (Producto p : productos) {
    porCategoria
    .computeIfAbsent(p.categoria(), c -> new ArrayList<>())
    .add(p);
}

Buenas prácticas

• Declara con la interfaz Map<K, V> y elige la implementación al asignar.
• Si las claves tienen equals/hashCode mal implementados, toda la estructura falla. Usa records o implementa con rigor.
• Para literales, Map.of(...) hasta 10 entradas; Map.ofEntries(...) para más.
• Inmutables por defecto si no necesitas modificar.
• Para iteración ordenada, elige LinkedHashMap o TreeMap desde el principio, no intentes "ordenar" un HashMap después.

Resumen

Las tres implementaciones cubren tres necesidades fundamentales:

• HashMap: velocidad pura.
• LinkedHashMap: velocidad + orden o cache LRU.
• TreeMap: operaciones ordenadas y búsquedas por rango.

Elegir la correcta es parte del diseño del sistema. Un desarrollador experto razona sobre estos compromisos de forma natural.