HashMap es una de las estructuras de datos más utilizadas por los desarrolladores Java para gestionar colecciones de pares clave-valor. Con cada actualización del Kit de Desarrollo de Java (JDK), la implementación subyacente de HashMap ha evolucionado. JDK 8 introdujo optimizaciones significativas, como la incorporación de la estructura de datos de árbol rojo-negro y mejoras en el mecanismo de redimensionamiento. Este artículo explora la arquitectura y el funcionamiento de HashMap, destacando las diferencias clave entre JDK 7 y JDK 8.

Clases de Implementación del Interfaz Map

Java define el interfaz java.util.Map para las estructuras de datos de tipo mapa. Las cuatro implementaciones más comunes son HashMap, Hashtable, LinkedHashMap y TreeMap. A continuación, se describen sus características principales:

• HashMap: Almacena datos basándose en el valor hashCode de la clave, lo que permite una recuperación rápida en la mayoría de los casos. Sin embargo, no garantiza un orden de iteración predecible. Permite una única clave null y múltiples valores null. No es seguro para hilos (no thread-safe), lo que significa que múltiples hilos que escriban concurrentemente podrían causar inconsistencias de datos. Para la seguridad de hilos, se puede usar Collections.synchronizedMap o, preferiblemente, ConcurrentHashMap.
• Hashtable: Una clase legada que ofrece funcionalidades similares a HashMap, pero es una subclase de Dictionary y es segura para hilos. Sin embargo, su concurrencia es inferior a la de ConcurrentHashMap debido a que utiliza un bloqueo único para toda la tabla. No se recomienda su uso en código nuevo; HashMap es una alternativa para entornos no concurrentes y ConcurrentHashMap para entornos concurrentes.
• LinkedHashMap: Extiende HashMap, manteniendo el orden de inserción de las entradas. Esto significa que al iterar sobre un LinkedHashMap, los elementos se devuelven en el orden en que fueron añadidos. También puede configurarse para ordenar por orden de acceso.
• TreeMap: Implementa el interfaz SortedMap, lo que le permite mantener sus entradas ordenadas según las claves. Por defecto, ordena las claves en orden ascendente, pero se puede especificar un comparador personalizado. Para usar TreeMap, las claves deben implementar el interfaz Comparable o se debe proporcionar un Comparator en el constructor, de lo contrario, se lanzará una excepción java.lang.ClassCastException.

Para todas estas implementaciones de Map, es crucial que las claves sean objetos inmutables, es decir, que su valor hashCode no cambie después de su creación. Si el hashCode de una clave varía, el mapa podría no ser capaz de localizar correctamente la entrada.

Arquitectura Interna de HashMap

Para comprender HashMap, es fundamental conocer su estructura de almacenamiento y sus mecanismos operativos. En esencia, HashMap se implementa como una combinación de un array (también llamado cubo o bucket), listas enlazadas y, a partir de JDK 8, árboles rojo-negro.

Estructura de Almacenamiento: Campos Clave

La estructura fundamental de HashMap reside en su campo Node[] table, que es un array de nodos. Cada nodo es una entrada (par clave-valor) dentro del mapa. La definición de la clase Node en JDK 8 es la siguiente:

static class EntryNode<K,V> implements Map.Entry<K,V> {
    final int hashVal;    // Hash calculado para la clave
    final K entryKey;     // La clave de la entrada
    V entryValue;         // El valor asociado a la clave
    EntryNode<K,V> nextNode; // Referencia al siguiente nodo en caso de colisión (lista enlazada)

    EntryNode(int hash, K key, V value, EntryNode<K,V> next) {
        this.hashVal = hash;
        this.entryKey = key;
        this.entryValue = value;
        this.nextNode = next;
    }

    public final K getKey(){ return entryKey; }
    public final V getValue() { return entryValue; }
    public final String toString() { return entryKey + "=" + entryValue; }
    public final int hashCode() { return Objects.hashCode(entryKey) ^ Objects.hashCode(entryValue); }
    public final V setValue(V newValue) {
        V oldVal = entryValue;
        entryValue = newValue;
        return oldVal;
    }
    public final boolean equals(Object other) {
        if (other == this) return true;
        if (!(other instanceof Map.Entry)) return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)other;
        return Objects.equals(entryKey, e.getKey()) &&
               Objects.equals(entryValue, e.getValue());
    }
}

Cada objeto EntryNode representa un par clave-valor. HashMap utiliza una técnica de resolución de colisiones conocida como "encadenamiento", donde múltiples entradas que tienen el mismo índice de hash se almacenan en una lista enlazada en esa posición del array.

Cuando se inserta un par clave-valor (por ejemplo, map.put("Ejemplo", "Valor")), el sistema primero invoca el método hashCode() de la clave ("Ejemplo") para obtener su valor hash. Luego, este valor se procesa mediante un algoritmo de dispersión para determinar la posición exacta en el array table. Si dos claves diferentes resultan en la misma posición (una colisión de hash), se añaden a la lista enlazada en ese índice. Un algoritmo de hash eficiente y una adecuada gestión de las colisiones son cruciales para el rendimiento de HashMap.

Campos de Configuración Esenciales

Los siguientes campos son fundamentales para el comportamiento de HashMap, especialmente durante la inicialización y el redimensionamiento:

• int currentThreshold (anteriormente threshold): El número máximo de elementos que HashMap puede contener antes de que se redimensione. Se calcula como capacidad * loadFactor.
• final float loadFactor: El factor de carga (por defecto 0.75). Este valor determina cuándo se debe redimensionar la tabla hash. Un factor de carga más alto reduce el espacio, pero aumenta las colisiones; uno más bajo aumenta el espacio, pero reduce las colisiones. El valor predeterminado de 0.75 busca un equilibrio entre el uso de memoria y el rendimiento.
• int modificationsCount (anteriormente modCount): Cuenta el número de veces que la estructura interna del HashMap ha sido modificada (por ejemplo, añadiendo o eliminando pares clave-valor). Se utiliza para el mecanismo de "fallo rápido" de los iteradores.
• int currentSize (anteriormente size): El número real de pares clave-valor almacenados actualmente en el HashMap.

Es importante destacar que la longitud del array de la tabla hash (Node[] table) debe ser siempre una potencia de 2 (por ejemplo, 16, 32, 64). Este diseño no convencional (ya que los números primos son a menudo preferidos para las tablas hash) permite optimizaciones de rendimiento en las operaciones de módulo y redimensionamiento.

Optimización con Árboles Rojo-Negro en JDK 8

A pesar de los algoritmos de hash y los factores de carga bien diseñados, las listas enlazadas en los cubos pueden volverse demasiado largas, degradando seriamente el rendimiento de HashMap (cambiando la complejidad de tiempo de O(1) a O(N) en el peor de los casos). Para mitigar esto, JDK 8 introdujo árboles rojo-negro. Si una lista enlazada en un cubo excede una cierta longitud (por defecto 8), se convierte en un árbol rojo-negro. Esto reduce la complejidad de tiempo para operaciones de búsqueda, inserción y eliminación en ese cubo de O(N) a O(log N).

Funcionamiento Principle: Métodos Clave

El corazón de HashMap radica en sus métodos, que gestionan la inserción, recuperación y eliminación de datos. Analicemos cómo se determinan las posiciones de índice, el proceso de inserción (put) y el mecanismo de redimensionamiento.

1. Determinación de la Posición del Índice

Localizar la posición correcta en el array para una clave es el primer paso crucial en cualquier operación de HashMap. La eficiencia de esta localización depende directamente del rendimiento del algoritmo de hash. El algoritmo de hashing en HashMap consta de tres pasos fundamentales:

// Paso 1 y 2: Obtener el hashCode y aplicar operación de bit alto
static final int computeHash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// Paso 3: Operación de módulo para el índice del array (conceptual)
// (equivalente a 'h & (arrayLength - 1)' cuando arrayLength es potencia de 2)
static int calculateIndex(int hash, int arrayLength) {
    return hash & (arrayLength - 1);
}

1. Obtener hashCode(): El método hashCode() de la clave genera un número entero.
2. Operación de Bits Altos: El resultado del hashCode() se somete a una operación XOR con sus propios bits superiores (h ^ (h >>> 16)). Esto asegura que incluso en arrays pequeños, los bits altos del hash, que de otro modo podrían no influir en el cálculo del índice (ya que solo se usan los bits bajos en la operación final), contribuyan a la dispersión de las claves.
3. Operación de Módulo (& (longitud - 1)): Finalmente, el hash modificado se combina con la longitud del array menos uno (& (length - 1)). Dado que la longitud del array es siempre una potencia de 2, esta operación bit a bit es un equivalente más rápido de la operación de módulo (%), distribuyendo la clave en una de las posiciones del array.

2. Análisis del Método put

El método put(K key, V value) es central para la funcionalidad de HashMap. Su proceso se puede resumir en los siguientes pasos:

1. Si la tabla de nodos (table) está vacía o nula, se inicializa o redimensiona.
2. Se calcula el hash para la clave y se determina su índice en el array. Si la posición del índice está vacía (table[i] == null), se crea un nuevo nodo y se inserta directamente.
3. Si la posición del índice no está vacía, se verifica si el primer elemento en esa posición es idéntico a la clave (misma hash y equals()). Si es así, se sobrescribe el valor.
4. Si el primer elemento no es idéntico, se verifica si la estructura en esa posición es un árbol rojo-negro (instanceof TreeNode). Si lo es, la inserción se realiza dentro del árbol.
5. Si es una lista enlazada, se recorre la lista. Si se encuentra una clave existente, su valor se sobrescribe. Si la clave no existe, se añade un nuevo nodo al final de la lista. Durante este recorrido, si la longitud de la lista excede el umbral de "arborización" (TREEIFY_THRESHOLD, por defecto 8), la lista se convierte en un árbol rojo-negro.
6. Después de una inserción exitosa, si el número total de elementos (size) excede el threshold, HashMap se redimensiona.

A continuación, una versión simplificada del método putVal de JDK 8:

final V insertValue(int hash, K key, V value, boolean replaceIfExists, boolean evict) {
    EntryNode<K,V>[] currentTable; EntryNode<K,V> currentEntry; int tableLength, index;
    // Paso 1: Si la tabla está vacía o es nula, se inicializa (resize)
    if ((currentTable = table) == null || (tableLength = currentTable.length) == 0)
        tableLength = (currentTable = resizeTable()).length;

    // Paso 2: Calcular el índice y manejar el caso de bucket vacío
    if ((currentEntry = currentTable[index = (tableLength - 1) & hash]) == null)
        currentTable[index] = new EntryNode<>(hash, key, value, null);
    else {
        EntryNode<K,V> existingEntry; K existingKey;
        // Paso 3: La clave ya existe en el primer nodo del bucket
        if (currentEntry.hashVal == hash &&
            ((existingKey = currentEntry.entryKey) == key || (key != null && key.equals(existingKey))))
            existingEntry = currentEntry;
        // Paso 4: El bucket es un árbol rojo-negro
        else if (currentEntry instanceof TreeNode) // Suponiendo TreeNode extendiendo EntryNode
            existingEntry = ((TreeNode<K,V>)currentEntry).putTreeVal(this, currentTable, hash, key, value);
        // Paso 5: El bucket es una lista enlazada
        else {
            for (int counter = 0; ; ++counter) {
                if ((existingEntry = currentEntry.nextNode) == null) {
                    currentEntry.nextNode = new EntryNode<>(hash, key, value, null);
                    if (counter >= TREEIFY_THRESHOLD - 1) // -1 porque el 1er nodo no cuenta en el bucle
                        treeifyBin(currentTable, hash); // Convertir a árbol rojo-negro
                    break;
                }
                // Si la clave ya existe en la lista, se rompe para sobrescribir
                if (existingEntry.hashVal == hash &&
                    ((existingKey = existingEntry.entryKey) == key || (key != null && key.equals(existingKey))))
                    break;
                currentEntry = existingEntry;
            }
        }

        if (existingEntry != null) { // Si se encontró una entrada existente para la clave
            V oldVal = existingEntry.entryValue;
            if (!replaceIfExists || oldVal == null)
                existingEntry.entryValue = value; // Se sobrescribe el valor
            // ... (Llamadas a métodos afterNodeAccess, si existieran)
            return oldVal;
        }
    }

    modificationsCount++; // Incrementar contador de modificaciones
    // Paso 6: Si el tamaño excede el umbral, se redimensiona
    if (++currentSize > currentThreshold)
        resizeTable();
    // ... (Llamadas a métodos afterNodeInsertion, si existieran)
    return null;
}

3. Mecanismo de Redimensionamiento (resize)

El redimensionamiento es la operación de expandir el array subyacente de HashMap cuando se alcanza la capacidad máxima. Esto implica crear un nuevo array de mayor tamaño (generalmente el doble del anterior) y reubicando todas las entradas del array antiguo al nuevo. En JDK 8, este proceso fue optimizado significativamente.

El código de redimensionamiento en JDK 8 es complejo debido a la gestión de árboles rojo-negro, pero la lógica central para las listas enlazadas es brillante. Dado que la nueva capacidad es siempre el doble de la antigua, la reubicación de un nodo se simplifica. El nuevo índice de un nodo será o bien el mismo que su índice anterior, o bien su índice anterior más la antigua capacidad (oldCap). Esto se determina simplemente observando un bit específico en el hash del nodo (el bit correspondiente a la antigua capacidad).

• Si el bit es 0, el nodo permanece en su índice original en la nueva tabla.
• Si el bit es 1, el nodo se mueve a original_index + oldCap en la nueva tabla.

Esta optimización evita recalcular el hash completo para cada nodo, lo que mejora considerablemente el rendimiento del redimensionamiento. Además, a diferencia de JDK 7, JDK 8 mantiene el orden relativo de los elementos dentro de las listas enlazadas (no invierte las listas durante el rehash).

final EntryNode<K,V>[] resizeTable() {
    EntryNode<K,V>[] oldArray = table;
    int oldArrayCapacity = (oldArray == null) ? 0 : oldArray.length;
    int oldThresholdVal = currentThreshold;
    int newArrayCapacity = 0, newThresholdVal = 0;

    if (oldArrayCapacity > 0) {
        if (oldArrayCapacity >= MAXIMUM_CAPACITY) { // Si ya es la capacidad máxima, no se expande
            currentThreshold = Integer.MAX_VALUE;
            return oldArray;
        }
        // Duplicar la capacidad si no se ha alcanzado el máximo
        else if ((newArrayCapacity = oldArrayCapacity << 1) < MAXIMUM_CAPACITY &&
                 oldArrayCapacity >= DEFAULT_INITIAL_CAPACITY)
            newThresholdVal = oldThresholdVal << 1; // Duplicar el umbral
    }
    else if (oldThresholdVal > 0) // Capacidad inicial especificada en el umbral
        newArrayCapacity = oldThresholdVal;
    else {               // Usar valores predeterminados
        newArrayCapacity = DEFAULT_INITIAL_CAPACITY;
        newThresholdVal = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    if (newThresholdVal == 0) { // Calcular nuevo umbral si no se calculó antes
        float tempFactor = (float)newArrayCapacity * loadFactor;
        newThresholdVal = (newArrayCapacity < MAXIMUM_CAPACITY && tempFactor < (float)MAXIMUM_CAPACITY ?
                           (int)tempFactor : Integer.MAX_VALUE);
    }
    currentThreshold = newThresholdVal; // Actualizar umbral

    @SuppressWarnings({"rawtypes","unchecked"})
    EntryNode<K,V>[] newArray = (EntryNode<K,V>[])new EntryNode[newArrayCapacity];
    table = newArray; // Asignar la nueva tabla

    if (oldArray != null) {
        for (int j = 0; j < oldArrayCapacity; ++j) {
            EntryNode<K,V> entry;
            if ((entry = oldArray[j]) != null) {
                oldArray[j] = null; // Liberar referencia en la tabla antigua
                if (entry.nextNode == null) // Nodo único en el bucket
                    newArray[entry.hashVal & (newArrayCapacity - 1)] = entry;
                else if (entry instanceof TreeNode) // Es un árbol rojo-negro
                    ((TreeNode<K,V>)entry).split(this, newArray, j, oldArrayCapacity);
                else { // Es una lista enlazada, aplicar la optimización de rehash
                    EntryNode<K,V> lowHead = null, lowTail = null; // Para nodos que mantienen su índice
                    EntryNode<K,V> highHead = null, highTail = null; // Para nodos que se mueven a + oldCap
                    EntryNode<K,V> nextNode;
                    do {
                        nextNode = entry.nextNode;
                        if ((entry.hashVal & oldArrayCapacity) == 0) { // Bit de oldCap es 0 -> mismo índice
                            if (lowTail == null)
                                lowHead = entry;
                            else
                                lowTail.nextNode = entry;
                            lowTail = entry;
                        } else { // Bit de oldCap es 1 -> índice + oldCap
                            if (highTail == null)
                                highHead = entry;
                            else
                                highTail.nextNode = entry;
                            highTail = entry;
                        }
                    } while ((entry = nextNode) != null);

                    if (lowTail != null) {
                        lowTail.nextNode = null;
                        newArray[j] = lowHead; // Asignar lista "low" al índice original
                    }
                    if (highTail != null) {
                        highTail.nextNode = null;
                        newArray[j + oldArrayCapacity] = highHead; // Asignar lista "high" al nuevo índice
                    }
                }
            }
        }
    }
    return newArray;
}

Seguridad de Hilos y Concurrencia

Es crucial entender que HashMap no es seguro para hilos. El uso de HashMap en un entorno multihilo sin sincronización externa puede llevar a condiciones de carrera y resultados impredecibles. Un ejemplo clásico en JDK 7 era la posibilidad de crear un bucle infinito durante una operación concurrente de resize(). Esto ocurría porque múltiples hilos podían modificar las listas enlazadas de manera entrealzada, formando un ciclo. Aunque JDK 8 mitigó este problema con la reestructuración del resize() para evitar la inversión de la lista, HashMap sigue siendo intrínsecamente no seguro para hilos y no debe usarse en escenarios concurrentes sin una sincronización explícita, que a menudo conlleva una sobrecarga significativa. Para escenarios concurrentes, ConcurrentHashMap es la solución preferida, diseñada específicamente para un alto rendimiento en entornos multihilo.

Comparativa de Rendimiento: JDK 8 vs. JDK 7

Las mejoras introducidas en JDK 8, especialmente los árboles rojo-negro y las optimizaciones de redimensionamiento, resultan en un rendimiento superior en la mayoría de los casos. La complejidad temporal de getKey puede variar de O(1) (para una dispersión hash perfecta) a O(log N) (cuando se usan árboles rojo-negro) o, en el peor de los casos en JDK 7, O(N) (con listas enlazadas muy largas).

Escenario 1: Claves con Distribución Hash Uniforme

Consideremos una clase KeyData con una buena implementación de hashCode() donde cada instancia produce un hash único:

class KeyData implements Comparable<KeyData> {
    private final int value;

    KeyData(int value) {
        this.value = value;
    }

    @Override
    public int compareTo(KeyData other) {
        return Integer.compare(this.value, other.value);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass())
            return false;
        KeyData key = (KeyData) o;
        return value == key.value;
    }

    @Override
    public int hashCode() {
        return value; // Excelente hash: cada valor es único
    }
}

Para la prueba, usamos una utilidad para cachear instancias de KeyData y evitar la creación repetida de objetos:

public class KeyFactory {
    public static final int MAX_KEYS_COUNT = 10_000_000;
    private static final KeyData[] CACHED_KEYS = new KeyData[MAX_KEYS_COUNT];

    static {
        for (int i = 0; i < MAX_KEYS_COUNT; ++i) {
            CACHED_KEYS[i] = new KeyData(i);
        }
    }

    public static KeyData from(int val) {
        return CACHED_KEYS[val];
    }
}

Un método de prueba para medir el tiempo de acceso:

public class HashMapPerformance {
    static void executeTest(int mapSize) {
        HashMap<KeyData, Integer> testMap = new HashMap<>(mapSize);
        for (int i = 0; i < mapSize; ++i) {
            testMap.put(KeyFactory.from(i), i);
        }

        long startTime = System.nanoTime();
        for (int i = 0; i < mapSize; i++) {
            testMap.get(KeyFactory.from(i));
        }
        long endTime = System.nanoTime();
        System.out.println("Tiempo para size " + mapSize + ": " + (endTime - startTime) + " ns");
    }

    public static void main(String[] args) {
        for(int i = 10; i <= 10_000_000; i *= 10){
            executeTest(i);
        }
    }
}

En este escenario, JDK 8 generalmente supera a JDK 7 en un 15% o más, e incluso en ciertos tamaños, la mejora puede ser superior al 100%. Dado que la distribución hash es uniforme, la ventaja de los árboles rojo-negro no es tan pronunciada, pero otras optimizaciones contribuyen a la mejora.

Escenario 2: Claves con Distribución Hash Muy Desigual

Consideremos ahora el peor escenario, donde todas las claves devuelven el mismo hashCode. Esto simula un hash muy pobre, donde todas las entradas colisionan en el mismo cubo, formando una lista enlazada muy larga (o un árbol rojo-negro en JDK 8).

class KeyData implements Comparable<KeyData> {
    // ... (campos y otros métodos como equals, compareTo)

    @Override
    public int hashCode() {
        return 1; // Todas las claves colisionan en el mismo hash
    }
}

Al ejecutar las pruebas con esta implementación de hashCode(), los resultados son drásticamente diferentes. Mientras que en JDK 7 el tiempo de acceso aumenta linealmente con el tamaño del mapa (O(N)), en JDK 8 el rendimiento es significativamente mejor y tiende a un crecimiento logarítmico (O(log N)) una vez que la lista enlazada se convierte en un árbol rojo-negro. Esto demuestra la importancia crítica de los árboles rojo-negro de JDK 8 para mitigar la degradación del rendimiento en situaciones de alta colisión.

Conclusiones Clave

• El redimensionamiento es una operación costosa. Para optimizar el rendimiento, es aconsejable estimar el tamaño del HashMap y proporcionar una capacidad inicial adecuada en el constructor para evitar redimensionamientos frecuentes.
• El factor de carga (loadFactor) es configurable, e incluso puede ser mayor que 1. Sin embargo, no se recomienda modificarlo a menos que se trate de un caso de uso muy específico. El valor predeterminado de 0.75 es un buen equilibrio entre uso de memoria y rendimiento.
• HashMap no es seguro para hilos. En entornos concurrentes, se debe utilizar ConcurrentHashMap para garantizar la integridad y el rendimiento de los datos.
• La introducción de árboles rojo-negro en JDK 8 ha optimizado significativamente el rendimiento de HashMap, especialmente en escenarios con muchas colisiones.
• La actualización a JDK 8 (o versiones posteriores) es altamente recomendable, ya que las mejoras en HashMap son solo una pequeña parte de las optimizaciones generales en el rendimiento y la funcionalidad del lenguaje.