Tablas hash: funciones hash y manejo de colisiones

Enunciado

Se tiene una tabla hash de tamano $m = 7$ (posiciones 0 a 6) con la siguiente funcion hash:

$h(k) = k \mod 7$

Se desean insertar las siguientes claves en orden:

$[15, 22, 8, 3, 37, 10, 29]$

Parte 1: Encadenamiento (Chaining)

(a) Inserte todas las claves usando encadenamiento (cada posicion de la tabla contiene una lista enlazada). Muestre el estado final de la tabla, indicando la lista enlazada en cada posicion.

(b) Cual es el factor de carga ($\alpha = n/m$) de la tabla?

(c) Cuantas comparaciones se necesitan en promedio para buscar una clave existente en esta tabla?

Parte 2: Direccionamiento abierto (Open Addressing)

(d) Inserte las mismas claves usando sondeo lineal (linear probing): si la posicion $h(k)$ esta ocupada, se prueba $h(k)+1$, $h(k)+2$, etc. (modulo $m$). Muestre el estado de la tabla despues de cada insercion.

(e) Inserte las mismas claves usando sondeo cuadratico: si la posicion $h(k)$ esta ocupada, se prueba $h(k)+1^2$, $h(k)+2^2$, $h(k)+3^2$, etc. (modulo $m$). Muestre el estado de la tabla despues de cada insercion. Se produce algun problema?

Parte 3: Analisis

(f) Compare las tres estrategias de resolucion de colisiones en terminos de:

• Complejidad de busqueda en el peor caso.
• Uso de memoria.
• Fenomeno de agrupamiento (clustering).

(g) Si el factor de carga supera 0.75, que se recomienda hacer con la tabla? Describa el proceso de rehashing y cual seria el nuevo tamano de tabla recomendado.