La tabla de hash guarda elementos en lo que se conoce como slot o como buckets, esta tabla
puede tener un número arbitrario de slots y es tarea de la función de hash determinar a qué slot
tiene que ir cierto elemento
Tienes un objeto que consta de una clave y una valor
Lo que quiero hacer es almacenarlo de forma sencilla y poder acceder a este rápidamente
Con un arreglo por ejemplo en una lista de datos podrías buscar algún valor en específico de
forma lineal, sin embargo, imagínate que haya 100000 valores diferentes.
Para esto se utilizan las tablas hash, ya que con esta puedes reducir ese tiempo buscando
exactamente en la casilla donde se encuentra.
Una función hash va a tomar nuestra clave y la va a transformar en un index o un índice, por
ejemplo metes la clave (marcos) y el valor (74489223), la función hash, luego de aplicar un
módulo (que cada quien podrá cambiar a su gusto, pero en este caso es tomando en cuenta el
valor ascii de cada letra del nombre de la persona, que es un sistema de codificación que
asigna un valor numérico único a diferentes caracteres, luego sumándolos todos y aplicándolo
un módulo con el número de espacios del arreglo, de esta manera te dará el valor del índice) te
dará un número, en este caso podría ser 5, entonces cuando yo quiera encontrar el valor de
marcos solo tengo que hacer referencia al índice 5 para poder obtener ese valor y así no tengo
que recorrer todos los datos del arreglo.
Puede haber casos donde tengas el mismo índice para dos valores diferentes, a esto se le
llama colisión, esto se puede solucionar buscando la siguiente casilla disponible (aunque no es
muy óptimo) o también es transformar tu arreglo en un arreglo de listas enlazadas, y lo que
hacemos es simplemente que cada casilla se convierta en una lista enlazada de tal forma que
si nos encontramos con una colisión, se creará una lista enlazada y se guardarán los
elementos uno tras otro y cuando entres a ese índice se hará el recorrido de todos los
elementos que están asociados en esa lista enlazada.
Otra opción sería cambiar tu función hash, básicamente cambiar la forma en la que el programa
decide el índice de cada valor.
Funcionamiento
Una tabla hash contiene:
● Los valores junto con su clave
● Arreglo (lugar donde se irán guardando los valores)
● Una función hash (se encarga de procesar la clave con alguna técnica en específico -
ej. sumar el número de letras en un nombre y multiplicarlo por 3- y transformar la clave
en un índice)
● Slots o bucket (el lugar donde se guardarán los valores, determinado por el índice)
● Índice (indica a qué slot/bucket ira el valor, de esta manera cuando quieras acceder a N
valor podrás utilizar su índice para obtener ese valor y que no sea necesario recorrer
todos los datos del arreglo)
Puede haber casos donde tengas el mismo índice para dos valores diferentes, a esto se le
llama colisión, esto se puede solucionar buscando la siguiente casilla disponible, transformando
tu arreglo en un arreglo de listas enlazadas (entonces cada casilla se convertirá en una lista
enlazada de tal forma que si nos encontramos con una colisión, se creará una lista enlazada y
se guardarán los elementos uno tras otro y cuando entres a ese índice se hará el recorrido de
todos los elementos que están asociados en esa lista enlazada) y por último, también se puede
resolver cambiando tu función hash (básicamente cambiando la forma en la que el programa
decide el índice de cada valor).
AQUI PONES EL EJEMPLO GIRL
Ejemplos
● Búsqueda de palabras clave en motores de búsqueda.
● Almacenamiento de contraseñas de usuarios en aplicaciones web.
● Detección de duplicados en bases de datos.
● Filtrado de spam en correos electrónicos.
● Autenticación de mensajes en sistemas de comunicación segura.