Red de conocimiento informático - Aprendizaje de programación - La estructura de datos subyacente de HashMap y sus principales parámetros

La estructura de datos subyacente de HashMap y sus principales parámetros

1. La capa inferior se implementa mediante una matriz de lista vinculada

2. ¿Puede almacenar claves y valores vacíos?

?3 Linealmente inseguro

. ?La capacidad inicial es 16, Cada expansión es la potencia n de 2 (operación de bits garantizada)

?5. El factor de carga es 0,75 cuando el número total de elementos en el Mapa supera el 0,75 de la Entrada. matriz, se activará la operación de expansión.

?6. Durante la concurrencia, la operación de colocación de HashMap provocará un bucle infinito, lo que provocará que el uso de la CPU sea cercano a 100

?(1) La estructura de datos implementada en el La parte inferior de HashMap tiene la forma de una lista vinculada de matriz. JDK8 y versiones posteriores adoptan la implementación de un árbol rojo-negro de lista vinculada de matriz, que resuelve el problema de la velocidad de consulta lenta causada por una lista vinculada demasiado larga.

?(2) En pocas palabras, HashMap consta de una matriz y una lista vinculada. La matriz es el cuerpo principal de HashMap. La lista vinculada existe principalmente para resolver conflictos de hash. HashMap obtiene el valor hash realizando una función de perturbación en el HashCode de la clave y luego usa operaciones de bits para determinar la ubicación donde se almacena el elemento actual. Si hay un elemento en la ubicación actual, entonces el valor hash y la clave. Para almacenar el elemento se determina si son iguales, si son iguales, se sobrescribirán directamente. Si no son iguales, el conflicto se resolverá mediante el método de cremallera. Cuando el número total de elementos en el Mapa excede 0,75 de la matriz de Entrada, se activa la operación de expansión para reducir la longitud de la lista vinculada y distribuir los elementos de manera más uniforme.

DEFAULT_INITIAL_CAPACITY: Capacidad de inicialización predeterminada, 1lt;lt; El resultado de la operación de 4 bits es 16, es decir, la capacidad de inicialización predeterminada es 16. Por supuesto, si los datos a almacenar tienen un valor estimado, es mejor mostrar la capacidad inicial al especificar la capacidad para reducir el consumo de eficiencia de expansión causado por la transmisión de datos, etc. Al mismo tiempo, el tamaño de la capacidad debe ser un múltiplo entero de 2.

MAXIMUM_CAPACITY: El valor máximo de la capacidad, 1 <30 bits elevado a la 30ª potencia de 2.

?DEFAULT_LOAD_FACTOR: El factor de carga predeterminado, que el diseñador considera como el mejor valor en función del consumo de tiempo y espacio. El producto de este valor y la capacidad es un valor importante, el umbral, cuyo alcance generará una expansión de aproximadamente el doble del tamaño original.

TREEIFY_THRESHOLD: debido a que después de jdk8, la estructura de almacenamiento subyacente de HashMap se cambió a la estructura de almacenamiento del árbol rojo-negro de lista vinculada de matriz (anteriormente era una lista vinculada de matriz), habrá una colisión en el Al comienzo de los elementos almacenados, la matriz estará colgada en la parte posterior de la lista vinculada. Cuando la longitud de la lista vinculada es mayor que la longitud de este parámetro, la lista vinculada se puede convertir en un árbol rojo-negro. ¿Es posible que haya otro parámetro detrás de la lista vinculada? ¿Por qué es posible que cuando se cumplen ambos parámetros, exista otro parámetro que deba convertirse?

UNTREEIFY_THRESHOLD: Al introducir los parámetros anteriores, sabemos que cuando la longitud es demasiado grande, se puede convertir de una lista vinculada a un árbol rojo-negro, pero no solo se pueden agregar sino también eliminar elementos. , O en otro caso, una matriz Después de expandir la posición de la ranura, los datos de los elementos no son muchos, y usar la estructura de árbol rojo-negro será un gran desperdicio, por lo que en este momento, la estructura de árbol rojo-negro puede se volverá a cambiar a la estructura de lista vinculada. Cuando se vuelva a cambiar, el número de elementos es igual al valor, que es 6. Vuelva a cambiarlo (el número de elementos se refiere al número de espacios en la matriz, no al número de. todos los elementos en el HashMap).

?MIN_TREEIFY_CAPACITY: un estándar para árboles de listas vinculadas. Como se mencionó anteriormente, cuando el número de elementos en la ranura de la matriz es mayor que 8, se puede convertir en un árbol rojo-negro. es posible debido a este valor. Cuando la longitud de la matriz es menor que este valor, se expandirá primero. La ranura de la matriz expandida tiene una alta posibilidad de dispersar los datos en la ranura de la matriz y no es necesario convertir. la estructura de almacenamiento después de la ranura de la matriz. La estructura de la matriz se convertirá después de convertir las ranuras. Por supuesto, si la longitud es mayor que este valor y los datos en la ranura son mayores que 8, se convertirá en un árbol rojo-negro.