Descripción general de hashmap
Hashmap es una implementación asincrónica de la interfaz MAP basada en la tabla hash. Esta implementación proporciona todas las operaciones de mapeo opcionales y permite el uso de valores nulos y claves nulas. Esta clase no garantiza el orden de las asignaciones, especialmente no garantiza que el pedido durará.
Estructura de datos de Hashmap
En el lenguaje de programación Java, hay dos estructuras básicas, una es una matriz y la otra es un puntero simulado (referencia). Todas las estructuras de datos se pueden construir utilizando estas dos estructuras básicas, y HASHMAP no es una excepción. Hashmap es en realidad una estructura de datos de "Lista de hash", es decir, la estructura de matrices y listas vinculadas, pero en JDK1.8
Se agrega la implementación del árbol rojo y negro. Cuando la longitud de la lista vinculada es mayor que 8, se convierte en la estructura del árbol rojo y negro.
Como se puede ver en la figura anterior, HashMap utiliza el método de dirección de cadena en Java. El método de dirección de enlace, en pocas palabras, es una combinación de matrices y listas vinculadas. Hay una estructura de lista vinculada en cada elemento de matriz. Cuando se hashan los datos, se obtiene el subíndice de matriz y los datos se colocan en la lista vinculada de los elementos de subíndice correspondientes.
*/ nodo de clase static <k, v> implementa map.entry <k, v> {final int hash; // utilizado para localizar la posición de la tecla K final de la matriz final; V valor; Nodo <k, v> next; // Nodo siguiente en el nodo de lista vinculada (int hash, k key, valor v, nodo <k, v> next) {this.hash = hash; this.key = key; this.Value = value; this.next = siguiente; }El nodo es una clase interna de hashmap, que implementa la interfaz MAP.Entry, que es esencialmente un mapa (par de valores clave).
A veces, se colocan dos claves en la misma posición, lo que indica que ocurrió una colisión hash. Por supuesto, cuanto más uniforme sean los resultados del cálculo del algoritmo hash, menor es la probabilidad de colisión hash y mayor es la eficiencia de acceso del mapa.
Hay un campo muy importante en la clase de hashmap, que es la tabla de nodo [], es decir, la matriz de cubos hash. Obviamente es una variedad de nodos.
Si la matriz de cubos hash es grande, incluso el algoritmo de hash pobre estará más disperso. Si la matriz de matriz de matriz de hash es pequeña, incluso un buen algoritmo de hash tendrá más colisiones, por lo que es necesario sopesar el costo del espacio y el costo de tiempo. De hecho, es para determinar el tamaño de la matriz de cubos hash en función de la situación real y, sobre esta base, el algoritmo hash diseñado reducirá las colisiones hash. Entonces, ¿cómo podemos controlar los mapas para hacer que la probabilidad de colisiones hash sea pequeña, y las matrices de cubos hash (tablas de nodo []) ocupan menos espacio? La respuesta es un buen algoritmo de hash y mecanismo de expansión de capacidad.
Antes de comprender el hash y el proceso de expansión, necesitamos comprender varios campos de hashmap. Desde el código fuente del constructor predeterminado de HashMap, se puede ver que el constructor inicializa los siguientes campos, el código fuente es el siguiente:
umbral int; // El valor clave que se puede acomodar es Ultimate Float LoadFactor; // Factor de carga int mod. tamaño int;
Primero, la longitud de inicialización de la tabla de nodo [] (el valor predeterminado es 16), el factor de carga es el factor de carga (el valor predeterminado es 0.75) y el umbral es el número de nodo (pares de valor clave) de la cantidad máxima de datos que HASHMAP puede acomodar. umbral = longitud * factor de carga. Es decir, después de que la matriz haya definido su longitud, cuanto mayor sea el factor de carga, más pares de valor clave puede acomodar.
Según la fórmula de definición del factor de carga, se puede ver que el umbral es el número máximo de elementos permitidos según este factor de carga y longitud (longitud de la matriz). Si este número excede esto, cambie el tamaño (amplíe la capacidad). La capacidad de hashmap ampliada es el doble de la capacidad anterior. El factor de carga predeterminado 0.75 es una opción equilibrada para el espacio y la eficiencia del tiempo. Se recomienda que no lo modifique a menos que en el caso de tiempo y espacio especiales, si hay mucho espacio de memoria y requisitos de eficiencia de alta tiempo, el valor del factor de carga de carga puede reducirse; Por el contrario, si el espacio de memoria es apretado y los requisitos de eficiencia de tiempo no son altos, el valor del factor de carga del factor de carga puede aumentar, lo que puede ser mayor que 1.
El campo de tamaño es realmente fácil de entender, es la cantidad de pares de valor clave que realmente existen en Hashmap. Tenga en cuenta la diferencia entre la longitud de la tabla y el número de umbrales que acomodan los pares de valor de clave máximos. El campo ModCount se utiliza principalmente para registrar el número de cambios en la estructura interna de HASHMAP, y se usa principalmente para la rápida falla de la iteración. Para enfatizar, los cambios en la estructura interna se refieren a los cambios en la estructura, como poner nuevos pares de valor clave, pero el valor correspondiente a una clave se sobrescribe y no pertenece a cambios estructurales.
En el hashmap, la longitud de la tabla de matriz de cubos hash debe estar en la potencia n de 2 (debe ser un número compuesto). Este es un diseño no convencional. El diseño convencional es diseñar el tamaño del cubo como un número primo. Relativamente hablando, la probabilidad de conflicto causada por números primos es menor que la de los números compuestos. Para pruebas específicas, consulte //www.vevb.com/article/100911.htm. La hashtable inicializa el tamaño del cubo a 11, que es la aplicación del tamaño del cubo diseñado como números primos (no se puede garantizar que se garantice números primos después de la expansión). Hashmap adopta este diseño no convencional, principalmente para optimizar cuando el módulo y la expansión. Al mismo tiempo, para reducir los conflictos, Hashmap también agrega el proceso de participación de alta bits en la computación al localizar la posición del índice de cubo hash.
Hay un problema aquí. Incluso si el factor de carga y el algoritmo hash se diseñan razonablemente, inevitablemente habrá una situación en la que la cremallera sea demasiado larga. Una vez que la cremallera sea demasiado larga, afectará seriamente el rendimiento de HashMap. Por lo tanto, en la versión JDK1.8, la estructura de datos se optimizó aún más y se introdujo el árbol rojo y negro. Cuando la longitud de la lista vinculada es demasiado larga (el valor predeterminado es más de 8), la lista vinculada se convierte en un árbol rojo y negro. Las características de la adición rápida, deleciones, modificaciones y búsquedas en el árbol rojo y negro se utilizarán para mejorar el rendimiento de HASHMAP. La inserción, la eliminación y la búsqueda de árboles rojos y negros se utilizarán para insertar, eliminar y buscar algoritmos como el árbol rojo y negro.
Determine la posición de índice de la matriz de cubos hash
Implementación del código:
// Método 1: static final int hash (clave de objeto) {//jdk1.8 & jdk1.7 int h; // h = key.hashcode () obtiene el valor hashcode para el primer paso // h ^ (h >>> 16) ¿Participa en la operación del retorno del segundo paso (clave == nulo)? 0: (h = key.hashcode ()) ^ (h >>> 16);} // Método 2: static int indexFor (int h, int longitud) {//jdk1.7 código fuente, jdk1.8 no tiene este método, pero el principio de implementación es el mismo retorno h & (longitud-1); // El tercer paso toma la operación del módulo}El algoritmo hash aquí es esencialmente tres pasos: tomar el valor de hashcode de la clave, la operación de alto bit y la operación de módulo.
Para cualquier objeto dado, siempre que su valor de retorno hashcode () sea el mismo, el código hash calculado por el método de llamadas del programa uno siempre es el mismo. Lo primero que pensamos es modular el valor hash a la longitud de la matriz, de modo que la distribución de elementos es relativamente uniforme. Sin embargo, el consumo de operaciones de módulo es relativamente grande. Esto se realiza en HASHMAP: Método de llamada dos para calcular qué índice se debe almacenar el objeto en la matriz de tabla.
Este método es muy inteligente. Obtiene los bits guardados del objeto a través de h & (table.length -1), y la longitud de la matriz subyacente de hashmap siempre es para la potencia n de 2, que es la optimización de hashmap en términos de velocidad. Cuando la longitud siempre es a la potencia de N de 2, la operación H & (Longitud-1) es equivalente a la longitud del módulo, es decir, la longitud de H %, pero y tiene mayor eficiencia que %.
En la implementación de JDK1.8, el algoritmo para las operaciones de alta bits está optimizado, y la implementación de HashCode (): (H = K.hashcode ()) ^ (H >> 16), que se considera principalmente a partir de la velocidad, eficiencia y calidad. Esto puede garantizar que cuando la longitud de la tabla de matriz sea relativamente pequeña, también puede garantizar que los bits estén involucrados en los cálculos hash teniendo en cuenta el alto-bajo, y no habrá sobrecarga excesivo.
Aquí hay un ejemplo, n es la longitud de la tabla.
Implementación de métodos de put put hashmap
La idea general de la función PUT es:
El código específico se implementa de la siguiente manera:
public v put (k key, v valor) {return PutVal (hash (clave), clave, valor, falso, verdadero); } / ***Método para generar hash* / static final int hash (clave de objeto) {int h; return (clave == nulo)? 0: (h = key.hashcode ()) ^ (h >>> 16); } final V PUTVAL (int hash, k key, v valor, boolean soloifabsent, boolean desalojo) {nodo <k, v> [] tabs; Nodo <k, v> p; int n, i; // juzga si la tabla está vacía, if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize ()). Longitud; // Cree una nueva matriz de tabla y obtenga la longitud de la matriz // calcule el valor de hash al índice de la matriz insertado I de acuerdo con la tecla de valor clave. Si la tabla [i] == null, cree directamente un nuevo nodo y agregue if ((p = tab [i = (n - 1) & hash]) == NULL) TAB [i] = newnode (hash, key, value, null); else {// si el nodo correspondiente tiene el nodo <k, v> e; K k; // juzga si el primer elemento de la tabla [i] es el mismo que la clave, si es lo mismo, sobrescribe directamente el valor if (p.hash == hash && ((k = p.key) == clave || (key! = Null && key.equals (k)))) e = p; // juzga si la tabla [i] es un treenode, es decir, si la tabla [i] es un árbol rojo-negro. Si se trata de un árbol rojo negro, inserte directamente el par de valores clave en el árbol de lo contrario si (p instancia de treeNode) e = ((treeNode <k, v>) p) .putTreeval (this, tab, hash, key, valor); // Esta cadena es una lista vinculada más {// Transipate a través de la tabla [i] para determinar si la longitud de la lista vinculada es mayor que Treify_threshold (el valor predeterminado es 8). Si es mayor de 8, convierta la lista vinculada en un árbol rojo-negro y realice la operación de inserción en el árbol rojo-negro. De lo contrario, se realiza la operación de inserción de la lista vinculada; Si se encuentra que la clave ya tiene un valor de sobrescrito directo durante el proceso de transversal; for (int bincount = 0;; ++ bincount) {if ((e = p.next) == null) {p.next = newnode (hash, key, valor, nulo); if (bincount> = treeify_threshold - 1) // -1 para 1st TreifyBin (Tab, hash); romper; } if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) break; P = E; }} // escribir if (e! = Null) {// asignación existente para la clave v oldValue = e.value; if (! SOLDIFABSENT || OldValue == NULL) E.Value = Value; TownodeAccess (E); devolver OldValue; }} ++ modcount; // Después de que la inserción sea exitosa, determine si el número real de pares de valor clave excede el umbral de capacidad máxima. Si excede la capacidad, expanda if (++ size> umbral) reize (); ToomdodeSertion (desalojo); regresar nulo; }Implementación de método de hashmap get
La idea es la siguiente:
1. El primer nodo en el cubo, presione directamente;
2. Si hay un conflicto, use Key.Equals (k) para encontrar la entrada correspondiente
Si es un árbol, busque en el árbol a través de Key.Equals (k), o (logn);
Si es una lista vinculada, busque a través de Key.Equals (k) en la lista vinculada, o (n).
public v get (clave de objeto) {nodo <k, v> e; return (e = getNode (hash (key), key)) == NULL? NULL: E.Value; } nodo final <k, v> getNode (int hash, clave de objeto) {nodo <k, v> [] pestina; Nodo <k, v> primero, e; int n; K k; if ((tab = table)! = null && (n = tab.length)> 0 && (first = tab [(n - 1) & hash])! = null) {// presione directamente if (first.hash == hash && // cada vez que se verifica el primer nodo ((k = primero.key) == Key || // perdió if ((e = first.next)! = Null) {// get if (primera instancia de treeNode) return ((treeNode <k, v>) primero) .getTreeNode (hash, key); // get do {if (e.hash == hash && ((k = e.key) == key || (key! = Null && key.equals (k)))) return e; } while ((e = e.next)! = null); }} return null; }Mecanismo de expansión de capacidad
El cambio de tamaño significa recalcular la capacidad y agregar constantemente elementos al objeto hashmap. Cuando la matriz dentro del objeto hashmap no puede cargar más elementos, el objeto debe expandir la longitud de la matriz para que se puedan cargar más elementos. Por supuesto, las matrices en Java no se pueden ampliar automáticamente. El método es usar una nueva matriz en lugar de matrices existentes con pequeña capacidad, al igual que usamos un pequeño cubo para llenar agua. Si queremos llenar más agua, tenemos que reemplazarla con un balde grande.
Analizamos el código fuente de cambio de tamaño. Dado que JDK1.8 integra árboles rojos y negros, es más complicado. Para facilitar la comprensión, todavía usamos el código JDK1.7, que es más fácil de entender. Hay poca diferencia en la esencia. Hablemos de las diferencias específicas más adelante.
Void reize (int newCapacity) {// pausa de la nueva capacidad de entrada [] oldTable = table; // Haga referencia a la matriz de entrada antes de la expansión int if (OldCapacity == Maximum_Capacity) {// Si el tamaño de la matriz antes de la expansión ha alcanzado el umbral máximo (2^30) = integer.max_value; // Modificar el umbral al valor máximo de int (2^31-1), de modo que la capacidad no se ampliará en el retorno futuro; } Entrada [] newtable = nueva entrada [newCapacity]; // Inicializar una nueva transferencia de matriz de entrada (NewTable); //! ! Transferir datos a la nueva tabla de matriz de entrada = newtable; // El atributo de tabla de hashmap se refiere al nuevo umbral de matriz de entrada = (int) (newCapacity * LoadFactor); // modificar el umbral}Aquí usamos una matriz con mayor capacidad en lugar de una matriz existente con menor capacidad. El método Transfer () copia los elementos de la matriz de entrada original a la nueva matriz de entrada.
transferencia void (entrada [] newtable) {Entry [] src = table; // src se refiere a la matriz de entrada anterior int newCapacity = newtable.length; para (int j = 0; j <src.length; j ++) {// tranquilidad a través de la entrada de matriz de entrada anterior <k, v> e = src [j]; // Obtenga cada elemento de la matriz de entrada anterior if (e! = Null) {src [j] = null; // libera la referencia de objeto de la matriz de entrada anterior (después del bucle for, la matriz de entrada anterior ya no se refiere a ningún objeto) do {Entry <k, v> next = e.next; int i = indexfor (E.Hash, Newcapacity); //! ! Recalcule la posición de cada elemento en la matriz E.Next = NewTable [i]; // etiqueta [1] newtable [i] = e; // Pon el elemento en la matriz e = siguiente; // acceder al elemento en la siguiente cadena de entrada} while (e! = Null); }}}La referencia a Newtable [i] se asigna a E.Next, lo que significa que se utiliza el método de inserción del encabezado de una sola lista vinculada. Los nuevos elementos en la misma posición siempre se colocarán en el cabezal de la lista vinculada; De esta manera, los elementos colocados en un índice eventualmente se colocarán al final de la cadena de entrada (si se produce un conflicto hash). Esto es diferente de JDK1.8, que se explica en detalle a continuación. Los elementos en la misma cadena de entrada en la matriz anterior se pueden colocar en diferentes posiciones en la nueva matriz después de recalcular la posición del índice.
Aquí hay un ejemplo para ilustrar el proceso de expansión de la capacidad. Suponga que nuestro algoritmo hash simplemente usa el MOD clave para obtener el tamaño de la tabla (es decir, la longitud de la matriz). El tamaño de la tabla de matriz de cubo hash = 2, por lo que la clave = 3, 7, 5, y el orden de puts es 5, 7 y 3. Después del mod 2, el conflicto está en la tabla [1]. Aquí, se supone que el factor de carga LoadFactor = 1, es decir, cuando el tamaño real del par de valor clave es mayor que el tamaño real de la tabla, se expande. Los siguientes tres pasos son el proceso de cambiar el tamaño de la matriz de cubos hash a 4, y luego rehacer todos los nodos.
Expliquemos qué optimizaciones se han hecho en JDK1.8. Después de la observación, podemos encontrar que estamos utilizando una potencia de dos expansión (refiriéndose a la longitud de dos veces el original), por lo que la posición del elemento está en la posición original o mueve la posición de la potencia de dos nuevamente en la posición original. Mirando la figura a continuación, puede comprender el significado de esta oración. n es la longitud de la mesa. La Figura (a) representa un ejemplo de la posición de índice de las dos claves que determinan la posición de índice de la clave1 y la clave2 antes de la expansión. La figura (b) representa un ejemplo de la posición de índice de la clave1 y la tecla2 después de la expansión. Donde hash1 es el hash y el resultado de la operación de alto bit correspondiente a Key1.
Después de que el elemento recalcula hash, ya que N se convierte en 2 veces, el rango de máscara de N-1 es de 1 bit (rojo) en el punto alto, por lo que el nuevo índice cambiará así:
Por lo tanto, cuando expandimos el hashmap, no necesitamos recalcular el hash como la implementación de JDK1.7. Solo necesitamos ver si el bit agregado al valor hash original es 1 o 0. Si es 0, el índice no ha cambiado. Si es 1, el índice se convierte en "Índice original + OldCap". Puede ver la siguiente figura como el diagrama de cambio de tamaño con 16 expansión a 32:
Este diseño es de hecho muy inteligente, lo que no solo ahorra el tiempo para recalcular el valor hash, sino también, ya que el 1bit recién agregado es 0 o 1, sino que puede considerarse aleatorio, por lo que el proceso de cambio de tamaño distribuye los nodos en conflicto anteriores al nuevo cubo. Este es el nuevo punto de optimización agregado por JDK1.8. Hay un poco de atención a la diferencia. Cuando se rehash en JDK1.7, cuando las viejas listas vinculadas migran nuevas listas vinculadas, si la posición del índice de matriz de la nueva tabla es la misma, los elementos de la lista vinculada se invertirán, pero como se puede ver en la figura anterior, JDK1.8 no se invertirá. Los estudiantes interesados pueden estudiar el código fuente de cambio de tamaño de JDK1.8, que es muy bueno, como sigue:
nodo final <k, v> [] resize () {nodo <k, v> [] oldtab = table; int 0: Oldtab.length; int int NewCap, novato = 0; if (OldCap> 0) {// Si el valor máximo excede, ya no se expandirá, por lo que tengo que chocar con usted if (OldCap> = Maximum_Capacity) {Umshold = Integer.max_value; regresar Oldtab; } // Si no se excede el valor máximo, se expandirá a 2 veces el original if ((newCap = OldCap << 1) <Maximum_Capacity && OldCap> = default_initial_capacity) Newthr = Oldthr << 1; // umbral doble} else if (oldthr> 0) // La capacidad inicial se colocó en umbral newCap = Oldthr; else {// umbral inicial cero significa utilizando valores predeterminados newCap = default_initial_capacity; newthr = (int) (default_load_factor * default_initial_capacity); } // Calcule el nuevo límite superior de cambio de tamaño if (newthr == 0) {float ft = (float) newCap * LoadFactor; newthr = (newCap <maximum_capacity && ft <(float) maximum_capacity? (int) ft: integer.max_value); } umbral = novato; @SupplesSwarnings ({"RawTypes", "sin verificar"}) nodo <k, v> [] newtab = (nodo <k, v> []) nuevo nodo [newCap]; tabla = newtab; if (oldtab! = null) {// mueve cada cubo a los nuevos cubos para (int j = 0; j <oldcap; ++ j) {nodo <k, v> e; if ((e = oldtab [j])! = null) {oldtab [j] = null; if (E.Next == NULL) Newtab [E.Hash & (NewCap - 1)] = E; else if (e instancia de treeNode) ((treeNode <k, v>) e) .split (this, newtab, j, OldCap); else {// preservar el nodo de orden <k, v> lohead = null, lotail = null; Nodo <k, v> hihead = null, hitail = null; Nodo <k, v> siguiente; do {next = E.Next; // índice original if ((e.hash & oldcap) == 0) {if (lotail == null) lohead = e; else lotail.next = e; lotail = e; } // Índice original + OldCap else {if (HitAil == NULL) HiHEAD = E; else Hitail.next = E; hitail = e; }} while ((e = next)! = null); // Ponga el índice original en el cubo if (lotail! = Null) {lotail.next = null; newtab [j] = lohead; } // Coloque el índice original + OldCap en el cubo if (Hitail! = NULL) {HitAil.Next = NULL; newtab [J + OldCap] = Hihead; }}}}} return newtab;}Resumir
Ahora podemos responder varias preguntas al principio para profundizar nuestra comprensión del hashmap:
1. ¿Cuándo se usará hashmap? ¿Cuáles son sus características?
Se basa en la implementación de la interfaz MAP. Al almacenar pares de valor clave, puede recibir valores de claves nulos, que es asíncrono. HASHMAP STORE ENTRAD (Hash, Key, Value, Next) objetos.
2. ¿Sabes cómo funciona hashmap?
A través del método hash, los objetos se almacenan y obtienen a través de Put and Get. Al almacenar un objeto, cuando pasamos K/V al método Put, llama a hashcode para calcular el hash para obtener la ubicación del cubo y almacenarlo más. HashMap ajustará automáticamente la capacidad de acuerdo con la ocupación actual del cubo (si excede la carga FACOTR, el cambio de tamaño es el doble del original). Al obtener el objeto, pasamos K para obtener, lo que llama al hashcode para calcular el hash para obtener la posición del cubo, y aún más llama al método igual () para determinar el par de valores clave. Si se produce una colisión, HashMap organiza los elementos que generan conflictos de colisión a través de la lista vinculada. En Java 8, si los elementos que chocan en un cubo exceden un cierto límite (el valor predeterminado es 8), se usa un árbol rojo y negro para reemplazar la lista vinculada para aumentar la velocidad.
3. ¿Conoces los principios de Get and Put? ¿Cuáles son las funciones de igual () y hashcode ()?
Al hash el hashcode () de la clave y calcular el subíndice (N-1 y hash), se obtiene la posición de los cubos. Si se produce una colisión, use el método Key.equals () para buscar el nodo correspondiente en la lista o el árbol vinculado
4. ¿Conoces la implementación del hash? ¿Por qué necesito hacer esto?
En la implementación de Java 1.8, se implementa a través del X-o bajo de 16 bits de 16 bits de hashcode (): (h = k.hashcode ()) ^ (h >>> 16), que se considera principalmente a partir de la velocidad, la eficiencia y la calidad. Esto puede garantizar que cuando la N del cubo sea relativamente pequeña, también puede garantizar que tanto los bits altos como los bajos estén involucrados en el cálculo del hash, y no habrá sobrecarga excesiva.
5. ¿Qué pasa si el tamaño de hashmap excede la capacidad definida por el factor de carga?
Si se excede el factor de carga (predeterminado 0.75), un hashmap con el doble de la longitud original se cambiará el tamaño y se volverá a llamar al método hash.
La hoja de trucos sobre las colecciones Java se describe de la siguiente manera:
La matriz de cubo hash implementada con la matriz de entrada [], y el valor hash de la clave se puede usar para obtener el subíndice de la matriz.
Al insertar un elemento, si dos claves caen en el mismo cubo (por ejemplo, después de que los valores hash 1 y 17 son Modulo 16, ambas pertenecen al primer cubo hash), la entrada utiliza una siguiente propiedad para implementar múltiples entradas en una lista vinculada unidireccional, y la entrada que ingresa al depósito de la entrada al lado de la entrada actual del cubo.
Cuando busque una clave con un valor hash de 17, primero ubique el primer cubo hash, luego itera a través de todos los elementos en el cubo con una lista vinculada, y compare sus valores clave uno por uno.
Cuando el número de entrada alcanza el 75% de los cubos (muchos artículos dicen que el número de cubos utilizados alcanza el 75%, pero de acuerdo con el código, la matriz de cubos se ampliará exponencialmente y toda la entrada original se reasignará, por lo que es mejor tener un valor estimado aquí.
La operación de bits (hash y (arrayLength-1)) será más rápido, por lo que el tamaño de la matriz siempre es para la potencia n de 2. Si da un valor inicial como 17, se convertirá en 32. El valor inicial predeterminado cuando el elemento se coloca por primera vez es 16.
Iterator () atraviesa a lo largo de la matriz de cubos hash, que parece un servicio fuera de servicio.
6. ¿Qué sucede cuando el hashcode de dos objetos es el mismo?
Debido a que el hashcode es el mismo, su posición de cubo es la misma y ocurrirá una 'colisión'. Debido a que HashMap usa una lista vinculada para almacenar objetos, esta entrada (el objeto MAP.Entry que contiene pares de valores clave) se almacena en la lista vinculada.
7. Si el cloque de dos claves es el mismo, ¿cómo se obtiene el objeto de valor?
Después de encontrar la ubicación del cubo, se llamará al método Keys.equals () para encontrar el nodo correcto en la lista vinculada y finalmente encontrar el objeto de valor que se encuentra. Por lo tanto, al diseñar el tipo clave de hashmap, si un objeto inmutable se declara como final y se utilizan los métodos iguales () y hashcode () apropiados, la aparición de colisiones se reducirá y la eficiencia mejorará. La inmutabilidad puede almacenar en caché de hashcodes para diferentes claves, lo que aumentará la velocidad de obtener todo el objeto. Usar clases de envoltura como String and Interger como teclas es una muy buena opción.
8. ¿Qué pasa si el tamaño de hashmap excede la capacidad definida por el factor de carga?
El tamaño del factor de carga predeterminado es 0.75. Es decir, cuando un mapa llena un 75% de cubos, como otras clases de recolección (como ArrayList, etc.), se creará una matriz de cubos que es dos veces el tamaño del hashmap original para cambiar el tamaño del mapa y colocar el objeto original en la nueva matriz de cubos. Este proceso se llama rehacer porque llama al método hash para encontrar la nueva ubicación del cubo
9. ¿Entiendes lo que hay de malo en cambiar el tamaño de el hashmap?
Al cambiar el tamaño de HASHMAP, de hecho existe una competencia condicional, porque si ambos hilos encuentran que Hashmap necesita cambiar el tamaño, intentarán cambiar el tamaño al mismo tiempo. Durante el proceso de cambio de tamaño, el orden de los elementos almacenados en la lista vinculada se revertirá, porque cuando se mueve a la nueva posición del cubo, HashMap no coloca los elementos al final de la lista vinculada, sino en la cabeza, que es evitar el recorrido de la cola. Si se produce una competencia condicional, entonces hay un círculo vicioso. Por lo tanto, en un entorno concurrente, usamos CurrentHashMap para reemplazar el hashmap
10. ¿Por qué las clases de envoltura son como String and Interger adecuadas como teclas?
Porque la cadena es inmutable y final, y los métodos iguales () y hashcode () se han reescrito. Otras clases de envoltura también tienen esta característica. La inmutabilidad es necesaria porque para calcular hashcode (), debe evitar que el valor clave cambie. Si el valor clave devuelve un CCODE diferente al poner y obtener, no puede encontrar el objeto que desea del hashmap. La inmutabilidad tiene otras ventajas, como la seguridad de los subprocesos. Si puede garantizar que el hashcode no cambie solo al declarar un campo como final, entonces hágalo. Debido a que los métodos iguales () y hashcode () se utilizan al obtener objetos, es muy importante reescribir estos dos métodos correctamente. Si dos objetos desiguales devuelven diferentes hashcodes, la posibilidad de colisión será menor, lo que mejorará el rendimiento de HASHMAP
Gracias por leer, espero que pueda ayudarte. ¡Gracias por su apoyo para este sitio!