HashMap es una estructura de datos fundamental en Java para almacenar pares clave-valor. Con la evolución del JDK, la versión 1.8 introdujo mejoras significativas en su implementación, incluyendo el uso de árboles rojo-negros para gestionar colisiones y optimizaciones en la expansión del mapa. Este artículo explora la arquitectura interna de HashMap, comparando sus características entre JDK 1.7 y JDK 1.8.
En Java, la interfaz java.util.Map define operaciones para mapas, con implemantaciones comunes como HashMap, Hashtable, LinkedHashMap y TreeMap. Cada una tiene características distintas:
- HashMap: Almacena datos basados en el código hash de la clave, permitiendo acceso rápido pero con orden de iteración no garantizado. Permite una clave nula y múltiples valores nulos. No es seguro para hilos; para concurrencia se recomienda
ConcurrentHashMap. - Hashtable: Una clase heredada que es segura para hilos pero con menor concurrencia que
ConcurrentHashMap. Evitar su uso en código nuevo. - LinkedHashMap: Extiende HashMap manteniendo el orden de inserción o acceso.
- TreeMap: Implementa
SortedMap, ordenando entradas por clave. Requiere que las claves implementenComparableo proporcione unComparator.
Las claves en estos mapas deben ser objetos inmutables para garantizar consistencia en el hash.
Arquitectura interna
Estructura de almacenamiento
Internmaente, HashMap utiliza una combinación de arreglo, lista enlazada y, desde JDK 1.8, árboles rojo-negros. El componente central es el arreglo Node[], donde cada elemento es un Node que representa un par clave-valor. Ejemplo de definición de Node en JDK 1.8:
static class NodeClaveValor<K, V> implements Map.Entry<K, V> {
final int hashClave;
final K clave;
V valor;
NodeClaveValor<K, V> siguiente;
NodeClaveValor(int hashClave, K clave, V valor, NodeClaveValor<K, V> siguiente) { ... }
// Métodos getters, setters y equals
}
HashMap resuelve colisiones mediante encadenamiento: elementos con el mismo índice del arreglo se enlazan en una lista. Si la lista excede un umbral (por defecto 8), se convierte en un árbol rojo-negro para mejorar el rendimiento en búsquedas.
Campos importantes
La inicialización de HashMap involucra varios campos clave:
int capacidadUmbral; // Máximo número de pares clave-valor antes de redimensionar
final float factorCarga; // Factor de carga para controlar la densidad (por defecto 0.75)
int contadorModificaciones; // Contador de cambios estructurales para iteradores seguros
int tamaño; // Número actual de pares clave-valor
La longitud del arreglo (Node[]) es una potencia de 2 para optimizar operaciones de módulo. El umbral se calcula como longitud * factorCarga.
Implementación de métodos
Cálculo del índice del hash
Para localizar un elemento, HashMap calcula un hash de la clave y lo mapea a un índice del arreglo. Algoritmo de hash en JDK 1.8:
static final int calcularHash(Object clave) {
int hashInicial;
return (clave == null) ? 0 : (hashInicial = clave.hashCode()) ^ (hashInicial >>> 16);
}
static int obtenerIndice(int hashCompleto, int longitudArreglo) {
return hashCompleto & (longitudArreglo - 1);
}
Este método utiliza la operación AND bit a bit en lugar de módulo para eficiencia, ya que la longitud del arreglo es potencia de 2.
Método put
El método put inserta o actualiza pares clave-valer. Pasos resumidos:
- Si el arreglo está vacío, se redimensiona.
- Se calcula el índice; si está vacío, se inserta un nuevo nodo.
- Si la clave ya existe, se actualiza el valor.
- Si el nodo es un árbol rojo-negro, se inserta en el árbol.
- Si es una lista enlazada, se recorre; si la longitud supera 8, se convierte en árbol.
- Después de insertar, si el tamaño excede el umbral, se redimensiona.
Ejemplo de implementación simplificada en JDK 1.8:
public V insertar(K clave, V valor) {
return insertarValor(calcularHash(clave), clave, valor, false, true);
}
final V insertarValor(int hashClave, K clave, V valor, boolean soloSiAusente, boolean evento) {
NodeClaveValor<K, V>[] arreglo; NodeClaveValor<K, V> nodo; int longitud, indice;
if ((arreglo = tabla) == null || (longitud = arreglo.length) == 0)
longitud = (arreglo = redimensionar()).length;
if ((nodo = arreglo[indice = (longitud - 1) & hashClave]) == null)
arreglo[indice] = nuevoNodo(hashClave, clave, valor, null);
else {
NodeClaveValor<K, V> nodoExistente; K claveExistente;
if (nodo.hashClave == hashClave && ((claveExistente = nodo.clave) == clave || (clave != null && clave.equals(claveExistente))))
nodoExistente = nodo;
else if (nodo instanceof NodoArbol)
nodoExistente = ((NodoArbol<K, V>)nodo).insertarEnArbol(this, arreglo, hashClave, clave, valor);
else {
for (int contador = 0; ; ++contador) {
if ((nodoExistente = nodo.siguiente) == null) {
nodo.siguiente = nuevoNodo(hashClave, clave, valor, null);
if (contador >= UMBRAL_ARBOL - 1)
convertirEnArbol(arreglo, hashClave);
break;
}
if (nodoExistente.hashClave == hashClave && ((claveExistente = nodoExistente.clave) == clave || (clave != null && clave.equals(claveExistente))))
break;
nodo = nodoExistente;
}
}
if (nodoExistente != null) {
V valorAntiguo = nodoExistente.valor;
if (!soloSiAusente || valorAntiguo == null)
nodoExistente.valor = valor;
despuesAccesoNodo(nodoExistente);
return valorAntiguo;
}
}
++contadorModificaciones;
if (++tamaño > capacidadUmbral)
redimensionar();
despuesInsercionNodo(evento);
return null;
}
Redimensionamiento (resize)
Cuando el tamaño supera el umbral, HashMap redimensiona el arreglo al doble de su capacidad. En JDK 1.8, se optimiza la reubicación de elementos:
final NodeClaveValor<K, V>[] redimensionar() {
NodeClaveValor<K, V>[] arregloViejo = tabla;
int capacidadVieja = (arregloViejo == null) ? 0 : arregloViejo.length;
int umbralViejo = capacidadUmbral;
int capacidadNueva, umbralNuevo = 0;
if (capacidadVieja > 0) {
if (capacidadVieja >= CAPACIDAD_MAXIMA) {
capacidadUmbral = Integer.MAX_VALUE;
return arregloViejo;
}
else if ((capacidadNueva = capacidadVieja << 1) < CAPACIDAD_MAXIMA && capacidadVieja >= CAPACIDAD_INICIAL)
umbralNuevo = umbralViejo << 1;
}
else if (umbralViejo > 0)
capacidadNueva = umbralViejo;
else {
capacidadNueva = CAPACIDAD_INICIAL;
umbralNuevo = (int)(FACTOR_CARGA_DEFECTO * CAPACIDAD_INICIAL);
}
if (umbralNuevo == 0) {
float calculoUmbral = (float)capacidadNueva * factorCarga;
umbralNuevo = (capacidadNueva < CAPACIDAD_MAXIMA && calculoUmbral < (float)CAPACIDAD_MAXIMA ?
(int)calculoUmbral : Integer.MAX_VALUE);
}
capacidadUmbral = umbralNuevo;
NodeClaveValor<K, V>[] arregloNuevo = (NodeClaveValor<K, V>[])new NodeClaveValor[capacidadNueva];
tabla = arregloNuevo;
if (arregloViejo != null) {
for (int j = 0; j < capacidadVieja; ++j) {
NodeClaveValor<K, V> e;
if ((e = arregloViejo[j]) != null) {
arregloViejo[j] = null;
if (e.siguiente == null)
arregloNuevo[e.hashClave & (capacidadNueva - 1)] = e;
else if (e instanceof NodoArbol)
((NodoArbol<K, V>)e).dividir(this, arregloNuevo, j, capacidadVieja);
else {
NodeClaveValor<K, V> cabezaBaja = null, colaBaja = null;
NodeClaveValor<K, V> cabezaAlta = null, colaAlta = null;
NodeClaveValor<K, V> siguiente;
do {
siguiente = e.siguiente;
if ((e.hashClave & capacidadVieja) == 0) {
if (colaBaja == null)
cabezaBaja = e;
else
colaBaja.siguiente = e;
colaBaja = e;
}
else {
if (colaAlta == null)
cabezaAlta = e;
else
colaAlta.siguiente = e;
colaAlta = e;
}
} while ((e = siguiente) != null);
if (colaBaja != null) {
colaBaja.siguiente = null;
arregloNuevo[j] = cabezaBaja;
}
if (colaAlta != null) {
colaAlta.siguiente = null;
arregloNuevo[j + capacidadVieja] = cabezaAlta;
}
}
}
}
}
return arregloNuevo;
}
Este método evita recalcular hashes completos, reutilizando bits existentes para determinar la nueva posición.
Seguridad en concurrencia
HashMap no es seguro para hilos. En entornos concurrentes, puede causar bucles infinitos o corrupción de datos. Ejemplo problemático con JDK 1.7:
public class BucleInfinitoHashMap {
private static HashMap<Integer, String> mapa = new HashMap<>(2, 0.75f);
public static void main(String[] args) {
mapa.put(5, "C");
new Thread("Hilo1") {
public void run() {
mapa.put(7, "B");
System.out.println(mapa);
};
}.start();
new Thread("Hilo2") {
public void run() {
mapa.put(3, "A");
System.out.println(mapa);
};
}.start();
}
}
Durante la expansión, los hilos pueden intercalarse creando listas circulares, llevando a un bucle infinito en operaciones como get.
Comparación de rendimiento entre JDK 1.7 y JDK 1.8
En pruebas con distribuciones uniformes de hash, JDK 1.8 mejora el rendimiento hasta en un 15% debido a optimizaciones internas. Para hashes no uniformes, JDK 1.8 muestra una mejora drástica al convertir listas largas en árboles, reduciendo la complejidad de O(n) a O(log n). Ejemplo de clave para pruebas:
class Clave implements Comparable<Clave> {
private final int valor;
Clave(int valor) { this.valor = valor; }
@Override
public int hashCode() { return valor; } // Hash uniforme; para no uniforme, retornar 1
@Override
public boolean equals(Object o) { ... }
@Override
public int compareTo(Clave o) { return Integer.compare(this.valor, o.valor); }
}
La caché de claves evita sobrecarga de GC, y las pruebas con diferentes tamaños de mapa confirman las mejoras.