Análisis del principio de hashmap en Java

Primero veamos una pregunta de entrevista:

Una serie de pares de valor clave almacenados en un hashmap, donde la clave es un tipo determinado que personalizamos. Después de colocar hashmap, cambiamos los atributos de una clave externamente, y luego usamos esta clave para eliminar elementos del hashmap. ¿Qué volverá hashmap en este momento?

El código de muestra y las respuestas se han dado en el artículo, pero no se da ninguna explicación sobre el principio de hashmap.

1. Características

Podemos usar cualquier clase como la clave hashmap, pero ¿cuáles son las restricciones en estas clases? Veamos el siguiente código:

 Persona de clase pública {nombre de cadena privada; Persona pública (nombre de cadena) {this.name = name; }} Mapa <persona, string> testMap = new Hashmap <> (); testMap.put (nueva persona ("hola"), "mundo"); testMap.get (nueva persona ("hola")); // ---> nulo

Originalmente quería obtener el valor de la clase de la persona con valores de campo iguales, pero el resultado fue nulo. Cualquiera que tenga un poco de conocimiento de HashMap puede ver que la clase de la persona no tiene un método de húsico anulada, lo que conduce a su herencia del objeto hashcode (el regreso es su dirección de memoria). Esta es también la razón por la cual las clases invariantes como la cadena (o entero, etc.) se usan comúnmente como la clave de HASHMAP. Entonces, ¿cómo usa HashMap hashcode para indexar rápidamente la clave?

2. Principio

Primero, echemos un vistazo a una solución simple de implementación del hashmap en "Pensar en Java":

 //: contenedores/simpleshashmap.java // una demostración hashed map.import java.util.*; import net.mindview.util.*; clase pública Simplehashmap <k, v> extiende abstractmap <k, v> {// elige un número primario para el tamaño de la tabla hash, para lograr una distribución no uniforme: el tamaño final estático = 997; // no puede tener una variedad física de genéricos, pero puede volver a uno: @suppleswarnings ("sin control") LinkedList <MapEntry <k, v >> [] buckets = new LinkedList [size]; public v put (k key, v valor) {v oldValue = null; int index = math.abs (key.hashcode ()) % tamaño; if (buckets [index] == null) cubos [index] = new LinkedList <MapEntry <k, v >> (); LinkedList <MapEntry <k, v >> bucket = buckets [index]; Mapentry <k, v> par = new MapEntry <k, v> (clave, valor); booleano encontrado = falso; ListIterator <MapEntry <k, v >> it = bucket.ListIterator (); while (it.hasnext ()) {MapEntry <k, v> ipair = it.next (); if (ipair.getKey (). Equals (Key)) {OldValue = ipair.getValue (); it.set (par); // reemplazar antiguo con nuevo encontrado = verdadero; romper; }} if (! encontrado) cubos [índice] .add (par); devolver OldValue; } public v get (clave de objeto) {int index = math.abs (key.hashcode ()) % size; if (buckets [index] == null) return null; for (MapEntry <k, v> ipair: buckets [index]) if (ipair.getKey (). Equals (Key)) return ipair.getValue (); regresar nulo; } set público <map.entry <k, v >> entrySet () {set <map.entry <k, v >> set = new Hashset <map.entry <k, v >> (); para (LinkedList <MapEntry <k, v >> bucket: buckets) {if (bucket == null) continuar; para (Mapentry <k, v> mpair: bucket) set.add (mpair); } Conjunto de retorno; } public static void main (string [] args) {simplyhashmap <string, string> m = new SimpleHashMap <String, String> (); M.putall (países. Capitales (25)); System.out.println (m); System.out.println (M.get ("eritrea")); System.out.println (m.Entryset ()); }}

SimpleHashmap construye una mesa hash para almacenar claves. La función hash es la operación de módulo Math.abs (key.hashcode ()) %de tamaño, y el conflicto hash se resuelve utilizando el método de lista vinculada; Cada ranura de cubos almacena mapa. Ingreso con el mismo valor del índice (hash), como se muestra en la figura a continuación:

El principio de implementación del hashmap de JDK es similar al que utiliza la tabla hash de la dirección de la cadena para almacenar map.entry:

 /*** La tabla, redimensionada según sea necesario. La longitud siempre debe ser un poder de dos. */Entrada transitoria <k, v> [] table = (entrada <k, v> []) vacía_table; entrada de clase estática <k, v> implementa map.entry <k, v> {key final k final; V valor; Entrada <k, v> siguiente; int hash; …}

El índice de map.Entry se obtiene al hash el hashcode de la clave. Cuando desee obtener el valor correspondiente a la clave, calcule su índice para la clave y luego elimine el map.Entry en la tabla para obtenerlo. Para más detalles, consulte el código:

 public v get (clave de objeto) {if (key == null) return getFornullKey (); Entrada <k, v> entry = getEntry (clave); return null == entrada? null: entry.getValue ();} Entrada final <k, v> getEntry (clave de objeto) {if (size == 0) {return null; } 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;}

Se puede ver que el cónimo de hash afecta directamente la eficiencia de la función hash de hashmap: un buen hashcode reducirá en gran medida los conflictos hash y mejorará el rendimiento de la consulta. Al mismo tiempo, esto también explica las dos preguntas planteadas al principio: si una clase personalizada hace la clave hashmap, el cálculo de hashcode debería cubrir todos los campos del constructor, de lo contrario es posible obtener nulo.