Principio de implementación de HashMap
Lo siguiente es mi propio entendimiento. Las discusiones son bienvenidas. No es fácil escribir.
La estructura de datos en HashMap es una tabla hash, también llamada tabla hash. Aquí presentaré brevemente las tablas hash. Antes de eso, debemos revisar las ventajas y desventajas de las matrices y las listas vinculadas.
Las ventajas y desventajas de las matrices y las listas enlazadas dependen de sus respectivos métodos de almacenamiento en la memoria, es decir, almacenamiento secuencial directo o almacenamiento encadenado. Tanto las matrices como las listas enlazadas tienen desventajas obvias. En los negocios reales, a menudo esperamos que la estructura de datos tenga un buen rendimiento de direccionamiento, eliminación e inserción. Hashtable es una estructura que combina inteligentemente las ventajas de las matrices y las listas enlazadas y debilita (en lugar de eliminar por completo) sus desventajas.
Una tabla hash asigna una clave a un subíndice de una matriz. Al acceder, el índice se obtiene a través de la clave y luego se accede directamente a través del índice. Es extremadamente rápido y la asignación de claves a subíndices requiere el uso de una función hash, también conocida como función hash. Hablando de funciones hash, es posible que alguien haya pensado en cómo asignar claves a subíndices de matrices.
Las siguientes dos funciones se utilizan para calcular los subíndices en el gráfico:
Vale la pena señalar que los subíndices no se obtienen directamente mediante la función hash y deben calcularse mediante el índice. () procesamiento.
Ps: en una tabla hash, la cuadrícula de la matriz se llama depósito y el subíndice se llama número de depósito. El depósito puede contener un par clave-valor. Para facilitar la comprensión, estos dos términos no se utilizarán en el futuro.
La siguiente es una descripción relacionada con una colisión de hash:
La siguiente es una descripción de un conflicto de subíndices:
Mucha gente piensa que las colisiones de valores hash y Las colisiones de subíndices son El conflicto es una cosa, pero no lo es. Su relación correcta es la siguiente: si el código hash entra en conflicto, los subíndices deben entrar en conflicto; cuando los subíndices entran en conflicto, el código hash no necesariamente entra en conflicto.
Como se mencionó anteriormente, antes de jdk1.8, la implementación de HashMap era tabla hash = lista enlazada de matriz, pero hasta ahora no hemos visto la función de lista enlazada. De hecho, el propósito de introducir listas vinculadas en HashMap es resolver conflictos de subíndices.
La siguiente figura es la tabla hash después de introducir la lista vinculada:
Como se muestra en la figura anterior, la línea vertical de la izquierda es una matriz de tamaño 16, que almacena la nodo principal de la lista enlazada. Sabemos que el nodo principal con la lista vinculada puede acceder a toda la lista vinculada, por lo que pensamos que cada subíndice de esta matriz almacena una lista vinculada. Específicamente, si se encuentra un conflicto de subíndices, el nodo insertado se agrega al nodo anterior en forma de lista vinculada.
Este método de utilizar listas enlazadas para resolver conflictos se llama método cremallera (también conocido como método de direcciones en cadena). HashMap utiliza el método de cremallera, que es una solución posterior a la colisión.
P: Al utilizar el método de la cremallera, ¿no tienes que preocuparte por los conflictos?
Respuesta: ¡En realidad no! Debido a que los nodos en conflicto se seguirán agregando a la lista vinculada, una gran cantidad de conflictos hará que una única lista vinculada sea demasiado larga, lo que reducirá el rendimiento de la consulta. Por lo tanto, una buena implementación de la tabla hash debería reducir la posibilidad de colisiones desde la fuente. La probabilidad de colisión está directamente relacionada con la coherencia del valor de retorno de la función hash. Cuanto más uniformes sean los hashes, es menos probable que se produzcan colisiones. Para que los valores hash sean más uniformes, HashMap implementa el método hash () por separado.
Lo anterior es la estructura de almacenamiento de la tabla hash, pero hay otras cosas a las que se debe prestar atención cuando se aplica a HashMap, que se explicarán en detalle aquí.
Ahora que conocemos la estructura de almacenamiento de la tabla hash, las personas cuidadosas deberían haber descubierto un problema: la longitud de la matriz en Java es fija. Independientemente de si la función hash es uniforme o no, a medida que aumentan los datos insertados en la tabla hash, la longitud de la lista vinculada seguirá aumentando mientras la longitud de la matriz permanece sin cambios. Esto conducirá a la desventaja de un rendimiento deficiente de las consultas de la lista vinculada en la tabla hash, lo que hará que la tabla hash pierda su significado original. Para resolver este problema, HashMap introduce factores de expansión y carga.
Los siguientes son algunos conceptos y explicaciones relacionados con la expansión:
Ps: el subíndice debe recalcularse para expansión, expansión y expansión, porque el cálculo del subíndice está relacionado con la matriz longitud, si la longitud cambia, se debe volver a calcular el subíndice.
En las versiones 1.8 y superiores de jdk, HashMap introduce árboles rojo-negro.
Introduce árboles rojo-negro para reemplazar las listas enlazadas. Como se mencionó anteriormente, si hay demasiados conflictos, la lista vinculada será demasiado larga y se reducirá el rendimiento de la consulta. Las funciones hash unificadas pueden mitigar eficazmente las colisiones excesivas, pero no pueden evitarlas por completo. Por lo tanto, HashMap agregó otra solución. Al agregar nodos a la lista vinculada, si la longitud de la lista vinculada llega a 8, la lista vinculada se convertirá en un árbol rojo-negro, mejorando así el rendimiento de la consulta.