7.4.
Gestión de colisiones mediante listas
encadenadas
La solución propuesta para implementar la tabla hash combina
la estructura de tabla con la de lista encadenada. Cada posición de la tabla
no almacena un único elemento sino la cabeza de una lista encadenada que a
su vez contiene todos aquellos elementos cuya función de hash ha devuelto
idéntico resultado. Una posición de la tabla en la que no se haya insertado
ningún elemento, contiene un puntero a NULL. La siguiente figura
muestra una tabla de tamaño
n y los elementos almacenados en las posiciones 0, 1, 2,
n-2 y n-1.
Fíjate que diferentes posiciones de la tabla pueden tener
listas de diferente longitud, o incluso vacías. Dada una clave, el proceso
de búsqueda consiste en calcular primero su índice mediante la función de
hash, y a continuación buscar esa clave en la lista de colisiones.
