La mayoría de los desarrolladores de Java usan MAP, especialmente hashmap. Hashmap es una forma simple pero poderosa de almacenar y obtener datos. Pero, ¿cuántos desarrolladores saben cómo funciona Hashmap internamente? Hace unos días, leí mucho código fuente de java.util.hashmap (incluidos Java 7 y Java 8) para obtener una comprensión profunda de esta estructura de datos básica. En esta publicación, explicaré la implementación de java.util.hashmap, describiré las nuevas características agregadas en la implementación de Java 8 y discutiré el rendimiento, la memoria y algunos problemas conocidos cuando se usa HashMap.
Almacenamiento interno
La clase Java Hashmap implementa la interfaz MAP <K, V>. Los principales métodos en esta interfaz incluyen:
V put (k key, v value) v get (clave de objeto) v remove (tecla de objeto) boolean contiene key (tecla de objeto)
HashMap utiliza una entrada de clase interna <K, V> para almacenar datos. Esta clase interna es un par simple de valor clave con dos datos adicionales:
Una referencia a otra entrada, para que HashMap pueda almacenar objetos como listas de enlaces.
Un valor hash utilizado para representar la clave. Almacenar este valor puede evitar que hashmap regenere el valor hash correspondiente a la clave cada vez que se necesita.
Aquí hay una parte del código de entrada <k, v> bajo Java 7:
Entrada de clase estática <k, v> implementa map.entry <k, v> {fin final k key; v valor; entrada <k, v> next; int hash; ...}Hashmap almacena datos en múltiples listas unidireccionales (a veces llamadas cubos o contenedores Orbins). Todas las listas están registradas en una matriz de entrada (entrada <k, v> [] matriz), y la longitud predeterminada de esta matriz interna es 16.
La siguiente figura describe el almacenamiento interno de una instancia de hashmap, que contiene una matriz de objetos anulables. Cada objeto está conectado a otro objeto, formando así una lista vinculada.
Todas las claves con el mismo valor hash se colocarán en la misma lista vinculada (cubo). Las teclas con diferentes hashes pueden terminar en el mismo cubo.
Cuando las llamadas al usuario se ponen (k clave, valor v) o obtengan (clave de objeto), el programa calcula el índice del cubo que debe estar el objeto. El programa luego iterará sobre la lista correspondiente para encontrar el objeto de entrada con la misma tecla (usando el método igual () de la clave).
En el caso de llamar get (), el programa devolverá el objeto de entrada correspondiente al valor (si el objeto de entrada existe).
Para la llamada para poner (K Key, V Value), si el objeto de entrada ya existe, el programa reemplazará el valor con un nuevo valor; de lo contrario, el programa creará una nueva entrada (clave y valor en el parámetro) en el encabezado de la lista vinculada unidireccional.
El índice del cubo (lista vinculada) se genera a través de 3 pasos del mapa:
Primero obtenga el código hash de la clave.
El programa repite el código hash para bloquear las funciones de hash malas para las claves, porque esto tiene el potencial de poner todos los datos en el mismo índice (cubo) de la matriz interna.
El programa toma el código de hash duplicado y usa una masilla de bits de la longitud de la matriz (mínimo 1) para ello. Esta operación asegura que el índice no sea mayor que el tamaño de la matriz. Puede pensar en ello como una función de módulo optimizado calculada.
Aquí está el código fuente para generar el índice:
// La función "Rehash" en Java 7 que toma el HASHCODE del KeyStatic int hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);} // la función "rehash" en java 8 que toma directamente el intento final de la tecla intra (inth inth) (int h; 0: (h = key.hashcode ()) ^ (h >>> 16);} // La función que devuelve el índice del índice Hashstatic int rehashed int indexFor (int h, int h, int long) {return h & (longitud-1);}Para trabajar de manera más eficiente, el tamaño de la matriz interna debe ser un poder de 2. Veamos por qué:
Suponiendo que la longitud de la matriz es 17, el valor de la máscara es 16 (longitud de matriz-1). La representación binaria de 16 es 0 ... 010000, de modo que para cualquier valor H, el resultado de "H & 16" es 16 o 0. Esto significa que las matrices de longitud 17 solo se pueden aplicar a dos cubos: uno es 0 y el otro es 16, lo que no es muy eficiente. Pero si establece la longitud de la matriz en una potencia de 2, por ejemplo 16, entonces la indexación de bits funciona a "H & 15". La representación binaria de 15 es 0 ... 001111, y la salida del valor por la fórmula del índice puede variar de 0 a 15, de modo que se puede usar una matriz de longitud 16. Por ejemplo:
Si H = 952, su representación binaria es 0..01110111000, y el índice correspondiente es 0 ... 01000 = 8
Si H = 1576, su representación binaria es 0..011000101000, y el índice correspondiente es 0 ... 01000 = 8
Si H = 12356146, su representación binaria es 0..0101111001000101010010, el índice correspondiente es 0 ... 00010 = 2
Si H = 59843, su representación binaria es 0..01110100111000011, su índice correspondiente es 0 ... 00011 = 3
Este mecanismo es transparente para el desarrollador: si selecciona un hashmap de longitud 37, el mapa seleccionará automáticamente el siguiente valor de potencia superior a 37 (64) como la longitud de la matriz interna.
Cambiar el tamaño automáticamente
Después de obtener el índice, los métodos get (), put () o eliminar () accederán a la lista vinculada correspondiente para ver si el objeto de entrada para la clave especificada ya existe. Sin modificación, este mecanismo puede causar problemas de rendimiento, ya que este método requiere iterarse en toda la lista para ver si el objeto de entrada existe. Suponga que la longitud de la matriz interna toma el valor predeterminado de 16, y necesita almacenar 2,000,000 de registros. En el mejor de los casos, habrá 125,000 objetos de entrada por lista vinculada (2,000,000/16). Los métodos get (), eliminar () y pon () requieren 125,000 iteraciones cada vez que se ejecutan. Para evitar esto, hashmap puede aumentar la longitud de la matriz interna, asegurando así que solo unos pocos objetos de entrada se conservan en la lista vinculada.
Cuando crea un hashmap, puede especificar una longitud inicial y un factor de carga a través del siguiente constructor:
</pre> pública hashmap (int InitialCapacity, Float LoadFactor) <pre>
Si no especifica los parámetros, el valor de capacidad inicial predeterminada es 16, y el valor de carga de carga predeterminado es 0.75. La capacidad inicial representa la longitud de la lista vinculada de la matriz interna.
Cuando usa el método PUT (...) para agregar un nuevo par de valores clave al mapa, el método verifica si la longitud de la matriz interna debe aumentarse. Para lograr esto, el mapa almacena 2 datos:
Tamaño del mapa: representa el número de registros en hashmap. Actualizamos el valor cuando lo insertamos o lo eliminamos en el hashmap.
Umbral: es igual a la longitud de la matriz interna*LoadFactor, y este umbral también se actualizará al mismo tiempo cada vez que se ajuste la longitud de la matriz interna.
Antes de agregar un nuevo objeto de entrada, el método PUT (...) verifica si el tamaño del mapa actual es mayor que el umbral. Si es mayor que el umbral, crea una nueva matriz con el doble de la longitud de la matriz interna actual. Debido a que el tamaño de la nueva matriz ha cambiado, la función de índice (es decir, el resultado de la operación de bit que devuelve el "valor hash de la clave y (longitud de la matriz -1)") también cambia. El cambio de tamaño de la matriz crea dos nuevos cubos (listas vinculadas) y reasigna todos los objetos de entrada existentes al cubo. El objetivo de ajustar el tamaño de la matriz es reducir el tamaño de la lista vinculada, reduciendo así el tiempo de ejecución de los métodos put (), eliminar () y get (). Para todos los objetos de entrada correspondientes a las claves con el mismo valor hash, se asignan al mismo balde después de cambiar el tamaño. Sin embargo, si los valores hash de los dos objetos de entrada son diferentes, pero estaban en el mismo balde antes, luego, después del ajuste, no hay garantía de que todavía estén en el mismo cubo.
Esta imagen describe la situación de las matrices internas previas al ajuste y después del ajuste. Antes de ajustar la longitud de la matriz, para obtener el objeto de entrada E, el mapa debe iterar sobre una lista vinculada que contiene 5 elementos. Después de ajustar la longitud de la matriz, el mismo método get () solo necesita atravesar una lista vinculada que contiene 2 elementos, por lo que la velocidad de ejecución del método get () después de ajustar la longitud de la matriz aumenta 2 veces.
Seguridad
Si ya está muy familiarizado con HashMap, definitivamente sabe que no es seguro de hilos, pero ¿por qué? Por ejemplo, suponga que tiene un hilo de escritor que solo insertará los datos existentes en el mapa, un hilo del lector que leerá datos del mapa, entonces, ¿por qué no funciona?
Porque bajo el mecanismo de cambio de tamaño automático, si el subproceso intenta agregar u obtener un objeto, el mapa puede usar el valor de índice anterior, de modo que no se encuentre el nuevo cubo donde se encuentra el objeto de entrada.
En el peor de los casos, cuando 2 subprocesos insertan datos al mismo tiempo, 2 llamadas put () comenzarán al mismo tiempo y la matriz cambiará automáticamente. Dado que dos hilos modifican la lista vinculada al mismo tiempo, es posible que el mapa salga en el bucle interno de una lista vinculada. Si intenta obtener datos de una lista con un bucle interno, el método get () nunca finalizará.
Hashtable proporciona una implementación segura de hilos que evita que ocurra lo anterior. Sin embargo, dado que todas las operaciones sincrónicas de crud son muy lentas. Por ejemplo, si las llamadas de Thread 1 obtienen (KEY1), entonces las llamadas de hilo 2 get (Key2) y las llamadas de Thread 2 obtienen (Key3), luego en un tiempo especificado, solo 1 subproceso puede obtener su valor, pero los 3 subprocesos pueden acceder a estos datos al mismo tiempo.
Desde Java 5, tenemos una implementación de hashmap mejor y segura de hilo: concurrenthashmap. Para concurrentes mapas, solo los cubos se sincronizan, de modo que si múltiples hilos no usan el mismo cubo o cambiar el tamaño de la matriz interna, pueden llamar a los métodos get (), eliminar () o poner () al mismo tiempo. En una aplicación múltiple, este enfoque es una mejor opción.
Invariancia de bonos
¿Por qué es una buena implementación usar cadenas e enteros como claves para el hashmap? ¡Principalmente porque son inmutables! Si elige crear una clase usted mismo como clave, pero no puede garantizar que la clase sea inmutable, puede perder datos dentro de Hashmap.
Veamos los siguientes casos de uso:
Tiene una clave cuyo valor interno es "1".
Si inserta un objeto en un hashmap, su clave es "1".
Hashmap genera valores hash del código hash de la clave (es decir, "1").
Mapa almacena este valor hash en el registro recién creado.
Cambia el valor interno de la clave y lo cambia a "2".
El valor hash de la clave cambió, pero hashmap no lo sabe (porque el valor de hash anterior se almacena).
Intenta obtener el objeto correspondiente mediante la clave modificada.
MAP calcula el valor hash de la nueva clave (es decir, "2") para encontrar la lista vinculada (cubo) donde se encuentra el objeto de entrada.
Caso 1: Como ha modificado la clave, el mapa intentará buscar el objeto de entrada en el cubo incorrecto, pero no se encuentra.
Caso 2: Tiene suerte de que el cubo generado por la tecla modificada y el cubo generado por la tecla anterior sean los mismos. Luego, el mapa atravesará la lista vinculada y se ha encontrado un objeto de entrada con la misma clave. Pero para encontrar la clave, el mapa primero comparará el valor hash de la clave llamando al método igual (). Debido a que la clave modificada generará diferentes valores hash (los valores hash antiguos se almacenan en el registro), entonces MAP no tiene forma de encontrar el objeto de entrada correspondiente en la lista vinculada.
Aquí hay un ejemplo de Java en el que insertamos dos pares de valores clave en el mapa, y luego modifico la primera clave e intento obtener los dos objetos. Encontrará que solo el segundo objeto devuelto del mapa, el primer objeto se ha "perdido" en el hashmap:
public class MutableKeyTest {public static void main (string [] args) {class myKey {integer i; public void seti (integer i) {this.i = i;} public mykey (Integer i) {this.i = i;}@overridePublic intSkcode () {return i;}@overDeP -booleN Ecals (oBj OBJ OBJ OBJ (OBJ OBJ) Mykey) {return i.equals (((mykey) obj) .i);} elsereturn false;}} map <mykey, string> mymap = new HashMap <> (); mykey key1 = new myKey (1); mykey key2 = new mykey (2); mymap.put (key1, "test" + 1); mymap.put (key2, "test" test "; Key1Key1.seti (3); String test1 = mymap.get (key1); string test2 = mymap.get (key2); system.out.println ("test1 =" + test1 + "test2 =" + test2);}}La salida del código anterior es "test1 = null test2 = test 2". Como esperamos, MAP no tiene la capacidad de obtener la cadena 1 correspondiente a la clave modificada 1.
Mejoras en Java 8
En Java 8, la implementación interna en Hashmap se ha modificado mucho. De hecho, Java 7 usa 1000 líneas de código para implementarlo, mientras que Java 8 usa 2000 líneas de código. La mayor parte de lo que describí anteriormente todavía es correcto en Java 8, excepto usar listas vinculadas para guardar objetos de entrada. En Java 8, todavía usamos matrices, pero se guardará en el nodo, que contiene la misma información que el objeto de entrada anterior y también usa una lista vinculada:
Aquí hay parte del código que implementa el nodo en Java 8:
nodo de clase estática <k, v> implementa map.entry <k, v> {final int hash; final k key; v valor; nodo <k, v> next;Entonces, ¿cuál es la gran diferencia en comparación con Java 7? Bueno, el nodo se puede extender a Treenode. TreeNode es una estructura de datos de un árbol rojo y negro que puede almacenar más información, por lo que podemos agregar, eliminar u obtener un elemento bajo la complejidad de O (log (n)). El siguiente ejemplo describe toda la información guardada por TreeNode:
Clase final estática TreeNode <K, V> extiende Linkedhashmap.Entry <k, V> {final int hash; // heredado de la tecla de nodo <k, v> final K; // heredado del nodo <k, v> v valor; // heredado del nodo <k, v> nodo <k, v> siguiente; // heredado del nodo <k, v> entrada <k, v> antes, después; // heredado de linkedhashmap.entry <k, v> parent; treeNode <k, v> izquierdo; treeNode <k, v> derecho; treeNode <k, v> previo; booleano rojo;Los árboles rojos y negros son árboles de búsqueda binarios autoequilibrados. Su mecanismo interno asegura que su longitud siempre sea log (n), ya sea que agregamos o eliminemos nodos. El beneficio más importante de usar este tipo de árbol es que es el caso que muchos datos en la tabla interna tienen el mismo índice (cubo). En este momento, la complejidad de buscar en el árbol es o (log (n)), y para la lista vinculada, la complejidad es o (n) para realizar la misma operación.
Como puede ver, almacenamos más datos en el árbol que las listas vinculadas. De acuerdo con el principio de herencia, la tabla interna puede contener nodo (lista vinculada) o treenode (árbol rojo y negro). Oracle decide usar estas dos estructuras de datos de acuerdo con las siguientes reglas:
- Para el índice especificado (cubo) en la tabla interna, si el número de nodos es más de 8, la lista vinculada se convertirá en un árbol rojo y negro.
- Para el índice especificado (cubo) en la tabla interna, si el número de nodos es inferior a 6, el árbol rojo y negro se convertirá en una lista vinculada.
Esta imagen describe una matriz interna en un hashmap Java 8, que contiene listas de árbol (cubo 0) y vinculadas (cubo 1, 2 y 3). El cubo 0 es una estructura de árbol porque contiene más de 8 nodos.
Sobrecarga de memoria
Java 7
El uso de hashmap consume algo de memoria. En Java 7, Hashmap encapsula los pares de valor clave en los objetos de entrada, un objeto de entrada contiene la siguiente información:
Referencia al siguiente registro un valor hash precalculado (entero)
Una referencia a una clave y una referencia a un valor
Además, hashmap en Java 7 utiliza una matriz interna de objetos de entrada. Supongamos que un java 7 hashmap contiene n elementos y su matriz interna tiene capacidad, entonces el consumo de memoria adicional es:
sizeof (entero)* n + sizeof (referencia)* (3* n + c)
en:
El tamaño de un entero es de 4 bytes
El tamaño de la referencia depende del JVM, el sistema operativo y el procesador, pero generalmente son 4 bytes.
Esto significa que la sobrecarga de memoria total suele ser de 16 * n + 4 * bytes de capacidad.
NOTA: Después de que el mapa se redimense automáticamente, el valor de la capacidad es la siguiente potencia más pequeña de 2 mayor que N.
Nota: A partir de Java 7, Hashmap adopta un mecanismo de carga perezoso. Esto significa que incluso si especifica el tamaño para HASHMAP, la matriz interna utilizada (consumiendo bytes de 4*capacidad) que no se asigna en la memoria antes de usar el método Put () Put ().
Java 8
En las implementaciones de Java 8, el uso de la memoria de cálculo se vuelve más complicado porque el nodo puede almacenar los mismos datos que la entrada o agregar 6 referencias y una propiedad booleana (especificando si es un treeNode).
Si todos los nodos son solo nodos, entonces la memoria consumida por Java 8 Hashmap es la misma que la consumida por Java 7 Hashmap.
Si todos los nodos son Treenode, entonces la memoria consumida por Java 8 Hashmap se convierte en:
N * sizeof (entero) + n * sizeof (boolean) + sizeof (referencia) * (9 * n + capacidad)
En la mayoría de los JVM estándar, el resultado de la fórmula anterior es 44 * n + 4 * bytes de capacidad.
Problemas de rendimiento
Hashmap asimétrico vs hashmap equilibrado
En el mejor de los casos, los métodos get () y put () solo tienen o (1) complejidad. Sin embargo, si no le importa la función hash de la clave, sus métodos put () y get () pueden ejecutarse muy lentamente. La ejecución eficiente de los métodos put () y get () depende de los datos que se asignan a diferentes índices de la matriz interna (cubo). Si la función hash de la clave no está diseñada correctamente, obtendrá una partición asimétrica (independientemente del tamaño de los datos internos). Todos los métodos put () y get () utilizarán la lista vinculada más grande, que será lenta para ejecutar porque requiere iterarse en todos los registros en la lista vinculada. En el peor de los casos (si la mayoría de los datos están en el mismo cubo), su complejidad de tiempo se convierte en O (n).
Aquí hay un ejemplo visual. El primer gráfico describe un hashmap asimétrico y el segundo gráfico describe un hashmap igualado.
sesgo
En este hashmap asimétrico, llevará tiempo ejecutar los métodos get () y poner () en el cubo 0. Obtener el registro K toma 6 iteraciones.
En este hashmap equilibrado, solo se necesitan 3 iteraciones para obtener el registro K. Estos dos hashmaps almacenan la misma cantidad de datos y las matrices internas son del mismo tamaño. La única diferencia es la función hash de la clave, que se utiliza para distribuir registros en diferentes cubos.
Aquí hay un ejemplo extremo escrito en Java, en el que uso una función hash para poner todos los datos en la misma lista vinculada (cubo) y luego agregué 2,000,000 de datos.
prueba de clase pública {public static void main (string [] args) {class myKey {integer i; public myKey (Integer i) {this.i = i;}@overRidePublic int hashcode () {return 1;}@overpidePublic Boolean iguales (obj obj) {}}} fechin Hashmap <> (2_500_000,1); for (int i = 0; i <2_000_000; i ++) {mymap.put (new mykey (i), "test"+i);} date end = new Date (); System.out.println ("Duración (ms)"+(end.gettime ()-begin.gettime ());}}}}}}La configuración de mi máquina es Core i5-2500k @ 3.6g, y se tarda más de 45 minutos en ejecutarse bajo Java 8U40 (detuve el proceso después de 45 minutos). Si ejecuto el mismo código, pero uso la función hash como esta:
@OverridePublic int hashcode () {int key = 2097152-1; clave de retorno+2097152*i;}Se tarda 46 segundos en ejecutarlo, ¡lo cual es mucho mejor que antes! La nueva función hash es más razonable que la antigua función hash al procesar particiones hash, por lo que llamar al método put () es más rápido. Si ejecuta el mismo código ahora, pero usa la función hash a continuación, proporciona una mejor partición hash:
@OverridePublic int hashcode () {return i;}¡Ahora solo toma 2 segundos!
Espero que puedas darte cuenta de lo importantes que son las funciones hash. Si ejecuta la misma prueba en Java 7, la primera y la segunda serán peores (porque el método PUT () en Java 7 tiene O (n) complejidad, mientras que la complejidad en Java 8 tiene O (log (n)).
Al usar HashMap, debe encontrar una función hash para las teclas que puedan extender las teclas al cubo más probable. Para hacer esto, debe evitar conflictos hash. Un objeto de cadena es una muy buena clave porque tiene una buena función hash. Integer también es bueno porque su hash es su propio valor.
Cambiar el tamaño de la sobrecarga
Si necesita almacenar una gran cantidad de datos, debe especificar una capacidad inicial al crear un hashmap, que debe estar cerca del tamaño deseado.
Si no hace esto, el mapa usará el tamaño predeterminado, es decir, 16, y el valor de factor carga es 0.75. Las primeras 11 llamadas para poner () el método serán muy rápidos, pero la 12ª (16*0.75) creará una nueva matriz interna con longitud 32 (y la lista/árbol vinculada correspondiente), y la decisión 13 a 22 para poner () el método muy rápido, pero la llamada 23rd (32*0.75) recreará (nuevamente) una nueva matriz interna y la longitud de la matriz estará dindadas. Luego, la operación de cambio de tamaño interna se activará cuando el método PUT () se denomina 48, 96, 192…. Si la cantidad de datos no es grande, el funcionamiento de la reconstrucción de la matriz interna será muy rápida, pero cuando la cantidad de datos es grande, el tiempo dedicado puede oscilar de unos segundos a minutos. Al especificar el tamaño deseado del mapa durante la inicialización, puede evitar el consumo causado por el cambio de tamaño de las operaciones.
Pero también hay un inconveniente aquí: si establece que la matriz sea muy grande, por ejemplo 2^28, pero solo usa 2^26 cubos en la matriz, entonces desperdiciará mucha memoria (aproximadamente 2^30 bytes en este ejemplo).
en conclusión
Para casos de uso simples, no necesita saber cómo funciona HashMap, porque no verá la diferencia entre O (1), O (N) y O (log (N)). Pero siempre es beneficioso comprender el mecanismo detrás de esta estructura de datos utilizada con frecuencia. Además, esta es una pregunta de entrevista típica para las posiciones de desarrolladores de Java.
Para grandes volúmenes de datos, se vuelve muy importante comprender cómo funciona HashMap y comprender la importancia de una función hash para las claves.
Espero que este artículo pueda ayudarlo a comprender profundamente la implementación de HashMap.