Introducción a LinkedHashMap

La clase LinkedHashMap en Java extiende HashMap y añade una característica fundamental: garantiza que el orden de iteración de los eleemntos coincida con el orden en que fueron insertados (o accedidos, dependiendo de su configuración). Para comprender su funcionamiento interno, es esencial tener un conocimiento previo de la implementación de HashMap.

Arquitectura y Modelo de Datos

Para mantener el orden de inserción sin comprometer el rendimiento de las operaciones de tabla hash, LinkedHashMap modifica la estructura de los nodos. Mientras que HashMap utiliza nodos básicos enlazados en una sola dirección dentro de cada cubo (bucket), LinkedHashMap introduce una lista doblemente enlazada que atraviesa todos los nodos del mapa.

Cada nodo, representado por la clase interna Entry, incorpora dos punteros adicionales:

• previousNode: Apunta al nodo insertado previamente.
• nextNode: Apunta al nodo insertado posteriormente.

Es crucial no confundir estos punteros con los utilizados para resolver colisiones en los cubos. Los punteros de la lista doblemente enlazada mantienen un orden global de todos los elementos, mientras que los punteros de los cubos gestionan las colisiones locales.

La estructura mantiene dos referencias principales:

• head: Referencia al nodo más antiguo (el primero en ser insertado).
• tail: Referencia al nodo más reciente (el último en ser insertado).

Cuando se añade un nuevo elemento, se enlaza al final de la lista mediante el puntero tail. Durante la iteración, el proceso comienza en head y avanza a través de los punteros nextNode, asegurando así el orden cronológico.

Estructura Interna y Variables de Instancia

A continuación, se detalla la estructura de la clase y sus variables principales. Se incluye la variable accessOrder, que permite alternar entre el orden de inserción y el orden de acceso.

public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V> {
    
    static class Entry<K, V> extends HashMap.Node<K, V> {
        Entry<K, V> previousNode;
        Entry<K, V> nextNode;

        Entry(int hashValue, K key, V value, Node<K, V> nextBucketNode) {
            super(hashValue, key, value, nextBucketNode);
        }
    }

    transient Entry<K, V> head;
    transient Entry<K, V> tail;
    final boolean accessOrder;
}

Si accessOrder se establece en true, el orden de iteración reflejará el orden en que las claves fueron accedidas por última vez (mediante operaciones get o put). Si es false, reflejará estrictamente el orden de inserción.

Patrón Template y Métodos Gancho

La integración con la superclase se logra mediante el Patrón de Diseño Template Method. HashMap define el esqueleto de las operaciones principales (como put y remove) y expone métodos gancho (hook methods) que LinkedHashMap sobrescribe para actualizar su lista doblemente enlazada.

// Ejecutado después de eliminar un nodo
void afterNodeRemoval(HashMap.Node<K, V> removedNode) {
    Entry<K, V> current = (Entry<K, V>) removedNode;
    Entry<K, V> prev = current.previousNode;
    Entry<K, V> next = current.nextNode;
    
    current.previousNode = current.nextNode = null;
    
    if (prev == null) {
        head = next;
    } else {
        prev.nextNode = next;
    }
    
    if (next == null) {
        tail = prev;
    } else {
        next.previousNode = prev;
    }
}

// Ejecutado después de insertar un nuevo nodo
void afterNodeInsertion(boolean mayEvict) {
    Entry<K, V> oldestNode;
    if (mayEvict && (oldestNode = head) != null && removeEldestEntry(oldestNode)) {
        K oldestKey = oldestNode.key;
        removeNode(hash(oldestKey), oldestKey, null, false, true);
    }
}

// Ejecutado después de acceder a un nodo existente
void afterNodeAccess(HashMap.Node<K, V> accessedNode) {
    Entry<K, V> lastNode;
    if (accessOrder && (lastNode = tail) != accessedNode) {
        Entry<K, V> current = (Entry<K, V>) accessedNode;
        Entry<K, V> prev = current.previousNode;
        Entry<K, V> next = current.nextNode;
        
        current.nextNode = null;
        if (prev == null) {
            head = next;
        } else {
            prev.nextNode = next;
        }
        
        if (next != null) {
            next.previousNode = prev;
        } else {
            lastNode = prev;
        }
        
        if (lastNode == null) {
            head = current;
        } else {
            current.previousNode = lastNode;
            lastNode.nextNode = current;
        }
        tail = current;
        ++modCount;
    }
}

Implementación de Caché LRU

El método afterNodeInsertion invoca a removeEldestEntry. Por defecto, este método retorna false, lo que significa que el mapa crece indefinidamente. Sin embargo, al sobrescribirlo, podemos implementar fácilmente una caché con política de reemplazo LRU (Least Recently Used) o FIFO.

El siguiente ejemplo muestra cómo crear una caché LRU personalizada limitando la capacidad máxima del mapa:

public class CustomLruCache<K, V> extends LinkedHashMap<K, V> {
    
    private final int capacity;

    public CustomLruCache(int maxCapacity) {
        // El tercer parámetro (accessOrder) debe ser true para un comportamiento LRU real
        super(maxCapacity, 0.75f, true);
        this.capacity = maxCapacity;
    }

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

Rendimiento del Iterador

El iterador de LinkedHashMap recorre la lista doblemente enlazada comenzando desde head. Esto le otorga una ventaja de rendimiento sobre el iterador de HashMap. Mientras que HashMap debe recorrer toda la tabla subyacente (incluyendo cubos vacíos), el tiempo de iteración de LinkedHashMap es estrictamente proporcional al número real de elementos (size), independientemente de la capacidad de la tabla subyacente.

Relación con LinkedHashSet

De manera similar a cómo HashSet está respaldado por una instancia de HashMap, LinkedHashSet está respaldado internamente por una instancia de LinkedHashMap. Por lo tanto, LinkedHashSet hereda automáticamente la capacidad de mantener el orden de inserción de sus elementos, aplicando exactamente los mismos principios de listas doblemente enlazadas descritos anteriormente, pero adaptados para una colección de elementos únicos sin valores asociados.