Diagnóstico

Búsquedas que fallan tras borrar

Una tabla de direccionamiento abierto funciona hasta que se empiezan a borrar claves. Desde entonces, algunas búsquedas devuelven «no está» para claves presentes. Son siempre claves que colisionaron con otras al insertarse.

Una tabla de direccionamiento abierto funciona hasta que se empiezan a borrar claves. Desde entonces, algunas búsquedas devuelven «no está» para claves presentes, siempre claves que colisionaron al insertarse. ¿Qué hipótesis explica el fallo?La función hash cambió al borrar, y las claves ya no caen en su posición inicialEl borrado no baja el contador de claves y la tabla cree estar más llena de lo que estáEl rehash no recoloca las claves, y las que colisionaron quedan en sus posiciones viejasEl borrado deja posiciones vacías en vez de lápidas y corta el camino de las claves posteriores