El HashMap de Java es una de las estructuras de datos más fundamentales y utilizadas para almacenar pares clave-valor. Internamente, organiza estos pares, conocidos como entradas o nodos, en un array. Cada posición del array, inicialmente nula, puede albergar una única entrada o servir como punto de partida para una lista enlazada o un árbol, resolviendo así las colisiones de hash. Su diseño permite la recuperación de elementos con una complejidad temporal promedio de O(1).

Evolución de HashMap

JDK 1.7: Array de Nodos y Listas Enlazadas

En la versión de JDK 1.7, HashMap se implementaba principalmente como un array de entradas (Entry[]), donde cada Entry representaba un par clave-valor y contenía una referencia al siguiente Entry en caso de colisión, formando así una lista enlazada.

Inicialización

Al instanciar un HashMap, se crea por defecto un array de Entry con una longitud inicial de 16. Si se conoce aproximadamente el volumen de datos, es recomendable especificar una capacidad inicial en el constructor para minimizar las operaciones de redimensionamiento y mejorar el rendimiento.

Cálculo de la Posición y Dispersión del Hash

Para determinar la posición de una clave en el array, HashMap primero obtiene el hashCode() del objeto clave. Luego, aplica un proceso de "dispersión" o "perturbación" para distribuir mejor los valores de hash y reducir la probabilidad de colisiones.

Este proceso en JDK 1.7 implicaba una secuencia de nueve operaciones: cuatro desplazamientos de bits y cinco operaciones XOR. El objetivo era que cualquier cambio en un bit del hash original influyera significativamente en el resultado final, optimizando la distribución.

// Obtenemos el código hash original de la clave
int codigoHashOriginal = clave.hashCode();

// Aplicamos operaciones de dispersión para mejorar la distribución y reducir colisiones
// Esto mezcla bits del hash original
int hashDisperso = codigoHashOriginal ^ (codigoHashOriginal >>> 20) ^ (codigoHashOriginal >>> 12);
return hashDisperso ^ (hashDisperso >>> 7) ^ (hashDisperso >>> 4);

Una vez obtenido el hash disperso, se calcula el índice dentro del array:

// El hash es el resultado de la función de dispersión, y capacidad es el tamaño actual del array.
// Esta operación AND es una forma eficiente de calcular el módulo cuando la capacidad es potencia de 2.
int indiceCalculado = hashDispersoFinal & (capacidadTabla - 1);

Resolución de Colisiones

Cuando diferentes claves producen el mismo índice (colisión), los nuevos nodos se insertan al principio de la lista enlazada existente en esa posición (estrategia de "inserción por cabecera").

Mecanismo de Redimensionamiento

El factor de carga por defecto es 0.75. Cuando el número de elementos supera el 75% de la capacidad actual del array (0.75 * capacidad), HashMap inicia una operación de redimensionamiento. La nueva capacidad siempre será el doble de la anterior.

Durante el redimensionamiento, HashMap debe reubicar todos los datos del array antiguo al nuevo. No es necesario recalcular el hash de las claves, pero sí se deben recalcular los índices de todos los elementos basándose en la nueva capacidad. Debido a la "inserción por cabecera" utilizada durante esta reubicación, el orden de los elementos en las listas enlazadas puede invertirse. Una vez reubicados, se inserta el nuevo elemento que desencadenó la operación.

JDK 1.8: Array de Nodos, Listas Enlazadas y Árboles Rojo-Negro

JDK 1.8 introduce una mejora significativa: la estructura subyacente de HashMap se compone de un array de nodos, donde cada nodo puede ser el inicio de una lista enlazada o, bajo ciertas condiciones, de un árbol rojo-negro. Cada Node contiene los campos key, value, hash y next. El campo hash almacena una versión dispersa del hashCode() de la clave, y next enlaza a otros nodos en caso de colisión.

Inicialización Diferida

A diferencia de JDK 1.7, la inicialización del array principal del HashMap en JDK 1.8 es diferida. El array de 16 elementos se crea únicamente en la primera llamada al método put().

Cálculo del Hash

Si la clave no es nula, se calcula su hashCode(). Este valor se mezcla con un desplazamiento de sus propios bits superiores (los 16 bits más significativos se combinan con los 16 bits menos significativos mediante una operación XOR). Esto es un proceso de dispersión más simple y eficiente que en JDK 1.7.

static final int calcularHash(Object clave) {
   int h;
   // Si la clave es nula, su hash es 0.
   // De lo contrario, se calcula el hash original y se mezcla con sus bits superiores
   // para mejorar la distribución en el array, especialmente con tamaños pequeños.
   return (clave == null) ? 0 : (h = clave.hashCode()) ^ (h >>> 16);
}

El cálculo del índice es el mismo que en JDK 1.7:

indice = (hashCalculado & (capacidadTabla - 1));

Resolución de Colisiones y Conversión a Árbol

Cuando hay colisiones, los nuevos nodos se añaden al final de la lista enlazada (estrategia de "inserción por cola"). Este método evita los problemas de bucles infinitos que podían surgir en entornos multihilo con la "inserción por cabecera" de JDK 1.7.

Una característica clave de JDK 1.8 es la "estructuración en árbol". Para mitigar la degradación del rendimiento de las listas enlazadas (O(n)) cuando son muy largas, si una lista enlazada en un bucket específico supera una longitud de 8 nodos Y la capacidad total del array es mayor a 64, la lista se transforma en un árbol rojo-negro. Los árboles rojo-negro ofrecen una eficiencia de búsqueda, inserción y eliminación de O(log n).

Mecanismo de Redimensionamiento Optimizado

El factor de carga sigue siendo 0.75. Cuando el tamaño de HashMap excede este umbral, se duplica su capacidad. El proceso de migración de datos ha sido optimizado en JDK 1.8:

• Nuevo Cálculo de Posición: Los nodos no necesitan recalcular completamente su hash. Dada la duplciación de la capacidad, la nueva posición de un nodo será su índice actual o su índice actual más la antigua capacidad. Esto se determina fácilmente mediante una operación AND bit a bit entre el hash del nodo y la antigua capacidad:
  • Si el resultado es 0, el nodo permanece en su índice original.
  • Si el resultado es 1, el nodo se mueve a índice_original + antigua_capacidad.
• Migración de Datos (Inserción por Cola):
  1. Si un bucket está vacío, permanece vacío.
  2. Si un bucket contiene un único nodo, se reubica directamente en su nueva posición.
  3. Si un bucket es una lista enlazada, se divide en dos nuevas listas enlazadas (una para la posición original, otra para posición_original + antigua_capacidad), utilizando la regla de cálculo de nueva posición. Ambas listas se construyen usando "inserción por cola", manteniendo el orden relativo de los elementos.
  4. Si un bucket es un árbol rojo-negro, también se divide en dos árboles o dos listas enlazadas, dependiendo del número de nodos resultantes en cada partición. Si una partición tiene 6 o menos nodos, se degrada a una lista enlazada.

Operación get(key) en JDK 1.8

Para recuperar un valor, HashMap calcula el hash de la clave, y luego el índice. A partir de ahí, busca en el bucket correspondiente:

public V obtener(Object clave) {
   Node<k> nodoEncontrado;
   // Calcula el hash y busca el nodo, si existe, devuelve su valor.
   return (nodoEncontrado = obtenerNodoInterno(calcularHash(clave), clave)) == null ? null : nodoEncontrado.value;
}

final Node<k> obtenerNodoInterno(int hashBuscado, Object claveBuscada) {
   Node<k>[] tablaArray;
   Node<k> primerElemento, elementoActual;
   int longitudArray;
   K claveEnNodo;

   // Se verifica que la tabla esté inicializada, no vacía y que el bucket no esté vacío.
   if ((tablaArray = tabla) != null && (longitudArray = tablaArray.length) > 0 &&
       (primerElemento = tablaArray[(longitudArray - 1) & hashBuscado]) != null) {

       // Primero, se compara el nodo cabecera del bucket.
       if (primerElemento.hash == hashBuscado &&
           ((claveEnNodo = primerElemento.key) == claveBuscada ||
            (claveBuscada != null && claveBuscada.equals(claveEnNodo)))) {
           return primerElemento;
       }

       // Si hay más elementos en el bucket, se procede a buscar en la estructura.
       if ((elementoActual = primerElemento.next) != null) {
           if (primerElemento instanceof TreeNode)
               // Si es un árbol rojo-negro, se delega la búsqueda al método del árbol.
               return ((TreeNode<k>)primerElemento).buscarEnArbol(hashBuscado, claveBuscada);
           do {
               // Si es una lista enlazada, se recorre comparando hashes y claves.
               if (elementoActual.hash == hashBuscado &&
                   ((claveEnNodo = elementoActual.key) == claveBuscada ||
                    (claveBuscada != null && claveBuscada.equals(claveEnNodo)))) {
                   return elementoActual;
               }
           } while ((elementoActual = elementoActual.next) != null);
       }
   }
   return null; // El nodo no fue encontrado.
}
</k></k></k></k></k>

Operación put(key, value) en JDK 1.8

El método put() gestiona la inserción o actualización de pares clave-valor:

public V poner(K clave, V valor) {
   return ponerValorInterno(calcularHash(clave), clave, valor, false, true);
}

final V ponerValorInterno(int codigoHash, K clave, V valor, boolean soloSiAusente, boolean forzarEviccion) {
   Node<k>[] arrayNodos;
   Node<k> nodoEnBucket;
   int longitudArray, indiceBucket;

   // Si la tabla no está inicializada o está vacía, se inicializa/redimensiona.
   if ((arrayNodos = tabla) == null || (longitudArray = arrayNodos.length) == 0) {
       longitudArray = (arrayNodos = redimensionar()).length;
   }

   // Se calcula el índice. Si el bucket está vacío, se inserta directamente un nuevo nodo.
   if ((nodoEnBucket = arrayNodos[indiceBucket = (longitudArray - 1) & codigoHash]) == null) {
       arrayNodos[indiceBucket] = crearNodo(codigoHash, clave, valor, null);
   } else {
       // Colisión o clave existente.
       Node<k> nodoExistente;
       K claveActual;

       // Comprueba si el primer nodo del bucket ya contiene la clave.
       if (nodoEnBucket.hash == codigoHash &&
           ((claveActual = nodoEnBucket.key) == clave || (clave != null && clave.equals(claveActual)))) {
           nodoExistente = nodoEnBucket;
       } else if (nodoEnBucket instanceof TreeNode) {
           // Si es un árbol, delega la inserción al método del árbol.
           nodoExistente = ((TreeNode<k>)nodoEnBucket).insertarEnArbol(this, arrayNodos, codigoHash, clave, valor);
       } else {
           // Es una lista enlazada, se recorre.
           for (int contadorElementos = 0; ; ++contadorElementos) {
               if ((nodoExistente = nodoEnBucket.next) == null) {
                   // Se llega al final, se inserta el nuevo nodo por cola.
                   nodoEnBucket.next = crearNodo(codigoHash, clave, valor, null);
                   // Si la lista excede el umbral, se convierte a árbol.
                   if (contadorElementos >= UMBRAL_ARBOL - 1) {
                       convertirBucketEnArbol(arrayNodos, codigoHash);
                   }
                   break;
               }
               // Si se encuentra la clave, se sale del bucle.
               if (nodoExistente.hash == codigoHash &&
                   ((claveActual = nodoExistente.key) == clave || (clave != null && clave.equals(claveActual)))) {
                   break;
               }
               nodoEnBucket = nodoExistente;
           }
       }

       // Si se encontró un nodo existente (clave duplicada), se actualiza su valor.
       if (nodoExistente != null) {
           V valorAntiguo = nodoExistente.value;
           if (!soloSiAusente || valorAntiguo == null) {
               nodoExistente.value = valor;
           }
           despuesDeAccesoANodo(nodoExistente);
           return valorAntiguo;
       }
   }

   ++contadorModificaciones; // Se incrementa el contador de modificaciones.
   // Si el tamaño actual excede el umbral de capacidad, se redimensiona.
   if (++tamanoActual > umbralRedimensionamiento) {
       redimensionar();
   }
   despuesDeInsercionDeNodo(forzarEviccion);
   return null;
}
</k></k></k></k>

Consideraciones de Concurrencia

Problemas de Seguridad en Entornos Multihilo

HashMap no es seguro para hilos (thread-safe). Esto se manifiesta en varios problemas:

1. JDK 1.7 - Bucles Infinitos: Durante el redimensionamiento en un entorno multihilo, la estrategia de "inserción por cabecera" en las listas enlazadas podía generar bucles infinitos. Múltiples hilos modificando la misma lista durante la reubicación de nodos podían dejar la lista en un estado inconsistente, formando un ciclo.
2. JDK 1.8 - Pérdida de Datos: Aunque JDK 1.8 utiliza "inserción por cola" para evitar los bucles infinitos, los problemas de concurrencia persisten. Múltiples hilos intentando insertar o modificar entradas simultáneamente pueden llevar a sobrescrituras de datos o a un conteo incorrecto del tamaño (size) del HashMap, ya que las operaciones no están sincronizadas.

Alternativas Seguras para Hilos

Para entornos multihilo, se recomienda usar alternativas:

1. Hashtable: Una opción más antigua que garantiza la seguridad de hilos al bloquear toda la tabla para cada operación. Sin embargo, su rendimiento es bajo debido a esta estrategia de bloqueo global.
2. Collections.synchronizedMap(new HashMap<K, V>()): Envuelve un HashMap regular con un envoltorio sincronizado. Cada método del HashMap envuelto es interceptado y ejecutado dentro de un bloque synchronized, asegurando así la seguridad de hilos. El rendimiento puede ser mejor que Hashtable en algunos escenarios, pero sigue aplicando un bloqueo global implícito.
3. ConcurrentHashMap: Parte del paquete java.util.concurrent (JUC), es la solución más eficiente para entornos multihilo. Utiliza una estrategia de "bloqueo segmentado" (o más precisamente, bloqueos a nivel de bucket o nodo en JDK 1.8+), permitiendo que múltiples hilos operen en diferentes partes de la tabla simultáneamente, lo que mejora drásticamente la concurrencia y el rendimiento.

Principios de Diseño de HashMap

¿Por qué la Capacidad Siempre es una Potencia de 2?

HashMap siempre utiliza una capacidad que es una potencia de 2 (16, 32, 64, etc.). Esto permite que el cálculo del índice (hash & (capacidad - 1)) sea extremadamente eficiente. Cuando la capacidad es una potencia de 2, (capacidad - 1) es una secuencia de unos en binario (ej. si capacidad es 16 (10000), capacidad - 1 es 15 (01111)). La operación AND bit a bit actúa como un módulo (hash % capacidad) pero es mucho más rápida.

Además, esta propiedad simplifica y optimiza la reubicación de nodos durante el redimensionamiento, ya que un nodo solo puede moverse a su índice original o a índice_original + antigua_capacidad.

¿Por qué String e Integer son Claves Ideales?

Clases como String e Integer (y otras clases wrapper) son excelentes candidatas para ser claves en HashMap por varias razones:

1. Inmutabilidad: Son clases final, lo que significa que sus valores no pueden cambiar después de la creación. Esto asegura que el hashCode() de un objeto clave permanezca constante durante toda su vida útil en el HashMap. Si el hash de una clave pudiera cambiar, sería imposible recuperarla correctamente.
2. Implementación de equals() y hashCode(): Todas estas clases tienen implementaciones robustas y correctas de los métodos equals() y hashCode(). Esto es crucial para el funcionamiento de HashMap, ya que garantiza que objetos considerados "iguales" por equals() también produzcan el mismo hashCode() y, por lo tanto, sean gestionados correctamente dentro de la tabla hash.