HashMap es una implementación de interfaz de mapa basada en tablas de hash, que proporciona todas las operaciones de mapeo opcionales y permite valores nulos y construcción nula, fuera de sincronización y sin garantía de orden de mapeo. Registremos el principio de implementación de HashMap.
Almacenamiento interno de hashmap
En HashMap, todas las relaciones de pares de valores clave se almacenan manteniendo una matriz de tabla de variables instantáneas (también conocida como cubo). El cubo es una variedad de objetos de entrada. El tamaño del cubo se puede redimensionar según sea necesario, y la longitud debe ser una potencia de 2. El siguiente código:
/ *** Una matriz de entrada vacía, el valor predeterminado de la entrada final*/ estática final <?,?> [] Vacía_table = {}; / *** cubo, cambiar el tamaño según sea necesario, pero debe ser una potencia de 2*/ entrada transitoria <k, v> [] table = (entrada <k, v> []) vacía_table;Capacidad inicial y factor de carga
HashMAP tiene dos parámetros que afectan el rendimiento, la capacidad inicial y el factor de carga. La capacidad es el número de cubos en la tabla hash, la capacidad inicial es solo la capacidad de la tabla hash cuando se crea, y el factor de carga es una escala en la que la tabla hash puede alcanzar la forma completa 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 debe rehacer (es decir, reconstruir la estructura de datos internos), y la reconstrucción se crea al doble del número de capacidad actual. La capacidad inicial y el factor de carga se pueden establecer a través del constructor. La capacidad inicial predeterminada es de 16 entradas, la capacidad máxima es de 2^30 entradas y el factor de carga predeterminado es 0.75
Un cubo es como un cubo que almacena agua. Su capacidad de almacenamiento inicial predeterminada es de 16 unidades de agua. Cuando se vierte el agua a 16*0.75, la capacidad se ampliará primero a 32 unidades cuando los datos se agregan la próxima vez. 0.75 es el factor de carga, y la capacidad inicial y el factor de carga se pueden establecer al crear un cubo. La capacidad máxima de un cubo es de 2 unidades de agua a la potencia de 30. Cuando el número de configuraciones de capacidad inicial es mayor que la capacidad máxima, prevalecerá la capacidad máxima. Al expandirse, se devolverá directamente si es mayor o igual a la capacidad máxima.
El siguiente es parte del código fuente de HashMap, que define la capacidad inicial predeterminada, el factor de carga y algunas otras constantes:
/ ** * La capacidad inicial predeterminada debe ser el poder de 2. */ Static final int default_initial_capacity = 1 << 4; // también conocido como 16/ *** Capacidad máxima, si la capacidad inicial es mayor que la capacidad máxima a través del parámetro del constructor, la capacidad también se utilizará como la capacidad inicial* debe ser la potencia de 2 y menor o igual a la potencia 30 de 2*/ estática final int maximum_capacity = 1 << 30; / *** El factor de carga predeterminado puede especificarse mediante el constructor*/ static final float default_load_factor = 0.75f; / *** Una tabla de matriz vacía, cuando el cubo no se inicializa*/ Entrada final estática <?,?> [] Vacía_table = {}; / *** Bucket, almacena todas las entradas de par de valores clave, y se puede cambiar el tamaño según sea necesario, y la longitud debe ser una potencia de 2*/ entrada transitoria <k, v> [] table = (entrada <k, v> []) vacía_table; /*** El número de pares de valor clave en el mapa, el tamaño será de operación +1 o -1 cada vez que se agrega o elimine. */ Tamaño transitorio int; /** * El valor crítico del valor de carga, que debe redimensionarse es: (capacidad * factor de carga). Después de cada cambio de tamaño, la nueva capacidad se calculará utilizando la nueva capacidad. * @serial */ // if table == vacía_table, entonces esta es la capacidad inicial en la que se creará la tabla // cuando se inflará. umbral int; / ** * Factor de carga, si no se especifica en el constructor, se usa el factor de carga predeterminado, * * @serial */ final float loadFactor; /** * Número de veces Modificaciones de la estructura HASHMAP, cambie el número de mapas en el hashmap o modifique su estructura interna cuando la estructura se modifica (por ejemplo, el método de rehash *, reconstruye la estructura de datos internos). Este campo se usa en * Los iteradores generados en la vista de colección HashMap se procesan en Fast Falling */Transient int ModCount;Capacidad inicial y ajuste del rendimiento del factor de carga
Por lo general, el factor de carga predeterminado (0.75) busca un compromiso en los costos de tiempo y espacio. Aunque el factor de carga es demasiado alto, también aumenta el costo de la consulta (esto se refleja en la mayoría de las operaciones de hashmap, incluidas las operaciones de Get and Put). Al establecer la capacidad inicial, se debe tener en cuenta el número de entradas requeridas en el mapa y su factor de carga para minimizar el número de operaciones de repetición. Si la capacidad inicial es mayor que el número máximo de entradas divididas por el factor de carga, no se producirá la operación de rehacer.
Si muchas relaciones de mapeo se almacenarán en una instancia de hashmap, crearlo con una capacidad inicial lo suficientemente grande hará que la relación de mapeo se almacene de manera más eficiente en relación con la realización de operaciones automáticas de repetición a pedido para aumentar la capacidad de la tabla.
El siguiente es el código para reconstruir la estructura de datos hashmap:
Void reize (int newCapacity) {Entry [] OldTable = table; int if (OldCapacity == Maximum_Capacitity) {// Si la capacidad ha alcanzado el límite máximo, establezca el valor de carga y vuelva directamente al umbral = integer.max_value; devolver; } // Cree una nueva tabla para almacenar la entrada de datos [] newtable = nueva entrada [newCapacity]; // Transferir los datos de la tabla antigua a la nueva tabla, este paso llevará mucho tiempo transferir (NewTable, InithashSeedasNeeded (NewCapacity)); tabla = newtable; // finalmente establece el valor de carga del siguiente umbral de cambio de tamaño = (int) Math.min (NewCapacity * LoadFactor, Maximum_Capacity + 1);}Método de construcción de hashmap
El cuarto método de construcción es crear un nuevo hashmap con un mapa existente. Hablemos de ello más tarde. De hecho, los primeros tres métodos de construcción se llaman en el tercer método final con dos parámetros. Si no se pasan parámetros, se usa el valor predeterminado. El código es el siguiente:
/** * Construye un vacío <Tt> Hashmap </tt> con la capacidad inicial predeterminada * (16) y el factor de carga predeterminado (0.75). */ public hashmap () {this (default_initial_capacity, default_load_factor); } /** * Construye un vacío <Tt> Hashmap </tt> con la capacidad inicial * especificada y el factor de carga predeterminado (0.75). * * @param InicialCapacity La capacidad inicial. * @throws ilegalArgumentException si la capacidad inicial es negativa. */ public hashmap (int InitialCapacity) {this (inicialCapacity, default_load_factor); } /** * Construye un vacío <Tt> Hashmap </tt> con la capacidad inicial * especificada * Factor de carga. * * @param Inicialcapacidad La capacidad inicial * @param LoadFactor El factor de carga * @throws ilegalArgumentException Si la capacidad inicial es negativa * o el factor de carga es no positivo */ public Hashmap (int InitialCapacity, Float LoadFactor) {if ((inicial <0) tire una nueva concepción ilegalArgumentException ("Capacidad inicial:" +inicialcapacidad); 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 (); }Como se puede ver en lo anterior, en el constructor, si la capacidad inicial es mayor que la capacidad máxima, la capacidad máxima se reemplazará directamente.
poner el método
A continuación, echemos un vistazo a las partes más importantes del hashmap
/*** En este mapa, el valor especificado y la compilación especificada están asociados. Si el mapa contenía previamente una relación de mapeo de la clave, el valor anterior se reemplazó** @param especifica la clave para asociar* @param Especifica el valor que se asociará* @return El valor anterior asociado con la clave, si la clave no tiene relación de asignación, devuelve nulo (returning null puede significar que el mapeo se asoció con la clave antes)*/ public v put (k key, value), valor nulo (table de retorno también puede significar que la mapeable se ha asociado con la clave)*/ public v. inflatetable (umbral); } 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); regresar nulo; }1. Primero, en el método PUT, primero determine si el cubo está en el estado no inicializado predeterminado. Si no se inicializa, llame al método inflatetable para inicializarlo y luego determine si la tecla de parámetro es nula. Si es nulo, llame a Putfornullkey específicamente para poner los datos con la clave como nulo. El método PutfornullKey es en realidad el mismo que el siguiente paso 3, excepto que la ubicación de almacenamiento predeterminada de los datos con la clave como nulo es el primero, es decir, el subíndice predeterminado es 0.
2. Si la clave no es nula, llame al método hash () para obtener el valor hash de la clave. Puede calcular la posición donde la clave se puede colocar en el cubo en función del valor hash y la longitud del cubo.
3. Hay un atributo a continuación en el objeto de entrada, que puede formar una lista vinculada unidireccional para almacenar elementos con el mismo valor hash. Por lo tanto, cuando se calcula el valor hash de la clave, la ubicación de almacenamiento también se repetirá. Simplemente juzgue si el elemento de la ubicación de almacenamiento y la siguiente lista de atributos del elemento es exactamente el mismo que el valor hash de la clave y la clave dada. Si hay uno completamente consistente, significa que ya existe, reemplace el valor anterior y devuelva el valor anterior directamente como el valor de retorno.
4. Aumente el número de modificaciones estructurales por 1
5. Llame al método Addentry para agregar el nuevo par de valores clave al hashmap. El método de adicionalidad primero determina si los datos de entrada actuales son mayores o iguales al valor de carga (la capacidad del factor de carga *) y la posición especificada del cubo no es nula. Si ya es mayor que y la posición especificada no es nula, la capacidad del cubo de ajuste es el doble de la capacidad actual. La capacidad del cubo de ajuste se hace referencia a la capacidad inicial y al directorio de ajuste de rendimiento del factor de carga anterior. Recalcule el valor hash y calcule la ubicación de almacenamiento. Llame al método CreateEntry para almacenarlo en el cubo
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 valor, int bucketIndex) {Entry <k, v> e = table [bucketIndex]; tabla [bucketIndex] = nueva entrada <> (hash, clave, valor, e); tamaño ++; } /*** Método de constructor de entrada para crear una nueva entrada. */ Entrada (int h, k k, v v, entrada <k, v> n) {valor = v; siguiente = n; clave = k; hash = h; }6. En el método CreateEntry, primero obtenga la entrada en la ubicación especificada y luego genere una nueva entrada. Al generar la entrada, almacene la entrada original en la siguiente propiedad de la entrada recién generada (consulte el método de construcción de entrada) y reemplace la entrada en la ubicación especificada con la recién generada.
Porque al agregar nuevas entradas, el valor hash debe calcularse, y cuando la longitud no es suficiente, la longitud debe ajustarse. Cuando hay elementos en la ubicación de almacenamiento calculada, la lista vinculada debe almacenarse, por lo que la eficiencia de usar HashMap para agregar nuevas operaciones no es demasiado alta.
Obtener método
Primero, veamos el código fuente del método GET:
/*** Devuelve el valor asignado por la clave especificada; Si este mapa no contiene ninguna relación de mapeo para esta clave, devuelve nulo * devolver un valor nulo no significa necesariamente que el mapa no contenga la asignación de la clave, y también puede cambiar la asignación a NULL. Puede usar la operación ContinsKey para distinguir entre estas dos situaciones * @see #put (objeto, objeto) */ public v get (clave de objeto) {if (key == null) return getFornullKey (); Entrada <k, v> entry = getEntry (clave); return null == entrada? nulo: 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;}El método GET es fácil de implementar, y los siguientes son algunos pasos:
Al observar el código fuente de Get, podemos encontrar que el método GET calcula la ubicación de almacenamiento a través del valor hash de la clave y la longitud del cubo. Básicamente, puede localizar el elemento que está buscando. Incluso si atraviesa algunas claves con valores de hash repetidos, es muy rápido. Debido a que el valor hash es relativamente único, el hashmap es muy rápido para buscar.
Objeto personalizado como clave para hashmap
Usuario de clase {// número de identificación protegido int idnumber; Usuario público (int id) {idnumber = id; }} public class testUser {public static void main (string [] args) {map <user, string> map = new Hashmap <user, string> (); for (int i = 0; i <5; i ++) {map.put (nuevo usuario (i), "Nombre:"+i); } System.out.println ("Nombre del usuario3:" + map.get (nuevo usuario (3))); }} Salida: User3 Nombre: NULLComo se mencionó anteriormente, cuando se usa una instancia de clase de usuario personalizada como un objeto hashmap, el nombre de User3 no se puede encontrar al imprimir, porque la clase de usuario hereda automáticamente el objeto de clase base, por lo que el método hashcode de objeto se utilizará automáticamente para generar un valor hash, y utiliza la dirección del objeto para calcular el valor hash de forma predeterminada. Por lo tanto, el valor hash de la primera instancia generado por el nuevo usuario (3) es diferente del valor hash de la segunda instancia generada. Sin embargo, si solo necesita anular el método hashcode, no funcionará correctamente, a menos que anule el método igual al mismo tiempo, también es parte del objeto. HashMap usa igual () para determinar si la clave actual es la misma que las claves presentes en la tabla. Puede consultar el método Get o Put anterior.
El método correcto iguales () debe cumplir con las siguientes 5 condiciones: --- Consulte "Pensamientos de programación de Java" -Página 489
Nuevamente : el objeto predeterminado.equals () es solo la dirección del objeto de comparación, por lo que un nuevo usuario (3) no es igual a otro usuario nuevo (3). Por lo tanto, si desea usar su propia clase como la clave para HashMap, debe sobrecargar tanto hashcode () como igual ().
El siguiente código funciona normalmente:
Usuario de clase {// número de identificación protegido int idnumber; Usuario público (int id) {idnumber = id; } @Override public int hashcode () {return idnumber; } @Override public boolean iguales (object obj) {return obj instanceOf user && (idnumber == ((usuario) obj) .idnumber); }} public class testUser {public static void main (string [] args) {map <user, string> map = new Hashmap <user, string> (); for (int i = 0; i <5; i ++) {map.put (nuevo usuario (i), "Nombre:"+i); } System.out.println ("Nombre del usuario3:" + map.get (nuevo usuario (3))); }} Salida: Nombre del usuario3: Nombre: 3Lo anterior simplemente devuelve IdNumber como la única discriminación en hashcode, y los usuarios también pueden implementar sus propios métodos de acuerdo con su propio negocio. En el método igual, InstanceOF verificará en silencio si el objeto es nulo. Si el parámetro a la izquierda de instanciaf es nulo, se devolverá False. Si el parámetro de Equals () no es nulo y el tipo es correcto, la comparación se basará en el Number real en cada objeto. Como se puede ver en la salida, el método actual es correcto.
referirse a:
"Pensamientos de programación de Java"
JDK 1.6 Manual de ayuda china
Lo anterior es todo el contenido de este artículo. Espero que el contenido de este artículo sea de ayuda para el estudio o el trabajo de todos. ¡También espero apoyar a Wulin.com más!