Al aplicar HashMap en un entorno multiproceso de Java, existen principalmente las siguientes opciones: Usar java.util.Hashtable seguro para subprocesos como alternativa Usar el método java.util.Collections.synchronizedMap para envolver el objeto HashMap existente como subproceso. -seguro. Utilice la clase java.util.concurrent.ConcurrentHashMap como alternativa, que tiene muy buen rendimiento.
Todos los métodos anteriores utilizan bloqueos mutex más o menos en los detalles específicos de implementación. Los bloqueos Mutex provocarán el bloqueo de subprocesos, reducirán la eficiencia operativa y pueden causar una serie de problemas, como interbloqueos y cambios de prioridad.
CAS (Comparar e intercambiar) es una función proporcionada por el hardware subyacente, que puede atomizar la operación de juzgar y cambiar un valor.
Operaciones atómicas en Java
En el paquete java.util.concurrent.atomic, Java nos proporciona muchos tipos atómicos convenientes, que se basan completamente en operaciones CAS.
Por ejemplo, si queremos implementar un contador público global, podemos:
Copie el código de código de la siguiente manera:
contador privateAtomicInteger =newAtomicInteger(3);
publicvoidaddContador() {
para(;;) {
intoldValue = contador.get();
intnewValue = oldValue +1;
if(counter.compareAndSet(oldValue, newValue))
devolver;
}
}
Entre ellos, el método compareAndSet verifica si el valor existente del contador es oldValue. Si es así, se establece en el nuevo valor newValue. La operación es exitosa y se devuelve verdadero; de lo contrario, la operación falla y se devuelve falso.
Al calcular el nuevo valor del contador, si otros subprocesos cambian el valor del contador, compareAndSwap fallará. En este punto, solo necesitamos agregar una capa de bucle afuera y seguir intentando este proceso, luego eventualmente aumentaremos con éxito el valor del contador en 1. (De hecho, AtomicInteger ya ha definido los métodos incrementAndGet y decrementAndGet para las operaciones +1/-1 comúnmente utilizadas. Solo necesitamos llamarlos en el futuro)
Además de AtomicInteger, el paquete java.util.concurrent.atomic también proporciona los tipos AtomicReference y AtomicReferenceArray, que representan referencias atómicas y matrices de referencia atómica (matrices de referencias) respectivamente.
Implementación de lista enlazada sin bloqueo
Antes de implementar un HashMap sin bloqueos, primero echemos un vistazo al método de implementación relativamente simple de una lista vinculada sin bloqueos.
Tome la operación de inserción como ejemplo:
Primero necesitamos encontrar el nodo A delante de la posición a insertar y el nodo B detrás de ella.
Luego cree un nuevo nodo C y haga que su siguiente puntero apunte al nodo B. (Ver Figura 1)
Finalmente, haga que el siguiente puntero del nodo A apunte al nodo C. (Ver Figura 2)
Sin embargo, durante la operación, es posible que otros subprocesos inserten directamente algunos nodos en A y B (se supone que son D). Si no hacemos ningún juicio, puede provocar la pérdida de nodos insertados por otros subprocesos. (Consulte la Figura 3) Podemos usar la operación CAS para determinar si el siguiente puntero del nodo A todavía apunta a B al asignar un valor. Si el siguiente puntero del nodo A cambia, vuelva a intentar toda la operación de inserción. El código aproximado es el siguiente:
Copie el código de código de la siguiente manera:
privatevoidlistInsert (cabeza de nodo, nodo c) {
para(;;) {
Nodo a = findInsertionPlace(head), b = a.next.get();
c.siguiente.conjunto(b);
si(a.siguiente.compareAndSwap(b,c))
devolver;
}
}
(El siguiente campo de la clase Nodo es de tipo AtomicReference<Node>, que es una referencia atómica que apunta al tipo de Nodo)
La operación de búsqueda de una lista enlazada sin bloqueo no es diferente de la de una lista enlazada normal. La operación de eliminación requiere encontrar el nodo A delante del nodo que se va a eliminar y el nodo B detrás de él, y utilizar la operación CAS para verificar y actualizar el siguiente puntero del nodo A para que apunte al nodo B.
Dificultades y avances de HashMap sin bloqueos
HashMap tiene principalmente cuatro operaciones básicas: inserción, eliminación, búsqueda y ReHash. Una implementación típica de HashMap utiliza una matriz, y cada elemento de la matriz es una lista vinculada de nodos. Para esta lista vinculada, podemos utilizar los métodos de operación mencionados anteriormente para realizar operaciones de inserción, eliminación y búsqueda, pero la operación ReHash es más difícil.
Como se muestra en la Figura 4, durante el proceso ReHash, una operación típica es atravesar cada nodo en la tabla anterior, calcular su posición en la tabla nueva y luego moverlo a la tabla nueva. Durante este período necesitamos manipular el puntero tres veces:
El siguiente puntero del punto A a D
El siguiente puntero del punto B a C
El siguiente puntero del punto C a E
Estas tres operaciones de puntero deben completarse al mismo tiempo para garantizar la atomicidad de la operación de movimiento. Pero no es difícil ver que la operación CAS solo puede garantizar que el valor de una variable se verifique y actualice atómicamente a la vez, y no puede satisfacer la necesidad de verificar y actualizar tres punteros al mismo tiempo.
Por lo tanto, también podríamos cambiar nuestra forma de pensar. Dado que la operación de mover nodos es tan difícil, podemos mantener todos los nodos en un estado ordenado en todo momento, evitando así la operación de movimiento. En una implementación típica de HashMap, la longitud de la matriz siempre sigue siendo 2i, y el proceso de asignar el valor Hash al subíndice de la matriz simplemente realiza una operación de módulo en la longitud de la matriz (es decir, solo los últimos i bits del binario Hash son retenido). Cuando ReHash, la longitud de la matriz se duplica a 2i+1, y cada nodo en la j-ésima lista de collares de la matriz anterior se mueve al j-ésimo elemento de la nueva matriz o al j+2i-ésimo elemento en la nueva matriz, y su La única diferencia radica en el bit i+1 del valor Hash (si el bit i+1 es 0, sigue siendo el elemento j; de lo contrario, es el elemento j+2).
Como se muestra en la Figura 5, organizamos todos los nodos en orden ascendente de acuerdo con el orden invertido del valor Hash (como 1101->1011). Cuando el tamaño de la matriz es 8, 2 y 18 están en un grupo; 3, 11 y 27 están en otro grupo. Al inicio de cada grupo se inserta un ganglio centinela para facilitar las operaciones posteriores. Para organizar correctamente el nodo centinela al frente del grupo, configuramos el bit más alto del Hash del nodo normal (que se convierte en el bit más bajo después de voltear) en 1, mientras que el nodo centinela no establece este bit.
Cuando la matriz se expande a 16 (ver Figura 6), el segundo grupo se divide en un grupo que contiene solo 3 y un grupo que contiene 11 y 27, pero el orden relativo entre los nodos no ha cambiado. De esta manera, no necesitamos mover nodos durante ReHash.
Detalles de implementación
Dado que la copia de la matriz lleva mucho tiempo durante la expansión, aquí adoptamos el método de dividir la matriz completa en bloques y crearla de manera perezosa. De esta forma, cuando se accede a un determinado subíndice, solo es necesario juzgar si se ha establecido el bloque donde se encuentra el subíndice (si no, créelo).
Además, el tamaño se define como el rango de subíndices utilizado actualmente y su valor inicial es 2. Cuando se expande la matriz, el tamaño solo necesita duplicarse y el recuento se define para representar el número total de nodos incluidos actualmente en el HashMap ( sin contar los ganglios centinela).
Inicialmente, todos los elementos de la matriz, excepto el elemento 0, son nulos. El elemento 0 apunta a una lista enlazada con un solo ganglio centinela, que representa el punto de partida de toda la cadena. La imagen completa inicial se muestra en la Figura 7, en la que el verde claro representa el rango de subíndices actualmente no utilizado y las flechas punteadas representan bloques que existen lógicamente pero que en realidad no están establecidos.
Inicializar operación de subíndice
Los elementos nulos de la matriz se consideran en un estado no inicializado. Inicializar un determinado subíndice significa establecer su nodo centinela correspondiente. La inicialización se realiza de forma recursiva, es decir, si su subíndice principal no se inicializa, su subíndice principal se inicializa primero. (El subíndice principal de un subíndice es el subíndice obtenido eliminando el bit binario más alto). El código aproximado es el siguiente:
Copie el código de código de la siguiente manera:
privatevoidinitializeBucket(intbucketIdx) {
intparentIdx = bucketIdx ^ Integer.highestOneBit(bucketIdx);
si(getBucket(parentIdx) ==nulo)
inicializarCubo(parentIdx);
Nodo ficticio =newNode();
dummy.hash = Integer.reverse(bucketIdx);
dummy.next =newAtomicReference<>();
setBucket(bucketIdx, listInsert(getBucket(parentIdx), tonto));
}
Entre ellos, getBucket es un método encapsulado para obtener el contenido de un determinado subíndice en la matriz, y setBucket es el mismo. listInsert insertará el nodo dado en una posición adecuada a partir de la posición especificada. Si ya existe un nodo con el mismo hash en la lista vinculada, devolverá el nodo existente; de lo contrario, devolverá el nodo recién insertado.
operación de inserción
Primero, use el tamaño de HashMap para modular el código hash de la clave para obtener el subíndice de la matriz que debe insertarse.
Luego determine si el subíndice es nulo y, si es nulo, inicialice el subíndice.
Construya un nuevo nodo e insértelo en la posición apropiada. Tenga en cuenta que el valor hash en el nodo debe ser el valor del código hash original después de invertir el bit y establecer la posición más baja en 1.
Agregue 1 al contador de número de nodos. Si hay demasiados nodos después de agregar 1, solo necesita cambiar el tamaño a tamaño * 2, lo que significa expandir la matriz (ReHash).
encontrar operación
Encuentre el índice del nodo que se encontrará en la matriz.
Determine si el subíndice es nulo. Si es nulo, se devolverá el error de búsqueda.
Ingrese a la lista vinculada desde la posición correspondiente y busque secuencialmente hasta que el nodo a encontrar se encuentre o exceda el rango de este grupo de nodos.
eliminar operación
Encuentre el índice del nodo en la matriz que debe eliminarse.
Determine si el subíndice es nulo y, si es nulo, inicialice el subíndice.
Busque el nodo que desea eliminar y elimínelo de la lista vinculada. (Tenga en cuenta que debido a la existencia del nodo centinela, cualquier elemento normal solo es referenciado por su único nodo predecesor. No existe ninguna situación en la que el nodo predecesor y el puntero en la matriz hagan referencia a él al mismo tiempo, por lo que hay no es necesario modificar varios punteros al mismo tiempo).
Disminuya el contador del número de nodo en 1.