Creo que va a ser más útil si explico los HashMaps en inglés.

¿Qué es un HashMap?

Un HashMap es una estructura de datos que es capaz de asignar ciertas claves a ciertos valores. Las claves y los valores pueden ser cualquier cosa. Por ejemplo, si estuviera haciendo un juego, podría vincular cada nombre de usuario a una lista de amigos, representada por una lista de cadenas.

¿Por qué usar un HashMap?

Los HashMaps son mucho más rápidos para recuperar datos que los arrays y las listas enlazadas. Un array ordenado podría encontrar un valor particular en O(log n) con búsqueda binaria. Sin embargo, un HashMap puede comprobar si contiene una clave particular en O(1). Todas las claves deben ser únicas.

¿Cómo funcionan los HashMaps?

Los HashMaps utilizan un array en el fondo. Cada elemento del array es otra estructura de datos (normalmente una lista enlazada o un árbol de búsqueda binario). El HashMap utiliza una función sobre la clave para determinar dónde colocar el valor de la clave en el array. Por ejemplo, si mi HashMap acepta Strings… las posibles funciones hash pueden ser

A. Return the ASCII value of the first letter.B. Return the sum of the ASCII values of every character in the String.C. Return the ASCII value of the last character in the String.

El valor devuelto determinará el índice en el que el valor va en el array.

¡Pero espera! Hay un problema!

Es posible que el valor devuelto esté fuera de los límites del array. Por lo tanto, debemos modificar el valor devuelto por la longitud del array.

return Math.abs(number%hashMapArray.length);

Colisiones:

¿No es posible que varias claves hagan que la función hash genere el mismo índice? Sí. Por ejemplo, si utilizamos la primera función hash mostrada anteriormente en un mapa hash de cadenas…dos cadenas cualesquiera que empiecen por la misma letra recibirán el mismo índice del array.

Esto se llama colisión.

¿Cómo manejamos las colisiones?

Una técnica para manejar las colisiones se llama encadenamiento. Dado que cada elemento de la matriz es una lista enlazada (o una estructura de datos similar), varias claves que tienen el mismo valor hash se colocarán en la misma lista enlazada o «cubo». Después, el mapa hash es capaz de recuperar valores calculando el código hash con la función hash, y buscando en la lista enlazada particular para ver si contiene un valor con la misma clave.

Hay que escribir una buena función hash para evitar colisiones.

Inventajas del encadenamiento:

La matriz no puede desbordarse

Los datos pueden eliminarse fácilmente

Desventajas del encadenamiento:

Puede sufrir un golpe de rendimiento si los cubos contienen listas enlazadas muy largas.

El número total de entradas al número de cubos se llama factor de carga. Si el factor de carga es demasiado bajo, se desperdicia mucho espacio. Si el factor de carga es demasiado alto, se pierde la ventaja del hashing. Un buen compromiso en el factor de carga es .75