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:
Una función hash
es:
En una tabla hash
una colisión se produce cuando: