La estructura de datos subyacenet de ConcurrentHashMap utiliza un arreglo de nodos Node<K,V>[]. Para garantizar la seguridad de los hilos en entornos altamente concurrentes, la implementación combina el uso de bloques synchronized con opreaciones atómicas CAS (Compare-And-Swap).
- Propiedades Fundamentales y Control de Estado
Una de las variables más críticas en la gestión interna de la tabla hash es sizeCtl. Este entero actúa como un mecanismo de control multifuncional que representa diferentes estados dependiendo de su valor:
- -1: Indica que otro hilo está llevando a cabo la inicialización de la tabla.
- -N (donde N > 1): Señala que hay
N - 1hilos colaborando activamente en el proceso de redimensionamiento (expansión) de la tabla. - Positivo o 0: Cuando la tabla aún no ha sido inicializada, este valor define la capacidad inicial. Una vez inicializada, representa el umbral de carga que desencadenará la próxima expansión (equivalente al 75% de la capacidad actual).
Para calcular capacidades que sean potencias de 2, se utiliza un algoritmo de desplazamiento de bits altamente optimizado:
// Calcula la potencia de 2 más cercana que sea mayor o igual a la capacidad solicitada
private static final int calcularCapacidadTabla(int capacidadRequerida) {
int capacidadAjustada = capacidadRequerida - 1;
// Propaga el bit más significativo hacia la derecha para llenar de 1s
capacidadAjustada |= capacidadAjustada >>> 1;
capacidadAjustada |= capacidadAjustada >>> 2;
capacidadAjustada |= capacidadAjustada >>> 4;
capacidadAjustada |= capacidadAjustada >>> 8;
capacidadAjustada |= capacidadAjustada >>> 16;
// Manejo de casos límite y desbordamiento
return (capacidadAjustada < 0) ? 1 :
(capacidadAjustada >= CAPACIDAD_MAXIMA) ? CAPACIDAD_MAXIMA : capacidadAjustada + 1;
}
- Inicialización de la Tabla
El método de inicialización emplea un bucle sin bloqueo (spin-lock) junto con operaciones CAS para asegurar que solo un hilo asigne la memoria para el arreglo base, mientras que los demás hilos ceden el procesamiento temporalmente.
private final Node<k>[] inicializarTabla() {
Node<k>[] tablaActual; int control;
while ((tablaActual = tabla) == null || tablaActual.length == 0) {
if ((control = controlTamanio) < 0) {
// Si el control es negativo, otro hilo ya está inicializando o expandiendo
Thread.yield();
} else if (U.compareAndSwapInt(this, OFFSET_CONTROL, control, -1)) {
try {
// Doble verificación tras adquirir el "bloqueo" lógico
if ((tablaActual = tabla) == null || tablaActual.length == 0) {
int tamInicial = (control > 0) ? control : CAPACIDAD_POR_DEFECTO;
@SuppressWarnings("unchecked")
Node<k>[] nuevaTabla = (Node<k>[])new Node,?>[tamInicial];
tabla = tablaActual = nuevaTabla;
// Establece el nuevo umbral de expansión (n - n/4)
control = tamInicial - (tamInicial >>> 2);
}
} finally {
controlTamanio = control;
}
break;
}
}
return tablaActual;
}
</k></k></k></k>
- Inserción de Elementos
La lógica de inserción está diseñada para minimizar la contención. Rechaza claves o valores nulos, calcula el hash y determina si necesita inicializar la tabla, insertar en un espacio vacío, asistir en una expansión en curso o bloquera un nodo específico para actualizar una lista enlazada o un árbol rojo-negro.
final V insertarValor(K clave, V valor, boolean soloSiAusente) {
if (clave == null || valor == null) throw new NullPointerException();
int codigoHash = dispersarHash(clave.hashCode());
int contadorNodos = 0;
for (Node<k>[] t = tabla;;) {
Node<k> nodoActual; int longitud, indice, hashNodo;
if (t == null || (longitud = t.length) == 0)
t = inicializarTabla();
else if ((nodoActual = obtenerNodo(t, indice = (longitud - 1) & codigoHash)) == null) {
// Intento de inserción atómica en un bucket vacío
if (casNodo(t, indice, null, new Node<k>(codigoHash, clave, valor, null)))
break;
} else if ((hashNodo = nodoActual.hash) == HASH_MOVIDO) {
// Detecta un ForwardingNode, indica que la tabla se está redimensionando
t = asistirTransferencia(t, nodoActual);
} else {
V valorAnterior = null;
// Bloqueo fino: sincroniza solo sobre el nodo cabecera del bucket
synchronized (nodoActual) {
if (obtenerNodo(t, indice) == nodoActual) {
if (hashNodo >= 0) {
contadorNodos = 1;
for (Node<k> e = nodoActual;; ++contadorNodos) {
K k;
if (e.hash == codigoHash && ((k = e.key) == clave || (k != null && clave.equals(k)))) {
valorAnterior = e.val;
if (!soloSiAusente) e.val = valor;
break;
}
Node<k> predecesor = e;
if ((e = e.next) == null) {
predecesor.next = new Node<k>(codigoHash, clave, valor, null);
break;
}
}
} else if (nodoActual instanceof TreeBin) {
Node<k> p;
contadorNodos = 2;
if ((p = ((TreeBin<k>)nodoActual).insertarEnArbol(codigoHash, clave, valor)) != null) {
valorAnterior = p.val;
if (!soloSiAusente) p.val = valor;
}
}
}
}
if (contadorNodos != 0) {
if (contadorNodos >= UMBRAL_ARBORIZACION)
convertirEnArbol(t, indice); // Evolución a árbol rojo-negro si la tabla es lo suficientemente grande
if (valorAnterior != null)
return valorAnterior;
break;
}
}
}
agregarContador(1L, contadorNodos);
return null;
}
</k></k></k></k></k></k></k></k>
- Mecanismo de Pre-Expansión
Cuando se requiere alojar una gran cantidad de elementos de golpe (por ejemplo, mediante putAll), se invoca un método de pre-expansión para evitar múltiples redimensionamientos consecutivos. El núcleo de esta operación radica en la manipulación del estado controlTamanio.
private final void intentarPreExpansion(int tamRequerido) {
int capacidadObjetivo = (tamRequerido >= (CAPACIDAD_MAXIMA >>> 1)) ? CAPACIDAD_MAXIMA :
calcularCapacidadTabla(tamRequerido + (tamRequerido >>> 1) + 1);
int ctrl;
while ((ctrl = controlTamanio) >= 0) {
Node<k>[] t = tabla; int longActual;
if (t == null || (longActual = t.length) == 0) {
longActual = (ctrl > capacidadObjetivo) ? ctrl : capacidadObjetivo;
if (U.compareAndSwapInt(this, OFFSET_CONTROL, ctrl, -1)) {
try {
if (tabla == t) {
@SuppressWarnings("unchecked")
Node<k>[] nuevaT = (Node<k>[])new Node,?>[longActual];
tabla = nuevaT;
ctrl = longActual - (longActual >>> 2);
}
} finally {
controlTamanio = ctrl;
}
}
} else if (capacidadObjetivo <= ctrl || longActual >= CAPACIDAD_MAXIMA) {
break;
} else if (t == tabla) {
int sello = generarSelloExpansion(longActual);
if (ctrl < 0) {
Node<k>[] nt;
if ((ctrl >>> DESPLAZAMIENTO_SELLO) != sello || ctrl == sello + 1 ||
ctrl == sello + MAX_EXPANSORES || (nt = proximaTabla) == null ||
indiceTransferencia <= 0)
break;
// Registrar un hilo adicional para ayudar en la expansión
if (U.compareAndSwapInt(this, OFFSET_CONTROL, ctrl, ctrl + 1))
migrarDatos(t, nt);
} else if (U.compareAndSwapInt(this, OFFSET_CONTROL, ctrl,
(sello << DESPLAZAMIENTO_SELLO) + 2)) {
// Primer hilo que inicia la expansión
migrarDatos(t, null);
}
}
}
}
</k></k></k></k>
La dinámica aquí consiste en establecer un valor negativo en la variable de control para ejecutar la transferencia inicial migrarDatos(t, null). En iteraciones posteriores, el valor se incrementa para registrar hilos adicionales que ejecutarán migrarDatos(t, nt) de manera concurrente.
- Transferencia Concurrente de Datos
El método responsable de mover los elementos del arreglo original al nuevo arreglo es intrínsecamente concurrente. Aunque la pre-expansión inicia el proceso, las inserciones regulares pueden detectarlo y unirse a la tarea mediante asistirTransferencia.
Para coordinar múltiples hilos sin generar contención, la migración no se realiza nodo por nodo de forma aleatoria. En su lugar, el arreglo original de longitud n se divide en lotes. Doug Lea implementó un concepto de "paso" o stride (por ejemplo, 16 buckets por lote). Una variable global, indiceTransferencia, actúa como un planificador. El primer hilo apunta este índice al final del arreglo, asume la migración de los últimos stride buckets, y luego decrementa el índice para que el siguiente hilo disponible tome el lote adyacente, procesando la tabla de atrás hacia adelante de manera segura.