Coste

La longitud media de las cadenas

Con encadenamiento, el trabajo de buscar es la longitud de la cadena de la cubeta.

Una tabla con 500 cubetas guarda 4000 claves bien repartidas. ¿Cuántas claves tiene una cubeta en promedio? Si la función hash las mandara todas a la misma cubeta, ¿cuántas compararía buscar una clave ausente?Claves por cubeta en promedioComparaciones en el peor caso