4- Tablas Hash4.5 Recolocación

Resolución de Colisiones por Recolocación
  • Recolocación simple
  • Recolocación lineal
  • Recolocación cuadrática

Recolocación simple

Sea h la función hash. La recolocación consiste en:
  • Al insertar una clave c, si la posición h(c) está libre, se miran las posiciones h(c)+1 (mod maxTam), h(c)+2 (mod maxTam), h(c)+3 (mod maxTam), ... hasta encontrar una libre, en la que se inserta c.
  • Para buscar una clave c se repite el mismo proceso, se busca en h(c), h(c)+1, etc hasta encontrarla o llegar a una posición vacía, en este segundo caso la clave buscada no está.
  • ¿Qué problemas tiene el borrado?
  • Coste de las operaciones.

Recolocación lineal

Sea a un número fijo entre 1 y maxTam-1.
Las posiciones de recolocación son h(c), h(c)+a (mod maxTam), h(c)+2a (mod maxTam), etc. 
  • Problema: puede no encontrarse una posición libre. Solución: elegir a primo con maxTam.
  • Costes.

Recolocación cuadrática

Las posiciones de recolocación son h(c), h(c)+1 (mod maxTam), h(c)+4 (mod maxTam), h(c)+9 (mod maxTam), ... h(c)+i2 (mod maxTam), etc. 
  • Problema: puede no encontrarse una posición libre. Pero esto sólo ocurre si la tabla está casi llena (se evita haciendo n<=1/2 maxTam).
  • Costes.
 


  E.Mayordomo y K. Urzelai 
elvira at posta.unizar.es
karmelo at posta.unizar.es
Fecha de actualización: 4-9-01