Hashmap también es una colección que usamos mucho. Es una implementación de la interfaz MAP basada en tablas hash y existe en forma de valor clave. En HashMap, el valor clave siempre se procesa en su conjunto. El sistema calculará la ubicación de almacenamiento del valor clave en función del algoritmo hash. Siempre podemos almacenar rápidamente y recuperar el valor a través de la clave. Analicemos el acceso a HashMap.
1. Definición
Hashmap implementa la interfaz de mapa y hereda el mapas abstractas. La interfaz MAP define las reglas para la asignación clave a los valores, y la clase AbstractMap proporciona la implementación de la red troncal de la interfaz MAP para minimizar el trabajo requerido para implementar esta interfaz. De hecho, la clase AbstractMap ha implementado el mapa. ¡Creo que debería ser más claro marcar map lz aquí!
clase pública Hashmap <K, V> extiende AbstractMap <K, V> Implementa el mapa <k, v>, clonable, serializable
2. Función del constructor
Hashmap proporciona tres constructores:
Hashmap (): construye un hashmap vacío con la capacidad inicial predeterminada (16) y el factor de carga predeterminado (0.75).
Hashmap (int InitialCapacity): construye un hashmap vacío con capacidad inicial especificada y factor de carga predeterminado (0.75).
Hashmap (int InitialCapacity, Float LoadFactor): construye un hashmap vacío con capacidad inicial y factor de carga especificados.
Aquí se mencionan dos parámetros: capacidad inicial, factor de carga. Estos dos parámetros son parámetros importantes que afectan el rendimiento de HASHMAP. La capacidad representa el número de cubos en la tabla hash. La capacidad inicial es la capacidad al crear una tabla hash. El factor de carga es una escala que la tabla hash puede alcanzar antes de que su capacidad aumente automáticamente. Mide el grado de uso de un espacio de tabla hash. Cuanto mayor sea el factor de carga indica que cuanto mayor sea el grado de carga de la tabla hash, y viceversa. 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 mayor, el espacio se utilizará más completamente, pero la consecuencia es una disminución en la eficiencia de búsqueda; Si el factor de carga es demasiado pequeño, los datos de la tabla hash serán demasiado escasos, lo que causará desechos graves en el espacio. El factor de carga predeterminado del sistema es 0.75, y generalmente no necesitamos modificarlo.
HashMap es una estructura de datos que admite acceso rápido. Para comprender su rendimiento, debe comprender su estructura de datos.
Iii. Estructura de datos
Sabemos que las dos estructuras más utilizadas en Java son matrices y punteros simulados (referencias). Casi todas las estructuras de datos se pueden implementar en combinación con estos dos, y lo mismo es cierto para HASHMAP. De hecho, hashmap es un "hash de la lista vinculada", como sigue su estructura de datos:
De la figura anterior, podemos ver si la implementación subyacente de hashmap es o una matriz, pero cada elemento de la matriz es una cadena. La capacidad inicial del parámetro representa la longitud de la matriz. El siguiente es el código fuente del constructor hashmap:
Public HashMap (int InitialCapacity, Float LoadFactor) {// La capacidad inicial no puede ser <0 if (InitialCapacity <0) Throw New IlegalArGumentException ("Capacidad inicial ilegal:" + InicialCapacity); // La capacidad inicial no puede> valor máximo de capacidad, la capacidad máxima de hashmap es 2^30 if (inicialcapacity> maximum_capacity) inicialcapacity = maximum_capacity; // El factor de carga no puede ser <0 if (loadFactor <= 0 || float.isnan (loadFactor)) tirar nueva ilegalArgumentException ("Factor de carga ilegal:" + LoadFactor); // Calcule el valor de potencia N de los 2 más pequeños mayores que la capacidad inicial. int capacidad = 1; while (capacidad <inicialcapacity) capacidad << = 1; this.loadFactor = LoadFactor; // Establecer el límite de capacidad de HASHMAP. Cuando la capacidad de HASHMAP alcanza este límite, la operación de expansión de capacidad se realizará umbral = (int) (capacidad * LoadFactor); // Inicializar la tabla de matriz de tabla = nueva entrada [capacidad]; init (); } Como se puede ver en el código fuente, se inicializará una matriz de tabla cada vez que se cree un nuevo hashmap. El elemento de la matriz de tabla es un nodo de entrada.
Entrada de clase estática <k, v> implementa map.entry <k, v> {fin final k clave; V valor; Entrada <k, v> siguiente; final int hash; /*** Crea una nueva entrada. */ Entrada (int h, k k, v v, entrada <k, v> n) {valor = v; siguiente = n; clave = k; hash = h; } .....}Entre ellos, la entrada es la clase interna de hashmap, que contiene la clave, el valor de valor, el siguiente nodo siguiente y el valor hash. Esto es muy importante. Se debe precisamente a que la entrada forma los elementos de la matriz de tabla como una lista vinculada.
Lo anterior analiza brevemente la estructura de datos de HASHMAP, y a continuación explorará cómo HASHMAP implementa un acceso rápido.
4. Implementación de almacenamiento: PUT (Key, VLaue)
Primero, veamos el código fuente
public v put (k key, valor v) {// Cuando la clave es nula, llame al método PutfornullKey para guardar la primera posición de NULL y TABLE. Esta es la razón por la cual HashMap permite que NULL if (Key == NULL) return PutfornullKey (valor); // Calcule el valor hash de la clave int hash = hash (key.hashcode ()); ----- (1) // Calcule la posición del valor de hash clave en la matriz de tabla int i = indexfor (hash, table.length); ----- (2) // iterar desde i y encontrar la ubicación donde se guarda la clave para (entrada <k, v> e = table [i]; e! = Null; e = e.next) {objeto k; // juzga si hay el mismo valor hash en la cadena (la clave es la misma) // Si existe lo mismo, sobrescribe directamente el valor y devuelve el valor anterior if (e.hash == hash && ((k = e.key) == clave || key.equals (k))) {v oldValue = e.value; // valor antiguo = nuevo valor e.value = valor; E.RecordAccess (esto); devolver OldValue; // devuelve el valor anterior}} // Aumentar el número de modificaciones por 1 ModCount ++; // Agregar clave y valor a la posición I Addentry (hash, clave, valor, i); regresar nulo; }A través del código fuente, podemos ver claramente que el proceso de los datos de ahorro de hashmap es: primero determinar si la clave es nula. Si es nulo, llame directamente al método PutfornullKey. Si no está vacío, primero calcule el valor hash de la clave y luego busque la posición de índice en la matriz de tabla de acuerdo con el valor hash. Si hay un elemento en esta posición, compare si existe la misma clave. Si existe, sobrescribe el valor de la clave original, de lo contrario, guarde el elemento en la cabeza de la cadena (el primer elemento guardado se coloca al final de la cadena). Si la tabla no tiene elementos allí, se guardará directamente. Este proceso parece simple, pero en realidad tiene información privada profunda. Hay varios puntos de la siguiente manera:
1. Veamos primero la iteración. La razón para la iteración aquí es evitar la existencia del mismo valor clave. Si se encuentra que dos valores hash (claves) son los mismos, el método de procesamiento de HASHMAP es reemplazar el valor anterior con el nuevo valor. La clave no se procesa aquí, lo que explica que no hay dos claves idénticas en el hashmap.
2. En la vista (1) y (2). Esta es la esencia del hashmap. En primer lugar, está el método hash, que es un cálculo matemático puro, que es calcular el valor hash de h.
static int hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12); devolver h ^ (h >>> 7) ^ (h >>> 4); }Sabemos que para las tablas de hashmap, la distribución de datos debe ser uniforme (es mejor tener solo un elemento para cada elemento, para que se pueda encontrar directamente). No puede ser demasiado apretado o demasiado suelto. Demasiado apretado conducirá a una velocidad de consulta lenta, y demasiado flojo desperdiciará espacio. Después de calcular el valor hash, ¿cómo podemos asegurar que los elementos de la tabla se distribuyan por igual? Pensaremos en la adquisición de moho, pero debido a que la adquisición de moho consume mucho, hashmap lo maneja así: llame al método índice para.
static int indexFor (int h, int longitud) {return h & (longitud-1); }La longitud de la matriz subyacente de hashmap siempre está en la potencia n de 2, y existe en el constructor: capacidad << = 1; Hacerlo siempre puede garantizar que la longitud de la matriz subyacente de hashmap esté en la potencia n de 2. Cuando la longitud es a n potencia de 2, h & (longitud - 1) es equivalente a tomar el módulo de longitud, y la velocidad es mucho más rápida que tomar el módulo directamente. Esta es una optimización de hashmap en términos de velocidad. En cuanto a por qué es 2 para el enésimo poder, la siguiente explicación es.
Volvamos al método IndexFor, que solo tiene una declaración: H & (Longitud - 1). Además de la operación del módulo anterior, esta oración también tiene una responsabilidad muy importante: distribuir uniformemente los datos de la tabla y hacer un uso completo del espacio.
Aquí suponemos que la longitud es 16 (2^n) y 15, y H es 5, 6 y 7.
Cuando n = 15, los resultados de 6 y 7 son los mismos, lo que significa que sus ubicaciones almacenadas en la tabla son los mismos, es decir, se produce una colisión, y 6 y 7 formarán una lista vinculada en una ubicación, lo que conducirá a una disminución en la velocidad de la consulta. Es cierto que solo se analizan tres números aquí, pero no muchos, así que veamos 0-15.
Desde el cuadro anterior, vemos un total de 8 colisiones, y al mismo tiempo, encontramos que el espacio desperdiciado es muy grande, sin registros en 1, 3, 5, 7, 9, 11, 13 y 15 lugares, es decir, no se almacenan datos. Esto se debe a que cuando funcionan y funcionan con 14, el último bit del resultado que obtienen siempre será 0, es decir, es imposible almacenar datos en las ubicaciones de 0001, 0011, 0101, 0111, 1001, 1011, 1101, 1111 y 1111. La espacio se reduce y la posibilidad de colisión aumentará aún más, lo que provocará una velocidad de consulta lenta. Cuando la longitud = 16, la longitud 1 = 15 es 1111. Luego, al realizar el bit y la operación bajo, el valor siempre es el mismo que el valor hash original, y al realizar la operación de alto bit, su valor es igual a su valor de bajo bits. Por lo tanto, cuando la longitud = 2^n, la probabilidad de colisión entre los diferentes valores de hash es relativamente pequeña, lo que hará que los datos se distribuyan uniformemente en la matriz de la tabla y la velocidad de consulta sea más rápida.
Aquí revisamos el proceso PUT: cuando queremos agregar un par de valores clave a un hashmap, el sistema calculará primero el valor hash de la clave y luego confirmará la ubicación almacenada en la tabla en función del valor hash. Si no hay elemento en esta posición, inserte directamente. De lo contrario, ite sobre la lista de elementos en ese punto y compare el valor hash de su clave en consecuencia. Si los dos valores hash son iguales y los valores clave son iguales (E.Hash == Hash && ((k = E.Key) == Key || Key.Equals (k))), el valor del nodo original se sobrescribe con el valor de la nueva entrada. Si los dos valores hash son iguales pero los valores clave no son iguales, inserte el nodo en el encabezado de la lista vinculada. Para el proceso de implementación específico, consulte el método Addentry, como sigue:
Void Addentry (int hash, k key, v valor, int bucketIndex) {// Obtener la entrada de entrada <k, v> e = table [bucketIndex]; // Ponga la entrada recién creada en el índice de bucketIndex y deje que el nuevo punto de entrada a la tabla de entrada original [bucketIndex] = nueva entrada <k, v> (hash, clave, valor, e); // Si el número de elementos en el hashmap excede el límite, la capacidad será dos veces más grande if (size ++> = umbral) cambiar el tamaño (2 * table.length); }Hay dos puntos a tener en cuenta en este método:
Uno es la generación de cadenas. Este es un diseño muy elegante. El sistema siempre agrega un nuevo objeto de entrada al bucketIndex. Si hay un objeto en BucketIndex, el objeto de entrada recientemente agregado apuntará al objeto de entrada original, formando una cadena de entrada. Sin embargo, si no hay objeto de entrada en BucketIndex, es decir, E == NULL, entonces el objeto de entrada recientemente agregado apunta a NULL, y no habrá una cadena de entrada generada.
2. Expansión de capacidad.
A medida que aumenta el número de elementos en HASHMAP, la probabilidad de colisión se vuelve cada vez mayor, y la longitud de la lista de enlaces generadas se volverá cada vez más larga. Esto inevitablemente afectará la velocidad del hashmap. Para garantizar la eficiencia de HASHMAP, el sistema debe expandir la capacidad en un cierto punto crítico. Este punto crítico es cuando el número de elementos en el hashmap es igual al factor de carga de longitud de la matriz de tabla*. Pero la escala es un proceso que consume mucho tiempo porque requiere recalcular la ubicación de estos datos en la nueva matriz de tabla y copiarlo. Entonces, si hemos predicho el número de elementos en HASHMAP, entonces el número de elementos preestablecidos puede mejorar efectivamente el rendimiento de HASHMAP.
5. Implementación de lectura: Get (clave)
En comparación con el almacenamiento de hashmap, la retirada es relativamente simple. Encuentre la entrada en el índice en la matriz de tabla a través del valor hash de la clave y luego devuelva el valor correspondiente a la clave.
public v get (clave de objeto) {// if null, llame al método getfornullkey para devolver el valor correspondiente if (key == null) return getFornullKey (); // Calcule su código hash basado en el valor hashcode de la clave int hash = hash (key.hashcode ()); // Saque el valor en el índice especificado en la matriz de tabla para (entrada <k, v> e = table [indexfor (hash, table.length)]; e! = Null; e = e.next) {objeto k; // Si la clave registrada es la misma que la clave buscada, devuelva el valor correspondiente if (e.hash == hash && ((k = e.key) == clave || key.equals (k))) return e.value; } return null; } Aquí, el valor que se puede recuperar rápidamente en función de la clave no solo es inseparable de la estructura de datos de HashMap, sino que también tiene mucho que ver con la entrada. Como se mencionó anteriormente, HashMap no almacena la clave y el valor por separado en el procedimiento almacenado, pero se procesa como un valor clave completo, que es el objeto de entrada. Al mismo tiempo, el valor solo es equivalente al archivo adjunto de la clave. Durante el proceso de almacenamiento, el sistema determina la ubicación de almacenamiento de la entrada en la matriz de tabla basada en el código hash de la clave, y en el proceso de recuperación, el objeto de entrada correspondiente también se saca de acuerdo con el Código hash de la clave.
Enlace original: http://www.cnblogs.com/chenssy/p/3521565.html
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.