UC3M

Grado en Ing. Telemática/Sist. Audiovisuales/Sist. de Comunicaciones

Arquitectura de Sistemas

Septiembre 2017 - Enero 2018

7.3. Tablas hash
Anterior Capítulo 7. Tablas Hash  Siguiente

7.3. Tablas hash

Las tablas hash son uno de los mecanismos más utilizados en el desarrollo de aplicaciones (haz una búsqueda en internet del término hash table y mira número de enlaces que se devuelven). Existen múltiples librerías en casi todos los lenguajes de programación que proporcionan implementaciones muy eficientes de estas tablas (por ejemplo la clase java.util.Hashtable de las librerías del lenguaje Java).

La implementación de una tabla hash está basada en los siguientes elementos:

  • Una tabla de un tamaño razonable para almacenar los pares (clave, valor).

  • Una función “hash” que recibe la clave y devuelve un índice para acceder a una posición de la tabla.

  • Un procedimiento para tratar los casos en los que la función anterior devuelve el mismo índice para dos claves distintas. Esta situación se conoce con el nombre de colisión.

Las posibles implementaciones de cada uno de estos tres elementos se traducen en una infinidad de formas de implementar una tabla hash. A continuación se detalla una solución concreta para el problema de las colisiones.

Responde a las siguientes preguntas para ver si has entendido lo que se explica en este documento:

  1. Una función hash es:

    • Una función que, dada una clave de un elemento, devuelve el índice de la tabla hash donde se encuentra almacenado (o donde hay que almacenar) dicho elemento.

    • Una función que, dada una clave de un elemento, devuelve el elemento almacenado en la tabla hash.

    • Una función que, dado un elemento, devuelve su clave en la tabla hash.

  2. En una tabla hash una colisión se produce cuando:

    • En las tablas hash, si la función hash está bien diseñada no pueden ocurrir.

    • No hay espacio suficiente para guardar todos los elementos en la tabla hash. En este caso, la tabla debe redimensionarse.

    • La función hash devuelve el mismo índice para dos o más claves diferentes.

Anterior Subir Siguiente
7.2. Posibles implementaciones  Inicio 7.4. Gestión de colisiones mediante listas encadenadas
© Universidad Carlos III de Madrid | Licencia Creative Commons