Recolocación simple

• El borrado. 
• Al borrar una posición podemos hacer imposible el encontrar otras claves que se insertaron cuando esa posición estaba ocupada, ¿por qué?
• La solución es marcar la posición como borrada, es decir, que las posiciones tengan una etiqueta que pueda valer: "libre", "ocupada" y "borrada"
• Costes.
• El coste de una inserción, búsqueda o borrado depende del número de posiciones que es necesario examinar (número de ensayos o "probes").
• Ver costes de la recolocación lineal.

Recolocación lineal

• Costes.
• La media de número de ensayos en una tabla con n posiciones ocupadas es de 
1/2[1+maxTam²/(maxTam-n)²]
• Cuando n<=1/2 maxTam esta media es constante.
• Problema: Se forman bloques grandes de posiciones de la tabla llenas que están seguidas, cuando se entra en un bloque hay que recorrerlo entero ("primary clustering").

Recolocación cuadrática

• Costes.
 
• Cuando n<= 1/2 maxTam la media del número de ensayos es constante.
• No hay bloques de posiciones llenas.