Ayúdanos a dar forma a GoConqr. ¿Qué deberíamos añadir?

Mapa mental

Tablas hash

Clara Rodas Español

Tablas hash

Contenido del mapa

Tablas hash

  1. 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.
  2. 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.
  3. 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.
  4. Utilización de tablas hash

    • Almacenamiento asociativo
    • Recuperación eficiente de la información
  5. 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.

Imágenes y archivos del mapa

  • Tablas hash
  • Tablas hash

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

Escríbenos

¿Sobre qué es tu mensaje?

¿Qué deberíamos añadir?