Universidad Carlos III de Madrid

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

Arquitectura de Sistemas

Septiembre 2012 - Enero 2013

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.

Figura 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.