Sabemos que una tabla hash es una estructura de datos muy eficiente, y un excelente diseño de la función hash puede hacer que las operaciones de adición, eliminación, modificación y búsqueda alcancen el nivel O (1). Java nos proporciona una estructura hash preparada, es decir, la clase hashmap. En el artículo anterior, introduje la clase Hashmap y supe que todos sus métodos no estaban sincronizados, por lo que no es seguro en un entorno múltiple. Con este fin, Java nos proporciona otra clase de hashtable, que es muy simple y cruda en el manejo de la sincronización de múltiples subprocesos, es decir, para bloquear todos sus métodos utilizando la palabra clave sincronizada basada en HashMap. Aunque este método es simple, conduce a un problema, es decir, solo un hilo puede operar la tabla hash al mismo tiempo. Incluso si estos hilos solo son operaciones de lectura, deben colocarse en cola, lo que afecta en gran medida el rendimiento en entornos múltiples altamente competitivos. El Contrarrenthashmap introducido en este artículo es resolver este problema. Utiliza cerraduras segmentadas para grano fino, para que múltiples hilos puedan operar la tabla hash al mismo tiempo, lo que mejora enormemente el rendimiento. La siguiente figura es un diagrama esquemático de su estructura interna.
1. ¿Qué variables de miembro tiene concurrenthashmap?
// Capacidad de inicialización predeterminada estática final int default_initial_capacitity = 16; // factor de carga predeterminado Flot final float default_load_factor = 0.75f; // Nivel de concurrencia predeterminado estático final int default_concurrency_level = 16; // Establece la capacidad máxima de la capacidad máxima INTAT INTOPATIZACIAZACIA = 1 << 30; // Número de bloqueo de Locos de segmento STATIC STATIC STATIC STATIC MINEMENTACIÓN FINAL MÁSEGO MACHORMUMME_TACITATATATABE_CAPACIDAD 2; // Número máximo de bloqueos de segmento FINAL ESTÁTICO int max_segments = 1 << 16; // Número de reintentos antes de bloquear la finalización de los reintentos de los reintentos de los reintentos_before_lock = 2; // del bloqueo del segmento Final int segmentmask; // segmento del segmento de la matriz de bloqueo del segmento <k, v> [] segmentos;
Antes de leer este artículo, creo que los lectores no pueden entender el significado y la función específicos de estas variables miembros, pero se aconseja a los lectores que lean pacientemente. El papel de estas variables miembros se introducirá una por una en los escenarios específicos más adelante. Aquí los lectores solo necesitan dejar una mirada familiar a estas variables miembros. Sin embargo, todavía hay algunas variables que necesitamos saber ahora. Por ejemplo, la matriz de segmentos representa el conjunto de bloqueos de segmento, el nivel de concurrencia representa el número de bloqueos de segmento (lo que también significa cuántos hilos pueden operar al mismo tiempo), la capacidad de inicialización representa la capacidad de todo el contenedor, y el factor de carga representa el nivel de cómo pueden alcanzar los elementos de contenedor completos.
2. ¿Cuál es la estructura interna del bloqueo del segmento?
// Bloqueo de segmento Segmento de clase final estática <k, v> extiende ReentrantLock implementa serializable {// número de giro máximo estático final int max_scan_retries = runtime.getRuntime (). Disponibleprocessors ()> 1? 64: 1; // HAST TABLA TABLA TABLE TABLE TABLE CON TABLA COLERA <K, V> []; // Número total de elementos transitorios int count; // Número de modificaciones transitorias int mod; // Umbral de elemento Transitorio int int; // Factor de carga FLOAT FLOATFACTOR; // omitir el siguiente contenido ...}El segmento es una clase interna estática de concurrenthashmap, puede ver que hereda del reentrantlock, por lo que es esencialmente un bloqueo. Sostiene internamente una matriz de hashentry (tabla hash), y asegura que todos los métodos de agregar, eliminar, modificar y buscar la matriz sean seguros de subprocesos. La implementación específica se discutirá más adelante. Todas las operaciones para agregar, eliminar, modificar y verificar concurrenthashmap pueden confiarse al segmento, por lo que concurrenthashmap puede asegurarse de que sea seguro en un entorno múltiple. Además, debido a que los diferentes segmentos son cerraduras diferentes, los múltiples lecturas pueden operar diferentes segmentos al mismo tiempo, lo que significa que los múltiples lecturas pueden operar concurrenthashmap al mismo tiempo, lo que puede evitar los defectos de los hashtables y mejorar en gran medida el rendimiento.
3. ¿Qué inicializó concurrenthashmap?
// constructor de núcleo @SupplesSwarnings ("no facturado") Public ConcurrentHashMap (int InitialCapacity, Float LoadFactor, int ConcurrencyLevel) {if (! (LoadFactor> 0) || InitialCapacity <0 || ContrarrencyLevel <= 0) {tira nueva ilegalargumentException ();; } // Asegúrese de que el nivel de concurrencia no sea mayor que el límite if (concurrencyLevel> max_segments) {concurrencyLevel = max_segments; } int sshift = 0; int ssize = 1; // Asegúrese de que SSIZE sea un poder de 2, y es el número más cercano mayor o igual al nivel de concurrencia, mientras que (SSize <ConcurrencyLevel) {++ sshift; ssize << = 1; } // Calcule el valor de cambio del segmento bloquear this.segmentshift = 32 - sshift; // Calcule el valor de la máscara del segmento bloquear esto. Segmentmask = ssize - 1; // La capacidad inicial total no puede ser mayor que el valor límite if (inicialcapacity> maximum_capacity) {inicialcapacity = maximum_capacity; } // Obtener la capacidad inicial de cada bloqueo de segmento int c = inicialcapacity /ssize; // La suma de la capacidad de bloqueo segmentado no es menor que la capacidad total inicial si (c * ssize <inicialcapacity) {++ c; } int cap = min_segment_table_capacity; // Asegúrese de que CAP sea una potencia de 2, y es el número más cercano mayor o igual a C, mientras que (Cap <C) {Cap << = 1; } // Cree un nuevo segmento de plantilla de objeto de segmento <k, v> s0 = nuevo segmento <k, v> (loadFactor, (int) (cap * loadFactor), (hashentry <k, v> []) new Hashentry [Cap]); // Cree una nueva matriz de bloqueo de segmento del segmento de tamaño especificado <k, v> [] ss = (segmento <k, v> []) nuevo segmento [ssize]; // Use inseguro para asignar el elemento 0 de la matriz Unsafe.putOrderedObject (SS, SBase, S0); this.segments = ss;}Concurrenthashmap tiene múltiples constructores, pero lo que se publica anteriormente es su constructor central, y otros constructores completan la inicialización llamándolo. El constructor central debe pasar en tres parámetros, a saber, la capacidad inicial, el factor de carga y el nivel de concurrencia. Al introducir las variables de los miembros antes, podemos saber que la capacidad inicial predeterminada es 16, el factor de carga es 0.75F y el nivel de concurrencia es 16. Ahora vemos el código del constructor central. Primero, calculamos el ssize a través del nivel de concurrencia entrante. SSIZE es la longitud de la matriz de segmentos. Debe garantizarse que es un poder de 2. De esta manera, el subíndice del segmento bloqueado en la matriz puede calcularse mediante hash & ssize-1. Dado que no se puede garantizar que el nivel de concurrencia entrante sea una potencia de 2, no puede usarse directamente como la longitud de la matriz de segmentos. Por lo tanto, necesitamos encontrar una potencia de 2 más cercana al ConcurrenciDeLevel y usarlo como la longitud de la matriz. Si el ContrurrencyLevel = 15 se pasa ahora, el código anterior puede calcular ssize = 16 y sshift = 4. A continuación, puede calcular inmediatamente el desplazamiento de segmento = 16 y Segmentmask = 15. Tenga en cuenta que el desplazamiento de segmento aquí es el valor de cambio del bloqueo de segmento, y Segmentmask es el valor de máscara del bloqueo de segmento. Estos dos valores se utilizan para calcular el subíndice del bloqueo de segmento en la matriz, del cual hablaremos a continuación. Después de calcular el número de bloqueos de segmento SSIZE, la capacidad de cada bloqueo de segmento se puede calcular en función de la capacidad entrante total y su valor c = capacidad inicial/ssize. La capacidad del bloqueo del segmento es la longitud de la matriz de hashentry, y también debe garantizarse que es un poder de 2. El valor de C calculado anteriormente no puede garantizar esto, por lo que C no puede usarse directamente como la longitud de la matriz de hashentry. Debe encontrar otra potencia de 2 más cercana a C, asignar este valor a Cape y luego usar CAP como la longitud de la matriz de hashentry. Ahora que tenemos ssize y tap, podemos crear un nuevo segmento de matriz de bloqueo de segmento [] y un hashentry de matriz de elementos []. Tenga en cuenta que, a diferencia de JDK1.6, solo la matriz de segmentos se creó en JDK1.7 y no se inicializó. La operación de inicializar el segmento se dejó a la operación de inserción.
4. ¿Cómo localizar cerraduras y ubicar elementos?
// Obtenga bloqueos de segmento basados en el código hash @SupplesSwarnings ("no controlado") segmento privado <k, v> segmentforhash (int h) {long u = (((h >>> segmentshift) y segmentmask) << sshift) + sbase; return (segmento <k, v>) unsafe.getObjectVolatile (segmentos, u);} // get elemento basado en el código hash @supesswarnings ("sin verificar") Static final <k, v> hashentry <k, v> entryforhash (segmento <k, v> seg, int h) {hahentry <k, v> [] tabs; return (seg == null || (tab = seg.table) == null)? NULL: (Hashentry <k, v>) unsafe.getObjectVolatile (tab, ((long) ((tab.length - 1) & h)) << tshift) + tbase);} En JDK1.7, Insafe se usa para obtener elementos de matriz, por lo que aquí hay algunos códigos más para calcular las compensaciones de los elementos de matriz que JDK1.6. No prestaremos atención a estos códigos por el momento. Ahora solo necesitamos saber los siguientes dos puntos:
a. Calcule el subíndice del segmento bloqueado en la matriz a través del código hash: (h >>> desplazamiento de segmento) y masas de segmento.
b. Calcule el subíndice de elementos en la matriz por código hash: (tab.length - 1) y h.
Ahora supongamos que los dos parámetros pasados al constructor son la capacidad inicial = 128, ConcurrencyLevel = 16. Según el cálculo, podemos obtener ssize = 16, sshift = 4, sgmentshift = 28, segmentmask = 15. Del mismo modo, la longitud de la matriz de hashentry en cada bloqueo de segmento se calcula como 8, por lo que Tab.length-1 = 7. Según estos valores, explicamos cómo localizar bloqueos y elementos de segmento basados en el mismo código hash a través de la siguiente figura.
Se puede ver que el bloqueo del segmento y el posicionamiento del elemento están determinados por el código hash del elemento. El bloqueo del segmento de posicionamiento es el alto valor del código hash (a partir de 32 bits), y el elemento de posicionamiento es el bajo valor del código hash. Ahora hay una pregunta. Comienzan desde el extremo izquierdo del extremo de 32 bits y el extremo derecho de los 32 bits. ¿Habrá conflictos en algún momento? Podemos encontrar Maximum_Capacity = 1 << 30, max_segments = 1 << 16 en la variable de miembro, lo que significa que el número total de bits utilizados para colocar bloqueos de segmento y elementos de posicionamiento no excede 30, y el número de bits utilizados para posicionar las bloqueos de segmento de posicionamiento no excede 16, por lo que queda al menos 2 bits restantes, por lo que no habrá conflicto.
5. ¿Cómo encontrar elementos específicamente?
// Get ValuePublic v get (clave de objeto) {segmento <k, v> s; Hashentry <k, v> [] pestaña; // Calcule el código hash utilizando la función hash int h = hash (clave); // Calcule el índice del bloqueo del segmento en función del código hash largo U = (((H >>> SegmentShift) y Segmentmask) << sshift) + sbase; // Obtenga el bloqueo del segmento y la tabla hash correspondiente if ((s = (segmento <k, v>) unsafe.getObjectVolatile (segmentos, u))! = Null && (tab = s.table)! = Null) {// obtiene el nodo de cabeza de la lista vinculada de acuerdo con el código hash, y luego traza la lista vinculada para (hashentry <k, v> e = e> e = (Hashentry <k, v>) inseguro.getObjectVolatile (Tab, ((long) (((tab.length - 1) & h)) << tshift) + tbase); // Siga el valor del elemento correspondiente de acuerdo con la clave y hash y devuelva el valor if ((k = e.key) == clave || (e.hash == h && key.equals (k))) {return e.value; }}} return null;}En JDK1.6, el método GET de bloqueo del segmento accede a elementos de matriz a través de subíndices, mientras que en JDK1.7, los elementos en la matriz se leen a través del método GetObjectVolatile de GetObjectVolatil de Inseguridad. ¿Por qué hacer esto? Sabemos que aunque la referencia de matriz de hashentry sostenida por el objeto de segmento es de tipo volátil, las referencias de elementos en la matriz no son de tipo volátil, por lo que las modificaciones multiproceso a los elementos de la matriz son inseguros y pueden leer objetos que aún no se han construido en la matriz. En JDK1.6, se garantiza que la segunda lectura de bloqueo será segura, y en JDK1.7, la lectura a través del método GetObjectVolatile de GetObjectVolatil de Inseguridad también es garantizar esto. La lectura de elementos de matriz utilizando el método GetObjectVolatile requiere primero obtener el desplazamiento del elemento en la matriz. Aquí, según el código hash, el desplazamiento del bloqueo del segmento en la matriz es U, y luego el desplazamiento U se usa para intentar leer el bloqueo del segmento. Dado que la matriz de bloqueo del segmento no se inicializa durante la construcción, se puede leer un valor nulo, por lo que se requiere un juicio primero. Después de confirmar que el bloqueo del segmento y su tabla de hash interna no están vacíos, los elementos de la matriz de hashentry se leen a través del código hash. De acuerdo con el diagrama de la estructura anterior, puede ver que el nodo de encabezado de la lista vinculada se obtiene en este momento. Luego atraviese y busque la lista vinculada de principio a fin. Si se encuentra el valor correspondiente, se devolverá, de lo contrario se devolverá nulo. Lo anterior es todo el proceso de búsqueda de elementos.
6. ¿Cómo implementar el elemento de inserción?
// Agregar pares de valor clave al conjunto (reemplazar si hay) @supresswarnings ("sin verificar") public v put (k key, v valor) {segmento <k, v> s; // El valor pasado no puede estar vacío si (valor == null) tira nueva nullpointerException (); // Calcule el código hash usando la función hash int hash = hash (clave); // Calcule el subíndice del bloqueo de segmento en función del código hash int j = (hash >>> sgmentshift) & segmentmask; // Intenta obtener el bloqueo de segmento basado en el subíndice if ((s = (segmento <k, v>) unsafe.getObject (segmentos, (j << sshift) + sbase)) == null) {// si el bloqueo de segmento obtenido está vacío, construya un s = ssureSegment (j); } // Llame al método PUT del bloqueo del segmento return s.put (clave, hash, valor, falso);} // Agregue un par de valores clave al conjunto (Agregar si no existe) @SuppressWarnings ("sin verificar") public v putifabsent (k key, valor v) {segmento <k, v> s; // El valor pasado no puede estar vacío si (valor == null) tira nueva nullpointerException (); // Calcule el código hash con hash = hash (clave); // Calcule el subíndice del bloqueo de segmento en función del código hash int j = (hash >>> sgmentshift) & segmentmask; // Intenta obtener el bloqueo del segmento basado en el subíndice if ((s = (segmento <k, v>) unsafe.getObject (segmentos, (j << sshift) + sbase)) == null) {// construye a s = ssureSegment (j); } // Calendario El método PUT del bloqueo del segmento return s.put (clave, hash, valor, verdadero);}Hay dos métodos en concurrenthashmap para agregar pares de valor clave. Si existe, se sobrescribirá cuando se agregue a través del método PUT. El método ifabsent se agrega a través del método Put Ifabsent, no se sobrescribirá. Ambos métodos llaman al método PUT de bloqueo de segmento para completar la operación, pero el último parámetro que pasa es diferente. En el código anterior, podemos ver que primero, calculamos el subíndice del bloqueo del segmento en la matriz en función del código hash de la tecla, y luego usamos el método GetObject de clase inseguro para leer el bloqueo del segmento de acuerdo con el subíndice. Dado que los elementos en la matriz de segmentos no se inicializan al construir el ConcurrentHashmap, se puede leer un valor nulo y se creará un nuevo bloqueo de segmento a través del método de gemido profundo. Después de obtener el bloqueo del segmento, llame a su método PUT para completar la operación de adición. Echemos un vistazo a cómo operarlo.
// Agregar pares de valor de clave Final V Put (K Key, Int Hash, V valor, Boolean Onlyifabsent) {// Intenta adquirir el bloqueo, si falla, Spin Hashentry <K, V> node = TryLock ()? NULL: ScanandlockFORPUT (clave, hash, valor); V OldValue; Pruebe {Hashentry <k, v> [] tab = table; // Calcule el subíndice del elemento int index = (tab.length - 1) & hash; // Obtenga el nodo de encabezado de la lista vinculada basada en el subíndice hashentry <k, v> first = entryat (tab, índice); para (hashentry <k, v> e = fRIf primer ;;) {// Transfiar la lista vinculada para encontrar el elemento, y if (e! = null) {k k; if ((k = e.key) == clave || (e.hash == hash && key.equals (k)))) {OldValue = e.Value; // Decide si reemplazar el valor anterior en función de los parámetros if (! Soloifabsent) {e.value = valor; ++ modcount; } romper; } e = E.Next; // Si no se encuentra, agregue un nodo a la lista vinculada} else {// Inserte el nodo del nodo en el encabezado de la lista vinculada if (node! = Null) {node.setNext (primero); } else {nodo = new Hashentry <k, v> (hash, clave, valor, primero); } // Después de insertar el nodo, siempre agregue 1 int c = recuento + 1; // Si el elemento excede el umbral, expanda la capacidad if (c> umbral && tab.length <maximum_capacity) {rehash (nodo); // de lo contrario, reemplace el subíndice de la tabla hash especificado con nodo de nodo} else {setentryat (tab, index, nodo); } ++ modcount; recuento = c; OldValue = nulo; romper; }}} finalmente {desbloqueo (); } return OldValue;}Para garantizar la seguridad del hilo, las operaciones de poner en bloqueos segmentados deben ser bloqueados, por lo que el hilo adquirirá el bloqueo al principio y continuará ejecutándose si la adquisición es exitosa. Si la adquisición falla, llame al método ScanandlockFifutput para que gire. Durante el proceso de giro, escanee la tabla hash para encontrar la clave especificada. Si la clave no existe, se creará un nuevo hashentry, por lo que no es necesario crearla nuevamente después de obtener el bloqueo. Para hacer algunas cosas mientras espera la cerradura, no perderá el tiempo en vano. Esto muestra las buenas intenciones del autor. Explicaremos el método de giro específico en detalle más adelante. Ahora, primero retire el enfoque. Después de que el hilo adquiere con éxito el bloqueo, obtendrá el elemento del subíndice especificado en función del subíndice calculado. En este momento, se obtiene el nodo de encabezado de la lista vinculada. Si el nodo de encabezado no está vacío, la lista vinculada será atravesada y registrada. Después de encontrarlo, decida si reemplazarlo en función del valor del parámetro OnlyFabsent. Si no se encuentra el recorrido, un nuevo hashentry señalará el nodo del encabezado. En este momento, si se crea un hashentry durante el giro, entonces apunte directamente a su lado al nodo de encabezado actual. Si no se crea el giro, se creará un nuevo hashentry aquí y apuntará al nodo del encabezado. Después de agregar elementos a la lista vinculada, verifique si el número total de elementos excede el umbral. Si excede, llame a Rehash para la expansión. Si no lo excede, consulte directamente el elemento subíndice correspondiente de la matriz al nodo recién agregado. El método SetEntryat cambia la referencia del elemento de matriz llamando al método PutOrderedObject de Inse Safe, que asegura que otros hilos puedan leer el último valor al leer.
7. ¿Cómo implementar la eliminación de elementos?
// Eliminar el elemento especificado (eliminar directamente después de encontrar el elemento correspondiente) public v Retemt (Key de objeto) {// Use la función hash para calcular el código hash int hash = hash (clave); // adquirir el índice del bloqueo del segmento basado en el segmento de código hash <k, v> s = segmentforhash (hash); // Calendar el método de eliminar el retorno del bloqueo del segmento S == NULL? NULL: S.Remove (clave, hash, nulo);} // Elimine el elemento especificado (elimina el valor igual al valor dado) Public boolean Eliminar (clave de objeto, valor de objeto) {// Use la función hash para calcular el código hash int hash = hash (clave); Segmento <k, v> s; // puede asegurarse de que el bloqueo del segmento no esté vacío antes de llamar al valor de retorno del método eliminar! = Null && (s = segmentforhash (hash))! = Null && s.remove (clave, hash, valor)! = Null;}Concurrenthashmap proporciona dos operaciones de eliminación, una es eliminarlo directamente después de encontrarlo, y el otro es compararlo primero y luego eliminarlo después de encontrarlo. Ambos métodos de eliminación deben encontrar el bloqueo de segmento correspondiente basado en el código hash de la tecla, y luego completar la operación de eliminación llamando al método de eliminación del bloqueo del segmento. Echemos un vistazo al método de eliminación de bloqueo de segmento.
// Elimine el elemento especificado final V Remete (clave de objeto, int hash, valor de objeto) {// intente adquirir el bloqueo, si falla, girar if (! Trylock ()) {scanandlock (clave, hash); } V OldValue = null; Pruebe {Hashentry <k, v> [] tab = table; // Calcule el subíndice del elemento int index = (tab.length - 1) & hash; // Obtener el elemento de matriz de acuerdo con el subíndice (nodo de encabezado de la lista de enlaces) Hashentry <k, v> e = entryat (tab, índice); Hashentry <k, v> pred = null; // Transfiere la lista vinculada para encontrar el elemento que se eliminará mientras (e! = Null) {k k; // Siguiente puntos al nodo sucesor del nodo actual hashentry <k, v> next = e.next; // busca el nodo correspondiente basado en la clave y el hash if ((k = e.key) == clave || (e.hash == hash && key.equals (k))) {v v = e.value; // omita el valor pasado en si no es igual a V, y elimínelo en otros casos if (value == null || value == v || value.equals (v)) {// Si pred está vacío, significa que el nodo a eliminar es el nodo de encabezado si (pred == null) {// reajuste el nodo de encabezado del setentryat de la lista vinculada (tab, Índice, índice, el siguiente); } else {// Establezca la sucesión del nodo Pred en el siguiente nodo pred.setNext (siguiente); } ++ modcount; --contar; // Registre el valor de la eliminación del elemento OldValue = V; } romper; } // Si E no es el nodo que está buscando, apunte la referencia de PRED a él pred = E; // Verifique el siguiente nodo E = Next; }} finalmente {desbloqueo (); } return OldValue;}Al eliminar elementos en las cerraduras de segmento, primero debe adquirir el bloqueo. Si la adquisición falla, llame al método Scanandlock para girar. Si la adquisición es exitosa, ejecute el siguiente paso. Primero calcule el subíndice de matriz y luego obtenga los elementos de la matriz de hashentry a través del subíndice. Aquí se obtiene el nodo de encabezado de la lista vinculada. A continuación, recorrer y buscar la lista vinculada. Antes de esto, use el siguiente puntero para registrar el nodo sucesor del nodo actual, y luego compare la clave y el hash para ver si es el nodo que está buscando. Si es así, realice el siguiente juicio IF. Si el valor está vacío o el valor es igual al valor actual del nodo, ingresará la instrucción IF para la eliminación, de lo contrario se omitirá directamente. Hay dos situaciones al realizar una operación de eliminación en una declaración IF. Si el nodo actual es un nodo de encabezado, entonces configure directamente el siguiente nodo como el nodo de encabezado. Si el nodo actual no es un nodo de encabezado, establezca el sucesor del nodo Pred en el siguiente nodo. El nodo Pred aquí representa el predecesor del nodo actual. Cada vez antes de verificar el siguiente nodo, Pred se apunta al nodo actual, lo que asegura que el nodo Pred sea siempre el predecesor del nodo actual. Tenga en cuenta que, a diferencia de JDK1.6, en JDK1.7, la siguiente variable del objeto Hashentry no es definitiva, por lo que puede eliminar el elemento modificando directamente el valor referenciado por Next. Dado que la siguiente variable es de tipo volátil, el hilo de lectura puede leer inmediatamente el último valor.
8. ¿Cómo se implementan específicamente los elementos de reemplazo?
// reemplazar el elemento especificado (operación CAS) public boolean reemplazar (k key, v OldValue, v NewValue) {// Use la función hash para calcular el código hash int hash = hash (clave); // Asegúrese de que OldValue y NewValue no estén vacíos si (OldValue == NULL || NewValue == NULL) arroje nuevo nullPointerException (); // Obtenga el índice del bloqueo del segmento basado en el segmento de código hash <k, v> s = segmentforhash (hash); // Llamando al método de reemplazo del bloqueo del segmento devuelve s! = Null && s.replace (key, hash, oldValue, newValue);} // Reemplazar operación de elemento (operación CAS) Final Boolean Reemplazar (k Key, int hash, v OldValue, v NewValue) {// intenta el bloqueo, si no logra (Spin if if if if (trylock () {Scanandlock); } boolean reemplazado = falso; Prueba {Hashentry <K, V> E; // Busque el nodo del encabezado directamente a través del hash y luego atraviese la lista vinculada para (e = entryforhash (this, hash); e! = Null; e = e.next) {k k; // Busque el nodo para ser reemplazado en función de la clave y hash if ((k = e.key) == clave || (e.hash == hash && key.equals (k))) {// Si el valor de corriente especificado es correcto, reemplace if (OldValue.equals (e.value)) {e.Value = newValue; ++ modcount; reemplazado = verdadero; } // de lo contrario, si no se realiza una operación, retroceda el descanso; }}} finalmente {desbloqueo (); } return reemplazado;}Concurrenthashmap también proporciona dos operaciones de reemplazo, una es reemplazar directamente después de encontrar, y la otra es comparar primero y luego reemplazar (operación CAS). La implementación de estas dos operaciones es aproximadamente la misma, excepto que la operación CAS tiene una capa adicional de operaciones de comparación antes de reemplazar, por lo que solo necesitamos comprender brevemente una de las operaciones. Aquí usamos operaciones CAS para el análisis, que sigue siendo una rutina antigua. Primero, encuentre el bloqueo de segmento correspondiente en función del código hash de la tecla, y luego llame a su método de reemplazo. Después de ingresar el método de reemplazo en el bloqueo del segmento, primero debe adquirir el bloqueo. Si la adquisición falla, gírela. Si la adquisición es exitosa, proceda al siguiente paso. Primero, obtenga el nodo de encabezado de la lista vinculada de acuerdo con el código hash, y luego atraviese y busque de acuerdo con la clave y el hash. Después de encontrar el elemento correspondiente, compare si el Valor OldValue dado es el valor actual. Si no, renuncia a la modificación y, si es así, reemplácela con el nuevo valor. Dado que el campo de valor del objeto Hashentry es de tipo volátil, se puede reemplazar directamente.
9. ¿Qué hiciste exactamente al girar?
// girar esperando para adquirir el bloqueo de bloqueo (operación de poner) Private Hashentry <k, v> scanandlockFifutput (k key, int hash, valor valor) {// Obtenga el nodo de encabezado de acuerdo con el código hash hashentry <k, v> first = entryforhash (this, hash); Hashentry <k, v> e = primero; Hashentry <k, v> nodo = null; int reintentos = -1; // girar while (! Trylock ()) {Hashentry <k, v> f; if (reinties <0) {// Si el nodo de encabezado está vacío, cree un nuevo nodo if (e == null) {if (node == null) {nodo = new Hashentry <k, v> (hash, key, value, null); } reintentos = 0; // de lo contrario, atraviese la lista vinculada para localizar el nodo} else if (key.equals (e.key)) {reinties = 0; } else {e = E.Next; } // reintentos agregue 1 aquí cada vez y determine si excede el valor máximo} else if (++ reintentos> max_scan_retries) {lister (); romper; // Cuando los reintentos son uniformes, determine si el primero ha cambiado} else if ((reintentos & 1) == 0 && (f = EntryforHash (this, hash))! = Primero) {e = first = f; reintentos = -1; }} nodo de retorno;} // girar esperando para adquirir bloqueo (eliminar y reemplazar las operaciones) vacío privado scanandlock (clave de objeto, int hash) {// Obtenga el nodo de encabezado de la lista vinculada de acuerdo con el código hash hashentry <k, v> primero = entryforhash (this, hash); Hashentry <k, v> e = primero; int reintentos = -1; // girar while (! Trylock ()) {Hashentry <k, v> f; if (reinties <0) {// Transferir la lista vinculada para localizar el nodo if (e == null || key.equals (e.key)) {reinties = 0; } else {e = E.Next; } // reintentos agregue 1 aquí cada vez y determine si excede el valor máximo} else if (++ reintentos> max_scan_retries) {lister (); romper; // Cuando los reintentos son uniformes, determine si el primero ha cambiado} else if ((reintentos & 1) == 0 && (f = EntryforHash (this, hash))! = Primero) {e = first = f; reintentos = -1; }}}Como mencionamos anteriormente, poner, eliminar y reemplazar las operaciones en cerraduras segmentadas requieren que el bloqueo se adquiera primero. Solo después de obtener con éxito el bloqueo se puede realizar la siguiente operación. Si la adquisición falla, se realizará el giro. La operación de giro también se agrega en JDK1.7. Para evitar la suspensión frecuente y el despertar de hilos, puede mejorar el rendimiento durante las operaciones concurrentes. El SCANAndLockFifut se llama en el método PUT, y el escaneandlock se llama en los métodos de eliminación y reemplazo. Los dos métodos de giro son más o menos los mismos, aquí solo analizamos el método ScanandlockForcut. En primer lugar, debe obtener el nodo de encabezado de la lista vinculada basada en el código hash. Luego, el hilo entrará en el bucle While para ejecutar. La única forma de salir del bucle es adquirir con éxito el bloqueo, y el hilo no se suspenderá durante este período. Cuando el bucle acaba de ingresar, el valor de reintentos es -1. En este momento, el hilo no intentará adquirir el bloqueo de inmediato. En cambio, primero encontrará el nodo correspondiente a la clave (si no se encuentra, se creará una nueva), y luego establecerá las reintentos en 0. Luego, intentará adquirir el bloqueo una y otra vez. El valor de reintentos correspondientes también se agregará 1 cada vez hasta que el número máximo de intentos exceda el número máximo de intentos. Si no se ha obtenido el bloqueo, se solicitará el método de bloqueo para bloquear y obtener. Durante el intento de adquirir el bloqueo, verificará si el nodo de encabezado se ha cambiado cada otra vez (los requisitos son pares). Si se cambia, restablezca los reintentos a -1 y luego repita el proceso justo ahora. Esto es lo que hace el hilo al girar. Cabe señalar que si se ha detectado el nodo de la cabeza para cambiar durante el giro, se extenderá el tiempo de giro del hilo.
10. ¿Qué operaciones se realizan al expandir la tabla hash?
// hash nuevamente @SupessWarnings ("no controlado") Private void Rehash (Hashentry <K, V> nodo) {// Obtenga la referencia a la antigua tabla hash hashentry <k, v> [] oldtable = table; // Obtener la capacidad de la antigua tabla hash int // Calcule la capacidad de la nueva tabla hash (2 veces la tabla hash anterior) int NewCapacity = OldCapacity << 1; // Calcule el umbral de umbral del nuevo elemento = (int) (newCapacity * LoadFactor); // Crear una nueva matriz de Hashentry Hashentry <k, v> [] newtable = (hashentry <k, v> []) New Hashentry [NewCapacity]; // Generar un nuevo valor de máscara int SizEmask = NewCapacity - 1; // Tranquilidad a través de todos los elementos de la tabla antigua para (int i = 0; i <OldCapacity; i ++) {// Obtenga el nodo de encabezado de la lista vinculada Hashentry <k, v> e = oldtable [i]; if (e! = null) {hashentry <k, v> next = e.next; // Calcule el índice del elemento en la nueva tabla int idx = e.hash & sizEmask; // Siguiente está vacío para indicar que solo hay un nodo en la lista vinculada if (next == null) {// colocar el nodo directamente en la nueva tabla newtable [idx] = e; } else {Hashentry <k, v> lastrun = e; int lastidx = idx; // coloca el nodo Lastrun y coloca directamente el nodo después de Latrun en la nueva tabla para (hashentry <k, v> last = next; last! = Null; last = last.next) {int k = last.hash & sizEmask; if (k! = lastidx) {lastidx = k; lastrun = último; }} newtable [lastIdx] = lastrun; // Transipate los elementos antes del nodo Latrun de la lista vinculada, cottalos en la nueva tabla a su vez para (Hashentry <k, v> p = e; p! = Lastrun; p = p.next) {v v = p.value; int h = p.hash; int k = H & SizEmask; Hashentry <k, v> n = newtable [k]; newtable [k] = new Hashentry <k, v> (h, p.key, v, n); }}}}} // Calcule el subíndice del nodo entrante en la nueva tabla int nodeindex = node.hash & SizEmask; // Agregue el nodo entrante al nodo de encabezado de la lista vinculada node.setNext (newtable [nodeindex]); // Intercambia el elemento subíndice especificado de la nueva tabla con el nodo entrante newtable [nodeindex] = node; // señala la referencia de la tabla hash a la nueva tabla de tabla = newtable;}El método de repetición se llama en el método PUT. Sabemos que cuando se pone el método Put, el nuevo elemento se creará y se agregará a la matriz hash. Cuanto mayor sea la posibilidad de conflictos hash, mayor será el rendimiento de la tabla hash también disminuirá. Por lo tanto, cada vez que la operación de PUT, verificará si el número total de elementos excede el umbral. Si excede el umbral, se llamará al método de rehacer para expandir la capacidad. Debido a que la longitud de la matriz ya no se puede cambiar una vez que se determina, se debe crear una nueva matriz para reemplazar la matriz original. Desde el código, puede saber que la matriz recién creada es el doble de la longitud de la matriz original (OldCapacity << 1). After creating a new array, you need to move all elements in the old array into the new array, so you need to calculate the subscript of each element in the new array. The process of calculating the new subscript is shown in the figure below.
我们知道下标直接取的是哈希码的后几位，由于新数组的容量是直接用旧数组容量右移1位得来的，因此掩码位数向右增加1位，取到的哈希码位数也向右增加1位。如上图，若旧的掩码值为111，则元素下标为101，扩容后新的掩码值为1111，则计算出元素的新下标为0101。由于同一条链表上的元素下标是相同的，现在假设链表所有元素的下标为101，在扩容后该链表元素的新下标只有0101或1101这两种情况，因此数组扩容会打乱原先的链表并将链表元素分成两批。在计算出新下标后需要将元素移动到新数组中，在HashMap中通过直接修改next引用导致了多线程的死锁。虽然在ConcurrentHashMap中通过加锁避免了这种情况，但是我们知道next域是volatile类型的，它的改动能立马被读线程读取到，因此为保证线程安全采用复制元素来迁移数组。但是对链表中每个元素都进行复制有点影响性能，作者发现链表尾部有许多元素的next是不变的，它们在新数组中的下标是相同的，因此可以考虑整体移动这部分元素。具统计实际操作中只有1/6的元素是必须复制的，所以整体移动链表尾部元素(lastRun后面的元素)是可以提升一定性能的。
注：本篇文章基于JDK1.7版本。
Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.