Saltar al contenido

Borrar rompe la búsqueda

Capacidad 8, hash(k) = k. Las posiciones 5, 6 y 7 tienen 5, 13 y 21 (todos querían la 5). Borras el 13 dejando la posición 6 vacía. Después buscas 21. Predice la respuesta antes de mirar el paso 3 de la figura de abajo.

Borrar 13 y buscar 21Tres pasos sobre una tabla de 8 posiciones. Paso 1: las posiciones 5, 6 y 7 guardan 5, 13 y 21. Paso 2: se borra el 13 y la posición 6 queda vacía. Paso 3: buscar 21 empieza en 21 mod 8 = 5; el sondeo 1 ve 5, que no es 21; el sondeo 2 llega a la posición 6, vacía, y la búsqueda se corta con «no está», aunque 21 sigue en la posición 7.Paso 1 de 3: tabla inicial0123455613721Paso 2 de 3: borras 1301234556721Paso 3 de 3: buscas 21012345567211≠ 212vacía21 mod 8 = 5la búsqueda se corta:responde «no está»
En el paso 3 la búsqueda se detiene en la posición 6 y nunca llega a la 7, donde sigue el 21.
Capacidad 8, hash(k) = k. Las posiciones 5, 6 y 7 tienen 5, 13 y 21. Borras el 5 dejando la posición 5 vacía. ¿Qué ocurre al buscar 13 y 21?