Ahora, echemos un vistazo más de cerca a la clase que implementa la interfaz Map - HashMap.

Esta clase es comúnmente utilizada cuando hablamos de mapas. Ya has tenido la oportunidad de trabajar con esta clase y estudiar sus métodos. Pero veamos cómo funciona realmente esta clase.

Primero, necesitamos entender qué es un código hash, ya que se usa internamente en un HashMap.

Código Hash

Cada objeto tiene su propio código hash, que puede obtenerse utilizando el método hashCode() de la clase Object. Veamos un ejemplo:

Como puede ver, el objeto String con los datos "¡Hola Mundo!" tiene un código hash de "-969099747". El método que determina exactamente qué código hash se sobrescribirá en la clase StringLatin1 tiene el siguiente aspecto:

El objeto String se descompone en un array de bytes utilizando el método getBytes(), tras lo cual cada byte se procesa y se añade al código hash. De esta forma, el código hash se convierte en máximamente único, ayudando al programa a identificar este objeto.

Para objetos de clases personalizadas, también puedes sobrescribir el código hash definiendo una forma única para que los objetos obtengan este número. Creemos una clase de prueba Usuario y anulemos el método de código hash para ella.

Nota

El método del código hash pertenece a la clase Object, y todos los objetos heredan de esta clase. Por lo tanto, podemos reemplazar este método en cada objeto. Esto implica programación de bajo nivel, y no profundizaremos en ello aquí.

En la clase User hay 2 atributos que he **utilizado en el método hashCode(). Elegí operaciones aleatorias en el método hashCode() para obtener un número aleatorio máximo, haciéndolo único para cada objeto User.

Este es precisamente el código hash. Ahora vamos a ver cómo se utiliza en un HashMap.

HashMap

Un HashMap puede visualizarse como una matriz de cubos. Un bucket es una lista donde se almacena un elemento. Inicialmente, el HashMap tiene 16 cubos, que es la DEFAULT_INITIAL_CAPACITY.

Cuando ponemos un elemento en el HashMap usando el método put(), el HashMap necesita determinar en qué cubo específico colocar este elemento. Para ello utiliza una fórmula sencilla: keyValue.hashCode() & (n - 1), donde n es el tamaño de la matriz de cubos en el HashMap. &' es una operación bit a bit AND, que también es programación de bajo nivel, así que no entraremos en detalles.

Es importante entender que el HashMap utiliza el código hash del valor de la clave para encontrar el cubo apropiado para ella. Por lo tanto, es crucial crear un código hash único para evitar colisiones.

Colisión

No importa lo único que sea un código hash, puede darse la situación de que el HashMap calcule el mismo cubo para dos elementos. En estos casos, se produce una colisión. En términos simples, una colisión es una situación en la que dos o más elementos terminan en el mismo cubo. Se almacenan allí como una SinglyLinkedList, que implementaste antes.

Veamos un ejemplo:

La colisión no es favorable ya que afecta a la optimización. Si nos fijamos en esta tabla, veremos que en el mejor de los casos, el HashMap tiene complejidad algorítmica constante, mientras que en el peor de los casos, es lineal. Esta complejidad algorítmica lineal surge de colisiones significativas. Por lo tanto, los programadores aconsejan utilizar claves con códigos hash que sean lo más únicos posible para evitar colisiones.

Nota

Si hay muchos elementos en el HashMap, para su optimización, se utiliza un árbol rojo-negro en lugar de un SinglyLinkedList.
Con esta estructura de datos, la complejidad algorítmica es logarítmica, lo que hace que el procesamiento de datos sea mucho más rápido que con la complejidad lineal. No profundizaremos en el tema de los árboles en este curso, ya que es un tema para un curso aparte. Sin embargo, si te interesa, siempre puedes encontrar información sobre ello en Internet.

¿Cómo gestiona HashMap las colisiones?

HashMap también se ocupa de las colisiones a través de la constante redimensión de la matriz de cubos. Cuando el número de elementos alcanza el 75% del tamaño de la matriz de cubos, HashMap desencadena un redimensionamiento duplicando el tamaño de la matriz de cubos. Después, redistribuye los elementos entre los nuevos cubos utilizando el nuevo valor de n en la fórmula.

Por lo tanto, HashMap es una estructura de datos altamente optimizada y se utiliza a menudo como la principal implementación de la interfaz Map.

¿Por qué necesitas saber todo esto?

Esta es una teoría de programación de bajo nivel que es importante porque cuando se trabaja con grandes conjuntos de datos, las estructuras de datos pueden impactar significativamente el rendimiento de la aplicación. Esto sucede cuando estas estructuras de datos son mal utilizadas.

El mal uso de las estructuras de datos ocurre porque los programadores no entienden cómo funcionan estas estructuras de datos. Después de todo, quieres convertirte en un buen programador, ¿verdad?

Además, en las entrevistas suelen hacerse preguntas sobre estructuras de datos.

Si estás interesado en profundizar en cómo funciona HashMap bajo el capó, puedes consultar la documentación de Java en IntelliJ IDEA:

Nota

Por cierto, en el método equals(), el código hash también se utiliza para comparar dos objetos. Si los códigos hash son iguales, significa que los objetos se consideran iguales.