Marque, y al mismo tiempo, puede combinar bien los métodos hashcode () y igual (). hashcode () no es igual, debe ser también diferente para poder deducir iguales ();
Porque cuando hashmap, primero compare hashcode, luego compare iguales, hashcode == && iguales, ambos son verdaderos, por lo que se considera la misma clave
1. 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á.
2. Estructura de datos de hashmap:
En el lenguaje de programación de Java, hay dos estructuras básicas, una es una matriz y la otra es un puntero simulado (referencia). Hashmap es en realidad una estructura de datos de "Lista vinculada", es decir, una combinación de matrices y listas vinculadas.
Como se puede ver en la figura anterior, la capa subyacente de hashmap es una estructura de matriz, y cada elemento en la matriz es otra lista vinculada. Cuando se crea un nuevo hashmap, se inicializará una matriz.
El código fuente es el siguiente:
/ ** * La tabla, redimensionada según sea necesario. V valor;
Se puede ver que la entrada es el elemento en la matriz.
3. Implementación de acceso hashmap:
1) Almacenamiento:
public v put (k key, V value) {// hashmap permite claves nulas y valores nulos. // Cuando la clave sea nula, llame al método PutfornullKey y coloque el valor en la primera posición de la matriz. if (key == null) return putfornullkey (valor); int hash = hash (key.hashcode ()); int i = indexfor (hash, table.length); para (entrada <k, v> e = tabla [i]; e! = null; e = e.next) {objeto k; || key.equals (k)) {V OldValue = E.Value; que esta es que todavía no hay entrada. ModCount ++; Addentry (hash, clave, valor, i); En el código fuente anterior, podemos ver que cuando colocamos el elemento en HashMap, primero recalculamos el valor hash basado en el choque hash de la clave, y de acuerdo con el valor hash, la posición de este elemento en la matriz (es decir, subíndice. ), Si la matriz es, hay otros elementos ya almacenados en la posición, por lo que los elementos en esta posición se almacenarán en forma de una lista vinculada, los recién agregados se colocan en la cabeza de la cadena y los primeros agregados Los se colocan al final de la cadena. Si no hay elemento en esta posición en la matriz, coloque el elemento directamente en esta posición en la matriz.
El método Addentry (hash, clave, valor, i) coloca el par de valores clave en el índice I de la tabla de matriz en función del valor de hash calculado. Addentry es un método de permisos de acceso a paquetes proporcionados por HashMap, el código es el siguiente:
Void Addentry (int hash, k key, v value, int bucketIndex) {// Obtener la entrada en la entrada de índice BucketIndex especificada <k, v> e = table [bucketIndex]; índice y deje que el nuevo punto de entrada a la tabla de entrada original [bucketIndex] = nueva entrada <k, v> (hash, clave, valor, e); (tamaño ++> = umbral) // Expanda la longitud del objeto de tabla al doble del original. cambiar el tamaño (2 * table.length); Cuando el sistema decide almacenar el par de valor clave en el hashmap, el valor en la entrada no se considera en absoluto, y simplemente calcula y determina la ubicación de almacenamiento de cada entrada en función de la clave. Podemos tratar completamente el valor en la colección de mapas como un archivo adjunto a la clave.
El método hash (int h) recalcula el hash una vez basado en el choque de la clave. Este algoritmo agrega cálculos de alta bits para evitar conflictos hash causados cuando el bit bajo permanece sin cambios y cuando cambia el bits.
static int hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12); Podemos ver que para encontrar un elemento en hashmap, necesitamos encontrar la posición correspondiente en la matriz basada en el valor hash de la clave. Cómo calcular esta posición es el algoritmo hash. Como se mencionó anteriormente, la estructura de datos de HashMap es una combinación de matrices y listas vinculadas, por lo que, por supuesto, esperamos que las posiciones de los elementos en este hashmap se distribuyan uniformemente tanto como sea posible, de modo que el número de elementos en cada posición sea solo uno. Eficiencia de la consulta.
Para cualquier objeto dado, siempre que su valor de retorno hashcode () sea el mismo, el valor del código hash calculado por el programa que llama al método hash (int h) 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, la operación de "módulo" consume mucho, y esto se hace en hashmap: llame al método índice (int h, int longitud) para calcular qué índice se debe almacenar el objeto en la matriz de tabla.
El código del método indexFor (int h, int longitud) es el siguiente:
static int indexfor (int h, int longitud) {return h & (longitud-1);Este método es muy inteligente. Términos de velocidad. En el constructor hashmap, existe el siguiente código:
int capacidad = 1;
Este código asegura que la capacidad de HASHMAP siempre esté en la potencia n de 2 durante la inicialización, es decir, la longitud de la matriz subyacente siempre está en la potencia n de 2.
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 %.
Esto se ve muy simple, pero en realidad es bastante misterioso.
Suponiendo que las longitudes de la matriz son 15 y 16, y los códigos hash optimizados son 8 y 9, respectivamente, entonces el resultado después de la operación y es el siguiente:
H & (table.length-1) hash tabla.length-1
8 y (15-1): 0100 y 1110 = 0100
9 y (15-1): 0101 y 1110 = 0100
-------------------------------------------------- -------------------------------------------------- ---------------------------- ---------------------- -------------------------------------------------- -------------------------------------------------- ------ -------------------------------------------- -------------------------------------------------- -------------------------------------------------- -------------------------------------------------- -------------------------------------------------- ------------
8 y (16-1): 0100 y 1111 = 0100
9 y (16-1): 0101 y 1111 = 0101
Como se puede ver en el ejemplo anterior: cuando están "como" con 15-1 (1110), se produce el mismo resultado, es decir, se colocarán en la misma posición en la matriz, lo que crea una colisión, 8 y 9 se colocarán en la misma posición en la matriz para formar una lista vinculada. Al mismo tiempo, también podemos encontrar que cuando la longitud de la matriz es 15, el valor hash será "como" con 15-1 (1110), entonces el último bit siempre será 0 y 0001, 0011, 0101, 1001 , 1011, 0111, 0111, 1101 nunca puede almacenar elementos, y el espacio se desperdicia bastante. ¡La posibilidad de colisión aumenta aún más y la lenta eficiencia de consulta! Cuando la longitud de la matriz es 16, es decir, cuando está a la potencia n de 2, el valor en cada bit del número binario obtenido por 2n-1 es 1, lo que hace que la suma de la suma del hash original cuando Es y en el bit bajo, por lo que el bit bajo del hash de suma obtenido es el mismo, junto con el método hash (int h) optimiza aún más el código hash de la clave y agrega cálculos de alto bits, de modo que solo dos valores Del mismo valor hash se colocará en la misma posición en la matriz para formar una lista vinculada.
Por lo tanto, cuando la longitud de la matriz es n potencias de 2, la probabilidad de que diferentes claves puedan calcular el mismo índice es menor, por lo que los datos se distribuirán de manera uniforme en la matriz, lo que significa que la probabilidad de colisión es pequeña, relativa Esta vez, no tiene que atravesar la lista vinculada en una ubicación determinada, por lo que la eficiencia de consulta será mayor.
De acuerdo con el código fuente del método PUT anterior, cuando el programa intenta poner un par de valores clave en un hashmap, el programa determina primero la ubicación de almacenamiento de la entrada en función del valor de retorno hashcode () de la clave: si el Clave de dos entradas El valor de retorno hashcode () es el mismo, y su ubicación de almacenamiento es la misma. Si las claves de estas dos entradas devuelven verdaderas a través de la comparación igual, el valor de la entrada recientemente agregada anulará el valor de la entrada original en la colección, pero la clave no anulará. Si las claves de estas dos entradas devuelven falso a través de la comparación igual, la entrada recientemente agregada formará una cadena de entrada con la entrada original en la colección, y la entrada recientemente agregada se encuentra en el cabezal de la cadena de entrada, los detalles continúan viendo La descripción del método Addentry ().
2) Lea:
public v get (clave de objeto) {if (key == null) return getFornullKey (); . devolver E.Value; Con el algoritmo hash almacenado anteriormente como base, es fácil entender este código. En el código fuente anterior, podemos ver que al obtener un elemento en HashMap, primero calcule el Código hash de la clave, encuentre un elemento en la posición correspondiente en la matriz y luego encuentre el elemento requerido en la lista vinculada de la posición correspondiente a través del método igual de la clave.
3) Para resumir, hashmap procesa el valor clave en su conjunto en la parte inferior, y este todo es un objeto de entrada. El hashmap subyacente utiliza una matriz de entrada [] para almacenar todos los pares de valor clave. El método iguales.
4. RESEA DE HASHMAP (Rehash):
Como hay más y más elementos en el hashmap, la posibilidad de conflicto hash es cada vez mayor, porque la longitud de la matriz es fija. Por lo tanto, para mejorar la eficiencia de la consulta, la variedad de hashmap debe ampliarse. Aparece: los datos en la matriz original deben recalcularse y colocarse en la nueva matriz, que es cambiar el tamaño.
Entonces, ¿cuándo se expandirá Hashmap? Cuando el número de elementos en el hashmap excede el tamaño de la matriz *LoadFactor, la matriz se expande. Es decir, por defecto, el tamaño de la matriz es 16. Luego, cuando el número de elementos en hashmap excede 16*0.75 = 12, el tamaño de la matriz se expande a 2*16 = 32, es decir, duplicar el tamaño, y luego vuelva a calcularlo. .
5. Parámetros de rendimiento de hashmap:
Hashmap contiene los siguientes constructores:
Hashmap (): construya un hashmap con una capacidad inicial de 16 y un factor de carga de 0.75.
Hashmap (int InitialCapacity): construya un hashmap con capacidad inicial y un factor de carga de 0.75.
Hashmap (int InitialCapacity, Float LoadFactor): crea un hashmap con la capacidad inicial especificada y el factor de carga especificado.
El constructor básico de Hashmap, HashMap (int InitialCapacity, Float LoadFactor), tiene dos parámetros, son la capacidad inicial de capacidad inicial y el factor de carga de carga de carga.
Capacidad inicial: la capacidad máxima de hashmap, es decir, la longitud de la matriz subyacente.
LoadFactor: el factor de carga del factor de carga se define como: el número real de elementos de una tabla hash (n)/la capacidad de una tabla hash (m).
El factor de carga mide el grado de uso de un espacio de tabla hash. Para las tablas hash utilizando el método de lista vinculada, el tiempo promedio para encontrar un elemento es O (1+A), por lo tanto, si el factor de carga es más grande, el espacio se utiliza más completamente, pero la consecuencia es una disminución de la eficiencia de búsqueda; El factor de carga es también pequeño, entonces los datos de la tabla hash serán demasiado escasos, causando un gran desperdicio de espacio.
En la implementación de HASHMAP, la capacidad máxima de HASHMAP está determinada por el campo umbral:
La copia del código es la siguiente:
umbral = (int) (capacidad * loadFactor);
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 el factor de carga y la capacidad. El factor de carga predeterminado 0.75 es una opción equilibrada para la eficiencia espacial y temporal. Cuando la capacidad excede esta capacidad máxima, la capacidad del hashmap redimensionada es el doble de capacidad:
if (size ++> = umbral) cambiar el tamaño (2 * table.length);
6. Mecanismo de falla:
Sabemos que java.util.hashmap no es seguro de subprocesos, por lo que si otros hilos modifican el mapa durante el proceso de uso del iterador, se lanzará una medición de modificación concurrente, que es la llamada estrategia de fastidia.
Esta estrategia se implementa en el código fuente a través del campo ModCount. El MODCount de iterador.
HasShiterator () {esperadoModCount = ModCount; ; Durante el proceso de iteración, determine si el ModCount y el esperado MODCOUNT son iguales.
Tenga en cuenta que ModCount se declara como volátil, lo que garantiza la visibilidad de las modificaciones entre los hilos.
Entrada final <k, v> nextEntry () {if (modCount! = ExpectedModCount) Lanzar nueva concurrenteModificationException (); En la API de Hashmap, se dice:
Los iteradores devueltos por el "método de vista de colección" de todas las clases de hashmap fallan rápidamente: después de que se crea el iterador, si el mapeo se modifica a partir de la estructura, a menos que se pase a través del método de eliminación del iterador, de cualquier otra manera. Lanza una Modificación Concurrente Excepción si se realiza la modificación. Por lo tanto, ante las modificaciones concurrentes, el iterador pronto fallará completamente sin arriesgar un comportamiento incierto arbitrario en los tiempos inciertos en el futuro.
Tenga en cuenta que el comportamiento de falla rápido del iterador no puede garantizarse. El iterador de fallas rápidas lanza una concurrencia concurrente. Por lo tanto, es incorrecto escribir programas que dependan de esta excepción, y la forma correcta es: el comportamiento rápido de falla del iterador debe usarse solo para detectar errores del programa.