4- Tablas Hash4.4 Encadenamiento Resolución de Colisiones por Encadenamiento. Eficiencia.
Suponemos que: Tenemos una tabla de tamaño maxTam e insertamos n claves. La función hash distribuye uniformemente, luego tendremos unos n/maxTam elementos en cada posición de la tabla. La función hash se puede calcular en tiempo constante. Insertar un elemento requerirá calcular la función hash e insertar al principio de la lista. Buscar y borrar requerirá calcular la función hash y recorrer una lista, luego serán las operaciones más costosas. En el caso peor la búsqueda costará n/maxTam En media la búsqueda costará: (1+2+3+...+n/maxTam)/(n/maxTam) = ((n/maxTam)+1)/2 = (n+maxTam)/(2maxTam) Si n<=maxTam la búsqueda cuesta tiempo constante en media. Si n es grande el coste aumenta mucho.
E.Mayordomo y K. Urzelai  elvira at posta.unizar.es karmelo at posta.unizar.es Fecha de actualización: 4-9-01