Fenómeno
La tabla que se fue llenando
Una tabla hash con 16 cubetas iba rápido con 20 claves. Con 20 000 claves, las mismas 16 cubetas tienen más de mil claves cada una, y buscar vuelve a ser recorrer listas largas.
La solución es tener más cubetas. Pero al cambiar la capacidad, cambia hash(k) mod capacidad.
Piensa antes de seguir: si una clave estaba en la cubeta 5 con capacidad 8, ¿en qué cubeta tendría que estar con capacidad 16?
Escribe tu predicción. Esta reflexión no se califica.