Estructura de almacenamiento
Primero, hashmap se almacena en base a una tabla hash. Hay una matriz dentro de él. Cuando se debe almacenar un elemento, primero calcule el valor hash de su clave y encuentre el subíndice correspondiente del elemento en la matriz en función del valor hash. Si no hay ningún elemento en esta posición, coloque el elemento actual directamente. Si hay un elemento (recordado como un aquí), vincule el elemento actual al frente del elemento A y luego coloque el elemento actual en la matriz. Entonces, en HashMap, la matriz realmente guarda el primer nodo de la lista vinculada. A continuación se muestra una imagen de la enciclopedia de Baidu:
Como se muestra en la figura anterior, cada elemento es un objeto de entrada, donde se guardan la clave y el valor del elemento, y hay un puntero que puede usarse para apuntar al siguiente objeto. Todas las claves con el mismo valor hash (es decir, conflicto) las unen usando una lista vinculada, que es el método de cremallera.
Variables internas
// Capacidad inicial predeterminada estática final int default_initial_capacity = 16; // Capacidad máxima estática final int maximum_capacity = 1 << 30; // factor de carga predeterminado Float final estático Default_load_factor = 0.75f; // HAST TABLA Entrada transitoria <k, v> [] Tabla; // Número de la tecla Value Los pares de parejas transmisores intane; // el rayo de expansión de la expansión de la expansión; HASH Matriz Final Float LoadFactor;
En las variables anteriores, la capacidad se refiere a la longitud de la tabla hash, es decir, el tamaño de la tabla, y el valor predeterminado es 16. El factor de carga de carga es el "grado completo" de la tabla hash, y la documentación del JDK dice esto:
El factor de carga es una medida de cuán llena se permite que la tabla hash se obtenga antes de que su capacidad aumente automáticamente. Cuando el número de entradas en la tabla hash excede el producto del factor de carga y la capacidad actual, la tabla hash se vuelve a decir (es decir, las estructuras de datos internos se reconstruyen) para que la tabla hash tenga aproximadamente el doble del número de cubos.
El significado general es: el factor de carga es la medida de cuán llena se puede instalar la tabla hash antes de la expansión. Cuando el número de "pares de valor clave" en la tabla hash excede el producto de la capacidad actual y el factor de carga, la tabla hash ha (es decir, la estructura de datos internos se reconstruye), y la capacidad de la tabla hash se vuelve aproximadamente el doble del original.
Como se puede ver en la definición de variable anterior, el factor de carga predeterminado default_load_factor es 0.75. Cuanto mayor sea este valor, mayor será la tasa de utilización del espacio, pero la velocidad de consulta (incluida la obtención y la puesta) se reducirá. Después de comprender el factor de carga, el umbral también puede entenderlo. En realidad es igual a la capacidad* factor de carga.
Constructor
public HASHMAP (int InitialCapacity, Float LoadFactor) {if (InitialCapacity <0) Throw New IlegalArGumentException ("Capacidad inicial ilegal:" + InicialCapacity); if (inicialCapacity> maximum_capacity) inicialCapacity = maximum_capacity; if (loadFactor <= 0 || float.isnan (LoadFactor)) tire nueva ilegalargumentException ("Factor de carga ilegal:" + LoadFactor); // Encuentra una potencia de 2> = InitialCapacity int capacidad = 1; mientras que (capacidad <inicialcapacity) // calcule la potencia más pequeña de 2 que es mayor que la capacidad de capacidad especificada << = 1; this.loadFactor = LoadFactor; umbral = (int) math.min (capacidad * loadFactor, maximum_capacity + 1); tabla = nueva entrada [capacidad]; // Asignar espacio a la tabla hash USEALTHING = sun.misc.vm.isbooted () && (capacidad> = holder.alternative_hashing_threshold); init ();}Hay varios constructores, y eventualmente llamarán a lo anterior. Acepta dos parámetros, uno es la capacidad inicial y la otra es el factor de carga. Al principio, primero determinamos si la combinación de valor es legal, y si hay algún problema, se lanzará una excepción. Lo importante es el cálculo de la siguiente capacidad, su lógica es calcular la potencia más pequeña de 2 mayor que la capacidad inicial. De hecho, el propósito es hacer que la capacidad sea más o igual a la capacidad inicial especificada, pero este valor debe ser un múltiplo exponencial de 2, que es un tema clave. La razón de esto es principalmente para mapear los valores hash. Veamos primero el método hash en hashmap:
final int hash (objeto k) {int h = 0; if (USEALTHASHING) {if (k instanceOf string) {return sun.misc.hashing.stringhash32 (((string) k); } h = hashseed; } h ^= k.hashcode (); // Esta función garantiza que los hashcodes tan diferentes solo por // múltiplos constantes en cada posición de bit tengan un número // número de colisiones (aproximadamente 8 en el factor de carga predeterminado). h ^ = (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);} static int indexFor (int h, int longitud) {return h & (longitud-1);}El método hash () recalcula el valor hash de la clave y utiliza operaciones de bits relativamente complejas. No conozco la lógica específica. De todos modos, definitivamente es un método mejor, que puede reducir los conflictos o algo así.
El indexFor () a continuación es el subíndice del elemento en la tabla hash basado en el valor hash. En general, en una tabla hash, usa valores hash para modular la longitud de la tabla. Cuando la longitud (es decir, la capacidad) es una potencia de 2, H & (longitud-1) es el mismo efecto. Además, la potencia de 2 debe ser un número uniforme, luego, después de restar 1, es un número impar, y el último bit del binario debe ser 1. Entonces el último bit de H & (Longitud-1) puede ser 1 o 0, que se puede hacer uniformemente. Si la longitud es un número impar, entonces la longitud-1 es un número uniforme y el último bit es 0. En este momento, el último bit de H & (Longitud-1) solo puede ser 0, y todos los subíndices resultantes son pares, por lo que la mitad del espacio se desperdicia. Por lo tanto, la capacidad en HashMap debe ser un poder de 2. Puede ver que el predeterminado predeterminado_initial_capacity = 16 y Maximum_Capacity = 1 << 30 son así.
Objeto de entrada
Los pares de valor clave en HASHMAP están encapsulados en objetos de entrada, que es una clase interna en HashMap. Echemos un vistazo a su implementación:
Entrada de clase estática <k, v> implementa map.entry <k, v> {fin final k clave; V valor; Entrada <k, v> siguiente; int hash; Entrada (int h, k k, v v, entrada <k, v> n) {value = v; siguiente = n; clave = k; hash = h; } public final K getKey () {return Key; } public Final V getValue () {Valor de retorno; } public Final V setValue (v NewValue) {v OldValue = valor; valor = newValue; devolver OldValue; } público final booleano iguales (objeto o) {if (! (o instanciaf map.entry) devuelve falso; Map.Entry e = (map.entry) o; Objeto k1 = getKey (); Objeto k2 = e.getKey (); if (k1 == k2 || (k1! = null && k1.equals (k2)))) {objeto v1 = getValue (); Objeto v2 = e.getValue (); if (v1 == v2 || (v1! = null && v1.equals (v2))) return true; } return false; } public final int hashcode () {return (key == null? 0: key.hashcode ()) ^ (valor == null? 0: value.hashcode ()); } public Final String ToString () {return getKey () + "=" + getValue (); } Void RecordAccess (hashmap <k, v> m) {}}La implementación de esta clase es simple y fácil de entender. Se proporcionan métodos como GetKey (), GetValue () para llamar. Para determinar la igualdad, es necesario que tanto la clave como el valor sean iguales.
Poner operación
Pon primero antes de obtenerlo, así que mira primero el método PUT ():
public v put (k key, v value) {if (key == null) return putfornullkey (valor); int hash = hash (clave); int i = indexfor (hash, table.length); para (entrada <k, v> e = table [i]; e! = null; e = e.next) {objeto k; if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v OldValue = e.Value; e.value = valor; E.RecordAccess (esto); devolver OldValue; }} modcount ++; Addentry (hash, clave, valor, i); devolver nulo;}En este método, primero determine si la clave es nula. En caso afirmativo, llame al método PutfornLeyKey (), lo que significa que HASHMAP permite que la clave sea nula (de hecho, el valor puede ser). Si no es nulo, calcule el valor hash y obtenga el subíndice en la tabla. Luego vaya a la lista vinculada correspondiente para consultar si ya existe la misma clave. Si ya existe, el valor se actualizará directamente. De lo contrario, llame al método Addentry () para su inserción.
Eche un vistazo al método PutfornullKey ():
privado v putfornullkey (valor v) {para (entrada <k, v> e = table [0]; e! = null; e = e.next) {if (e.key == null) {v oldValue = e.value; e.value = valor; E.RecordAccess (esto); devolver OldValue; }} modcount ++; Addentry (0, nulo, valor, 0); devolver nulo;}Se puede ver que cuando la clave sea nula, el valor se actualizará si existe, de lo contrario Addentry () será llamado a insertar.
La siguiente es la implementación del método Addentry ():
Void Addentry (int hash, k key, v value, int bucketIndex) {if ((size> = umbral) && (null! = table [bucketIndex])) {resize (2 * table.length); hash = (nulo! = clave)? hash (clave): 0; bucketIndex = indexfor (hash, table.length); } createEntry (hash, clave, valor, bucketIndex);} void createEntry (int hash, k key, v value, int bucketIndex) {Entry <k, v> e = table [bucketIndex]; tabla [bucketIndex] = nueva entrada <> (hash, clave, valor, e); tamaño ++;}Primero, determine si expandir la capacidad (la capacidad de expansión recalculará el valor del subíndice y copiará el elemento), luego calcule el subíndice de la matriz y finalmente inserte el elemento utilizando el método de inserción del encabezado en CreateEntry ().
Obtener operación
public v get (clave de objeto) {if (key == null) return getFornullKey (); Entrada <k, v> entry = getEntry (clave); return null == entrada? null: entry.getValue ();} private v getFornullKey () {para (entrada <k, v> e = table [0]; e! = null; e = e.next) {if (e.key == null) return e.value; } return null;} Entrada final <k, v> getEntry (clave de objeto) {int hash = (key == null)? 0: hash (clave); para (entrada <k, v> e = table [indexfor (hash, table.length)]; e! = null; e = e.next) {objeto k; if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) return e; } return null;}Esto es más simple que PUT (). También debe determinar si la clave es nula, y luego la consulta transversal de la lista vinculada.
Optimización del rendimiento
Hashmap es una estructura de datos eficiente y universal que se puede ver en todas partes en cada programa de Java. Presentemos primero algunos conocimientos básicos. Como también sabrá, HashMap usa los métodos hashcode () e igual () de clave para dividir los valores en diferentes cubos. El número de cubos suele ser ligeramente mayor que el número de registros en el mapa, de modo que cada cubo incluirá menos valores (preferiblemente uno). Al buscar en las teclas, podemos localizar rápidamente un cubo (usando hashcode () para modular el número de cubos) y el objeto que buscamos en tiempo constante.
Ya deberías saber todas estas cosas. También puede saber que las colisiones hash pueden tener un impacto catastrófico en el rendimiento de Hashmap. Si los valores múltiples hashcode () caen en el mismo cubo, estos valores se almacenan en una lista vinculada. En el peor de los casos, todas las claves se asignan en el mismo cubo, por lo que el hashmap degenere en una lista vinculada: el tiempo de búsqueda es de O (1) a O (n). Primero probemos el rendimiento de Hashmap en Java 7 y Java 8 en circunstancias normales. Para controlar el comportamiento del método hashcode (), definimos una clase clave de la siguiente manera:
La clave de clase implementa comparable <Key> {private final int value; key (int value) {this.value = value;}@overRidePublic int CompareTo (Key o) {return integer.comPare (this.value, o.value);}@overridePublicean iguales (objeto o) {if (this == O) return verdadero; if (o = = = == null || o.getClass ()) return false; key clave = (clave) o; valor de retorno == key.Value;}@overridePublic int hashcode () {value de retorno;}}La implementación de la clase clave es bastante estándar: reescribe el método igual () y proporciona un método hashcode () bastante decente. Para evitar GC excesivo, almacené en caché el objeto clave inmutable en lugar de comenzar a crearlo nuevamente cada vez:
La clave de clase implementa comparable <Key> {public class Keys {public static final int max_key = 10_000_000; Key final estática privada [] keys_cache = new key [max_key]; static {for (int i = 0; i <max_key; ++ i) {keys_cache [i] = new key (i);}}}}}}}} static de (intento int) {retorts) Keys_cache [valor];}Ahora podemos comenzar a probar. Nuestro punto de referencia utiliza valores clave continuos para crear hashmaps de diferentes tamaños (multiplicador para 10, de 1 a 1 millón). En la prueba, también usaremos claves para buscar y medir el tiempo que lleva los hashmaps de diferentes tamaños:
import com.google.caliper.param; import com.google.caliper.runner; import com.google.caliper.simplebenchmark; public class MapBenchmark extiende SimpleBenchmark {private Hashmap <Key, Integer> Map; @paramprivate intence; Hashmap <> (mapsize); for (int i = 0; i <mapsize; ++ i) {map.put (keys.of (i), i);}} public void void timEmapget (int reps) {para (int i = 0; i <reps; i ++) {map.get (keys.of (i % mapsize));}}}}}}}}}}}Curiosamente, en este simple hashmap.get (), Java 8 es un 20% más rápido que Java 7. El rendimiento general también es bastante bueno: aunque hay un millón de registros en Hashmap, una sola consulta solo tomó menos de 10 nanosegundos, que son aproximadamente 20 ciclos de CPU en mi máquina. ¡Muy impactante! Pero esto no es lo que queremos medir.
Supongamos que hay una clave mala, siempre devuelve el mismo valor. Este es el peor escenario, y no debes usar hashmap en absoluto:
La clave de clase implementa comparable <Key> {//...@overridepublic int hashcode () {return 0;}}Se esperan los resultados de Java 7. A medida que crece el tamaño del hashmap, la sobrecarga del método get () se está haciendo cada vez más grande. Dado que todos los registros están en la lista vinculada de Ultra Long en el mismo cubo, buscar un promedio de un registro requiere atravesar la mitad de la lista. Por lo tanto, se puede ver en la figura que su complejidad de tiempo es O (n).
Sin embargo, ¡Java 8 funciona mucho mejor! Es una curva de registro, por lo que su rendimiento es mejor de magnitud. A pesar del peor de los casos de colisiones de hash severas, este mismo punto de referencia tiene una complejidad de tiempo en JDK8 de O (LOGN). Si miras solo la curva de JDK 8, será más claro. Esta es una distribución lineal logarítmica:
¿Por qué hay una mejora de rendimiento tan grande, a pesar de que el símbolo Big O se usa aquí (Big O describe el límite superior asintótico)? De hecho, esta optimización se ha mencionado en JEP-180. Si el registro en un cubo es demasiado grande (actualmente TreifiFe_threshold = 8), HashMap lo reemplazará dinámicamente con una implementación especial de Treemap. Esto dará como resultado mejores resultados, o (logn), no mal o (n). ¿Cómo funciona? Los registros correspondientes a la clave que tienen conflictos al frente simplemente se agregan a una lista vinculada, y estos registros solo se pueden encontrar a través de Traversal. Sin embargo, después de exceder este umbral, Hashmap comienza a actualizar la lista a un árbol binario, utilizando el valor hash como la variable de rama del árbol. Si los dos valores hash no son iguales pero apuntan al mismo cubo, el más grande se insertará en el subárbol derecho. Si los valores hash son iguales, HashMap espera que el valor clave sea implementado mejor por la interfaz comparable para que pueda insertarse en orden. Esto no es necesario para la clave de Hashmap, pero, por supuesto, es la mejor si se implementa. Si esta interfaz no se implementa, no debe esperar lograr mejoras de rendimiento en caso de colisiones de hash graves.
¿Cuál es el uso de esta mejora del rendimiento? Por ejemplo, un programa malicioso, si sabe que estamos utilizando un algoritmo de hash, puede enviar una gran cantidad de solicitudes, lo que resulta en colisiones de hash graves. Luego, acceder constantemente a estas claves puede afectar significativamente el rendimiento del servidor, lo que conduce a un ataque de denegación de servicio (DOS). El salto de O (N) a O (LOGN) en JDK 8 puede evitar efectivamente ataques similares, al tiempo que mejora ligeramente la previsibilidad del rendimiento de hashmap. Espero que esta mejora eventualmente convencerá a su jefe de que acepte actualizar a JDK 8.
El entorno utilizado para la prueba es: Intel Core i7-3635QM @ 2.4 GHz, memoria 8GB, disco duro SSD, utilizando parámetros JVM predeterminados, que se ejecutan en un sistema Windows 8.1 de 64 bits.
Resumir
La implementación básica de HASHMAP se analiza anteriormente, y finalmente se realiza el resumen: