El principio de Hashpmap y cómo HashMap garantiza la unicidad de las claves

En el lenguaje de programación Java, existen dos estructuras más básicas, una es una matriz y la otra es un puntero simulado (referencia). Todas las estructuras de datos se pueden construir utilizando estas dos estructuras básicas. sin excepción. HashMap es en realidad una estructura de datos de "hash de lista vinculada", que es una combinación de una matriz y una lista vinculada. HashMap es en realidad una estructura de datos de "hash de lista vinculada", que es una combinación de una matriz y una lista vinculada. La función de HashMap es encontrar rápidamente "valor" por "clave". Analicemos el proceso básico del almacenamiento de datos de HashMap:

1. Al llamar a put(key, value), primero obtenga el código hash de la clave, int?hash?=?key.hashCode( );

2. Luego opere el código hash para obtener int?h.

hash?(hash?>>>?20)?^?(hash?>>>?12);?

int?h?=?(hash?>> >?7)?^?(hash?>>>?4);?

¿Por qué se hacen estos cálculos matemáticos? Ésta es la belleza de HashMap. Veamos un ejemplo: el número decimal 32768 (1000?0000?0000?0000 binario), el resultado después de la operación de fórmula anterior es 35080 (1000?1001?0000?1000 binario). ¿Ves lo que quiero decir? Quizás esto todavía no diga nada. Tome otro número 61440 (binario 1111?0000?0000?0000), y el resultado de la operación es 65263 (binario 1111?1110?1110?1111). El propósito es hacer que "1" sea más uniforme. La intención original del hash es tomar tantos como sea posible y el resultado es 35080 (1000?1001?0000?1000 binario). La intención del hash es ser lo más uniforme posible. ¿Cuál es el punto? Por favor vea el paso 3.

3. Después de obtener h, h y la capacidad de carga de HashMap (la longitud de capacidad de carga predeterminada de HashMap es 16, que se puede alargar automáticamente. También puede especificar una longitud al crear un HashMap. Esta carga La capacidad es la anterior a la longitud de la matriz descrita). Realice una operación de suma lógica, es decir: ?(longitud-1), de modo que el resultado sea un número positivo menor que la longitud. A este valor lo llamamos índice. De hecho, este índice es la posición en la matriz donde se insertará el valor. La importancia del algoritmo del segundo paso es que esperamos obtener un índice uniforme. Esta es una mejora con respecto a HashTable. El algoritmo HashTable simplemente divide el código hash del valor clave por la longitud para obtener el resto, que es el porcentaje. valor hash a la longitud, lo que puede dar como resultado una distribución desigual del índice. Otra cosa a tener en cuenta es que la clave de HashMap puede estar vacía y su valor se coloca en la primera posición de la matriz.

4. Usamos tabla[índice] para indicar que se ha encontrado el elemento que necesita ser almacenado. Primero determine si hay un elemento en esta posición (¿el elemento es una clase definida en la entidad HashMap? Su estructura básica contiene tres clases, clave, valor y la siguiente apunta a la siguiente Entidad. Si no, cree una Entidad <). El objeto K, V> se inserta en la posición en la tabla [índice], y la inserción se completa, si hay una, recorra la lista vinculada una por una para ver si hay una clave existente, y si es así; , Úselo El nuevo valor se inserta en la clave, la clave no se usará, pero se usará la clave. Si es así, reemplace el valor anterior con el nuevo valor; si es así, recorra la lista vinculada una por una para ver si hay claves existentes. Reemplace el valor anterior; de lo contrario, inserte la entidad en la tabla [índice], asigne la entidad original en la tabla [índice] a la siguiente de la nueva entidad y la inserción finalizará.