Hashmap y Hashset son dos miembros importantes del marco de colección Java. Hashmap es una clase de implementación común para la interfaz de mapa, y HashSet es una clase de implementación común para la interfaz SET. Aunque las especificaciones de la interfaz implementadas por HashMap y Hashset son diferentes, su mecanismo de almacenamiento de hash subyacente es exactamente las mismas, e incluso hashset en sí utiliza HashMap para implementarlo.
De hecho, hay muchas similitudes entre hashset y hashmap. Para hashset, el sistema utiliza el algoritmo hash para determinar la ubicación de almacenamiento de los elementos de recolección, a fin de garantizar que los elementos de recolección se puedan almacenar y recuperar rápidamente; Para HASHMAP, el valor clave del sistema se procesa en su conjunto, y el sistema siempre calcula la ubicación de almacenamiento del valor clave en función del algoritmo hash, de modo que los pares de valor clave del mapa se pueden almacenar y recuperar rápidamente.
Antes de introducir el almacenamiento de la colección, debe señalarse que, aunque una colección afirma almacenar objetos Java, en realidad no pone objetos Java en la colección de conjuntos, sino que solo conserva referencias a estos objetos en la colección establecida. Es decir, una colección Java es en realidad una colección de múltiples variables de referencia que apuntan al objeto Java real.
1. Características básicas de hashmap
Después de leer los comentarios en el código fuente JDK hashmap.class, puede resumir muchas características de hashmap.
Hashmap permite que tanto la clave como el valor sean nulos, mientras que Hashtable no lo hace.
Hashmap es inhalación de hilos, mientras que la hashtable es segura de hilo
El orden de los elementos en hashmap no siempre es el mismo, y la posición del mismo elemento también puede cambiar con el tiempo (el caso de cambio de tamaño)
La complejidad del tiempo de atravesar un hashmap es proporcional a su capacidad y al número de elementos existentes. Si desea asegurarse de la eficiencia del recorrido, la capacidad inicial no se puede establecer demasiado o el factor de equilibrio no se puede establecer demasiado bajo.
Similar a la lista relacionada anterior, dado que hashmap es la inicio de hilo, se generará Fail-Fast cuando el iterador intente cambiar la estructura del contenedor durante el proceso de iteración. Se puede obtener un hashmap sincronizado a través de la colección. SynchronizedMap (Hashmap)
2. Análisis de la estructura de datos de la tabla hash
La tabla hash (tabla hash, tabla hash) es una estructura de datos que accede directamente a las ubicaciones de almacenamiento de memoria basadas en palabras clave. Es decir, la tabla hash establece una asignación directa entre palabras clave y direcciones de almacenamiento
Como se muestra en la figura a continuación, la clave obtiene una posición de índice de cubos a través de la función hash.
La obtención del índice a través de la función hash inevitablemente ocurrirá en la misma situación, es decir, conflicto. Aquí hay algunas formas de resolver conflictos:
Dirección abierta: la idea básica de este método es escanear las posiciones N debajo de la tabla en secuencia al encontrar conflictos y completar si hay alguna gratuita. El algoritmo específico ya no se explicará, el siguiente es un diagrama esquemático:
Caminaje separado: la idea básica de este método es unir la entrada con el mismo valor de índice en una lista vinculada al encontrar conflictos. El algoritmo específico ya no se explicará, el siguiente es un diagrama esquemático:
El método para resolver conflictos en HASHMAP en JDK es utilizar el método de encadenamiento separado.
3. Análisis del código fuente de Hashmap (JDK1.7)
1. Hashmap Leer y escribir elementos
Entrada
Los elementos almacenados en Hashmap son de tipo de entrada. El código fuente de entrada en el código fuente se proporciona a continuació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; } // Los métodos de clave Get and Set de clave se omiten, las operaciones GET y SET se utilizarán en los iteradores posteriores ... Public Final Boolean iguales (Object o) {if (! (O instanciaf map.entry) return false; 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; } // Aquí, realice u opere el húsico de clave y el valor hashcode de valor para obtener el hashcode de entrada pública pública final int hashcode () {return Objects.hashCode (getKey ()) ^ Objects.hashCode (getValue ()); } public Final String ToString () {return getKey () + "=" + getValue (); } /** * Este método se invoca cada vez que el valor en una entrada está * sobrescribido por una invocación de put (k, v) para una clave k que ya está * en el hashmap. * / void RecordAccess (hashmap <k, v> m) {} / ** * Este método se invoca cada vez que la entrada se elimina * de la tabla. */ void récordremoval (hashmap <k, v> m) {}}Una entrada incluye clave, valor, hash y una referencia a la siguiente entrada. Es obvio que esta es una única lista vinculada, que implementa la interfaz MAP.Entry.
RecordAcess (Hashmap <K, V> y Recordremoval (Hashmap <K, V>) no se implementan en HashMap. Sin embargo, los dos métodos de LinkedHashMap se utilizan para implementar el algoritmo LRU.
Obtenga: Leer elementos para obtener la entrada correspondiente de HashMap. El siguiente es el código fuente de Get:
public v get (clave de objeto) {// La situación en la que la clave es nulo if (key == null) return getFornullKey (); // encontrar entrada basada en la entrada de entrada de clave <k, v> entry = getEntry (clave); return null == entrada? nulo: Entry.getValue (); }Código fuente de GetFornullKey
privado v getFornullKey () {if (size == 0) {return null; } // Transtraighten la cadena de conflictos para (entrada <k, v> e = table [0]; e! = Null; e = e.next) {if (e.key == null) return e.value; } return null; }La entrada con una llave nula se almacena en la tabla [0], pero la cadena de conflictos en la tabla [0] no necesariamente tiene una clave como nula, por lo que debe atravesarse.
Obtenga entrada de acuerdo con la clave:
Entrada final <k, v> getEntry (clave de objeto) {if (size == 0) {return null; } int hash = (Key == NULL)? 0: hash (clave); // Obtenga la posición de índice en la tabla a través del hash, y luego atraviese la lista vinculada en conflicto para encontrar la 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; }Lo anterior es el proceso de hashmap que lee una entrada y su código fuente. Complejidad del tiempo o (1)
Pon: Escribir elementos
La operación de poner en HASHMAP es relativamente complicada porque habrá una operación de expansión de hashmap durante la operación de PUT.
Cuando se escribe un nuevo elemento, si hay una clave para escribir el elemento en HashMap, se realiza el funcionamiento de reemplazar el valor, que es equivalente a la actualización. Aquí está el código fuente de PUT:
public v put (k key, valor v) {// Si la tabla está vacía, llene si (table == vacía_table) según el umbral de tamaño {inflatetable (umbral); } // Completa la entrada con la clave como NULL if (Key == NULL) return PutfornullKey (valor); // Generar hash para obtener la asignación del índice índice int hash = hash (clave); int i = indexfor (hash, table.length); // Transular la cadena de conflictos del índice actual para encontrar si hay una clave correspondiente para (entrada <k, v> e = table [i]; e! = Null; e = e.next) {objeto k; // Si la clave correspondiente existe, reemplace OldValue y devuelva OldValue if (E.Hash == Hash && ((k = E.Key) == Key || Key.equals (k))) {V OldValue = e.Value; e.value = valor; E.RecordAccess (esto); devolver OldValue; }} // La clave de la entrada recientemente escrita no existe en la cadena de conflictos modCount ++; // insertar una nueva entrada Addentry (hash, clave, valor, i); regresar nulo; }Código fuente de Addentry y CreateEntry:
Void Addentry (int hash, k key, V value, int bucketIndex) {// Antes de insertar una nueva entrada, primero juzga el tamaño del HASHMAP actual y su tamaño de umbral, y seleccione si se expande si ((size> = umbral) && (null! = Tabla [bucketIndex])) {RESISE (2 * TABLE.LIngthing); hash = (nulo! = clave)? hash (clave): 0; bucketIndex = indexfor (hash, table.length); } createEntry (hash, clave, valor, bucketIndex); } void createEntry (int hash, k key, v valor, int bucketIndex) {Entry <k, v> e = table [bucketIndex]; // Método de inserción de la cabeza, la entrada recientemente escrita se inserta en la parte delantera de la primera entrada en la cadena de conflictos en la posición del índice actual. tabla [bucketIndex] = nueva entrada <> (hash, clave, valor, e); tamaño ++; }Lo anterior es el proceso de escribir una entrada en un hashmap y su código fuente. Complejidad del tiempo o (1)
Eliminar el elemento eliminar:
Entrada final <k, v> removeEntryForKey (clave de objeto) {if (size == 0) {return null; } // Calcular el valor hash de acuerdo con la clave y obtener el índice int hash = (clave == nulo)? 0: hash (clave); int i = indexfor (hash, table.length); // Eliminar la lista vinculada, definir dos punteros, pre representa la entrada predecesora <k, v> prev = tabla [i]; Entrada <k, v> e = anterior; // Transraight la cadena de conflictos y elimine toda la clave mientras (e! = Null) {entry <k, v> next = e.next; Objeto k; // si se encuentra (e.hash == hash && ((k = e.key) == key || (key! = Null && key.equals (k)))) {modcount ++; tamaño--; // Encontrar el primer nodo es el nodo que se eliminará si (prev == e) tabla [i] = next; else Prev.next = Next; E.Recordremoval (esto); regresar e; } prev = e; e = siguiente; } return e; }Lo anterior es el proceso de HashMap que elimina una entrada y su código fuente. Complejidad del tiempo o (1)
2. Principio de hash de hashmap (función hash)
La implementación de la función hash en hashmap se realiza a través de hash (objeto k) e indexfor (int h, int longitud). Echemos un vistazo al código fuente a continuación:
final int hash (objeto k) {int h = hashseed; if (0! = h && k instanceOf string) {return sun.misc.hashing.stringhash32 ((string) k); } 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). // para reducir la posibilidad de conflicto h ^ = (h >>> 20) ^ (h >>> 12); devolver h ^ (h >>> 7) ^ (h >>> 4); }Obtenga el código fuente del índice del índice:
static int indexFor (int h, int longitud) {// afirmar integer.bitCount (longitud) == 1: "La longitud debe ser una potencia distinta de cero de 2"; return h & (longitud-1); }HASHMAP mapea las claves para los índices dentro del intervalo de [0, table.length] a través de una función hash. Generalmente hay dos tipos de métodos de indexación:
Hash (clave) % Tabla. Longitud, donde la longitud debe ser un número primo. Hashtable utiliza esta implementación en JDK.
Por razones específicas para usar números primos, puede encontrar pruebas de datos de algoritmo relevantes, que no se establecerán aquí.
hash (clave) y (tabla. Longitud - 1) donde la longitud debe ser para la potencia exponencial. Hashmap en JDK utiliza este método de implementación.
Debido a que el tamaño de la longitud es de 2 tiempos exponenciales, hash (clave) y (Tabla. Longitud - 1) siempre estará entre [0, longitud - 1]. Sin embargo, si hace esto solo, habrá un gran problema con el conflicto, porque el valor del hasticón en Java es de 32 bits. Cuando la capacidad de HASHMAP es pequeña, por ejemplo, cuando 16, cuando realiza operación XOR, el bit alto siempre se descarta, pero después de la operación de bits bajo, la probabilidad de conflicto aumenta.
Por lo tanto, para reducir la probabilidad de ocurrencia de conflicto, se realizan muchas operaciones de bits y operaciones o operaciones en el código.
3. Estrategia de asignación de memoria de hashmap
Capacidad variable de miembros y factor de carga
La capacidad de capacidad requerida es un múltiplo exponencial de 2 en HASHMAP, y la capacidad predeterminada es 1 << 4 = 16. También hay un factor de equilibrio (Factor de carga) en HASHMAP. Los factores excesivamente altos reducirán el espacio de almacenamiento, pero aumentará el tiempo para la búsqueda (buscar métodos Put and Get en Hashmap). El valor predeterminado de LoadFactor es 0.75, que es el valor óptimo dado por sopesar la complejidad del tiempo y la complejidad del espacio.
static final int default_initial_capacity = 1 << 4; // también conocido como 16 static final int maximum_capacity = 1 << 30; float final estático default_load_factor = 0.75f;
Constructor de hashmap
La construcción de hashmap es establecer la capacidad y el valor inicial de LoadFactor
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); this.loadFactor = LoadFactor; Umbral = InicialCapacity; init (); } He dicho antes que esa capacidad en Hashmap debe ser tiempos exponenciales de 2, y no hay límite en el constructor. Entonces, ¿cómo garantizar que el valor de la capacidad sea tiempos exponenciales de 2?
Durante la operación de poner, el código fuente determinará si la tabla hash actual es una tabla vacía. Si es así, llame a Inflatetable (int tosize)
Void privado inflatetable (int tosize) {// Encuentra un poder de 2> = tosize int umbral = (int) math.min (capacidad * loadFactor, maximum_capacity + 1); tabla = nueva entrada [capacidad]; inithashseedasneded (capacidad); }donde RounduptOpowerof2 es obtener la potencia n de 2 mayor o igual que el parámetro dado
Private static int RoundupToPootOf2 (int número) {// afirmar número> = 0: "El número no debe ser negativo"; Número de retorno> = Maximum_Capacity? Maximum_capacity: (número> 1)? Integer.highestonebit ((número - 1) << 1): 1; }Integer.hightestonebit (int) es una operación que conserva el bit más alto de un parámetro dado y cambia los 0 restantes. En pocas palabras, es cambiar el parámetro int a n potencias menores o igual a su máximo 2.
Si el número es n potencia de 2, la broca más alta está en el segundo bit alto original después de la disminución 1, y luego cambia 1 bit a la izquierda para que aún se coloque a la posición de bit más alta. Si el número no es n potencia de 2, el bit más alto sigue siendo el bit más alto original después de la disminución de 1 bit restante para cambiar 1 bit restante para ser
Expandir la capacidad:
Hashmap tendrá un comportamiento de cambio de tamaño cuando la opere. El código fuente específico es el siguiente:
Void reize (int newCapacity) {Entry [] OldTable = table; int // La tabla hash ha alcanzado su capacidad máxima, 1 << 30 if (OldCapacity == Maximum_Capacity) {umbral = Integer.max_value; devolver; } Entrada [] newtable = nueva entrada [newCapacity]; // Transferir la entrada en la antigua a la antigua // El valor de retorno de inithashseedasneeded determina si recalcular la transferencia de valor hash (newtable, inithashseedasneeded (newcapacity)); tabla = newtable; // Recalcular umbral umbral = (int) Math.min (NewCapacity * LoadFactor, Maximum_Capacity + 1); } transferencia void (entrada [] NewTable, Boolean Rehash) {int newCapacity = newtable.length; // transweep oldtable para (entrada <k, v> e: table) {// cadena de conflictos transweep while (null! = E) {entry <k, v> next = e.next; if (rehash) {// recalcule el valor hash e.hash = null == e.key? 0: Hash (E.Key); } int i = indexfor (E.Hash, NewCapacity); // Inserte el elemento en la cabeza, el método de inserción del encabezado E.Next = Newtable [i]; Newtable [i] = E; e = siguiente; }}}Lo anterior es todo el proceso de asignación de memoria hashmap. En resumen, cuando Hashmap pone una entrada, verificará la capacidad actual y el tamaño del umbral para seleccionar si se debe expandir la capacidad. El tamaño de cada expansión es 2 * tabla. Longitud. Durante el período de expansión, determinará si el valor hash debe recalcularse en base a inithashseedasneded.
4. Iterador hashmap
Los iteradores como ValueIterator, KeyIterator, EntryIterator y otros en HashMap se basan en el hashiterator. Echemos un vistazo a su código fuente:
HASHITERATOR DE CLASE RESUMEN PRIVADO <E> Implementa Iterator <E> {Entrada <k, V> Next; // Siguiente entrada para devolver int esperandoModCount; // para el índice INT de Fail Fail; // ranura actual, entrada de índice de tabla <k, v> corriente; // Entrada actual hashiterator () {esperadoModCount = modCount; // Encuentra la primera entrada en la tabla hash if (size> 0) {entrada [] t = table; while (index <t.length && (next = t [index ++]) == null); }} public Final Boolean Hasnext () {return Next! = Null; } Entrada final <k, v> nextEntry () {// hashmap no es seguro de huelga, y al atravesar, aún determina si hay alguna modificación de la estructura de la tabla si (modcount! = ExpectedModCount) arroje nuevo concurrentModificationException (); Entrada <k, v> e = next; if (e == null) tirar nueva nosuchelementException (); if ((next = E.Next) == null) {// Encuentra la siguiente entrada de entrada [] t = tabla; while (index <t.length && (next = t [index ++]) == null); } corriente = e; regresar e; } public void remove () {if (current == null) tirar nueva ilegalStateException (); if (ModCount! = ExpectedModCount) tire nuevo concurrentModificationException (); Objeto k = corriente.key; corriente = nulo; Hashmap.this.removeEntryforkey (k); esperadoModCount = modCount; }}Los tres iteradores, la clave, el valor y la entrada, se encapsulan y se convierten en tres perspectivas de colección: KeySet, valores y entrada. Estas tres perspectivas de recolección admiten las operaciones de eliminación, eliminación y clara de HashMap, y no admiten operaciones ADD y ADDALL.