Mapa mental
Tablas hash

Contenido del mapa
Tablas hash
Definición
- Una tabla Hash es un contenedor asociativo (tipo Diccionario) que permite un almacenamiento y posterior recuperación eficientes de elementos (denominados valores) a partir de otros objetos, llamados claves.
- Una tabla hash se puede ver como un conjunto de entradas. Cada una de estas entradas tiene asociada una clave única, y por lo tanto, diferentes entradas de una misma tabla tendrán diferentes claves. Esto implica, que una clave identifica univocamente a una entrada en una tabla hash.
- Una tabla hash está formada por un array de entradas, que será la estructura que almacene la información, y por una función de dispersión. La función de dispersión permite asociar el elemento almacenado en una entrada con la clave de dicha entrada. Por lo tanto, es un algoritmo crítico para el buen funcionamiento de la estructura.
A considerar
- Cuando se trabaja con tablas hash es frecuente que se produzcan colisiones. Las colisiones se producen cuando para dos elementos de información distintos, la función de dispersión les asigna la misma clave. Como se puede suponer, esta solución se debe arreglar de alguna forma. Para ello las tablas hash cuentan con una función de resolución de colisiones.
- Dos fromas de resolver por colisiones y son:
- Encadenamiento separado:
- Las coliciones se resuelven insertándolas en una lista. De esa forma tendríamos como estructura un vector de listas. Al número medio de claves por lista se le llama factor de carga y habría que intentar que esté próximo a 1.
- Direccionamiento abierto
- Utilizamos un vector como representación y cuando se produzca una colisión la resolvemos reasignándole otro valor hash a la clave hasta que encontremos un hueco.
- Encadenamiento separado:
- Dos fromas de resolver por colisiones y son:
- Cuando se trabaja con tablas hash es frecuente que se produzcan colisiones. Las colisiones se producen cuando para dos elementos de información distintos, la función de dispersión les asigna la misma clave. Como se puede suponer, esta solución se debe arreglar de alguna forma. Para ello las tablas hash cuentan con una función de resolución de colisiones.
Operaciones con tablas hash
- Borrar
- Una vez indicada la clave del objeto a borrar, se procederá a eliminar el valor asociado a dicha clave de la tabla. Esta operación se realiza en tiempo constante, sin importar el tamaño de la tabla o el número de elementos que almacene en ese momento la estructura de datos. Esto es así ya que al ser la tabla una estructura a la que se puede acceder directamente a través de las claves, no es necesario recorrer toda la estructura para localizar un elemento determinado.
- Insertar
- Sobre el elemento que se desea insertar se aplica la función de dispersión. El valor obtenido tras la aplicación de esta función será el índice de la tabla en el que se insertará el nuevo elemento. Veamos este proceso con un ejemplo. Sobre la siguiente tabla hash se desea introducir un nuevo elemento, la cadena azul. Sobre este valor se aplica la función de dispersión, obteniendo el índice 2.
- Borrar
Utilización de tablas hash
- Almacenamiento asociativo
- Recuperación eficiente de la información
REHASHING
- Ventajas
- Permite mantener un reducido factor de carga para que las principales operaciones (insertar, buscar, eliminar) se realicen en tiempo constante.
- esventajas
- Almacenar N datos requiere una Tabla Hash de tamaño M>N, para reducir el número de colisiones.
- No es posible obtener el elemento mínimo ni el máximo con un coste temporal asintótico inferior a lineal con el número de entradas.
- Ventajas
Imágenes y archivos del mapa
Información
- Descripción
- Mapa Mental sobre Tablas hash, creado por Clara Rodas el 22/07/2018.
- Creado por
- Clara Rodas
- Visitas
- 1
- Valoración
Más sobre Tablas hash y dispersión
