Pregunta 2 · Programació II UDL 2022

Tema: Tablas hash · Del examen Examen Segundo Parcial Enero 2022 (2022)

Enunciado

Pregunta 2 (3,5 puntos). Tablas hash con dispersión abierta y cerrada

Se dispone de dos tablas hash inicialmente vacías (denominadas tabla 1 y tabla 2) de dimensión M=10M = 10 (posiciones de 0 a 9) tal y como se muestra en la Figura 2-a.

Se debe simular paso a paso la inserción y eliminación de elementos aplicando la siguiente secuencia de 10 operaciones de parejas (clave, valor):

Insertar (100, 1000)

Insertar (10, 100)

Insertar (31, 310)

Insertar (55, 550)

Eliminar 10

Insertar (5, 50)

Eliminar 31

Insertar (1000, 10000)

Insertar (100, 90)

Insertar (320, 3200)

Función de dispersión común:

h(k)=((∑dıˊgitos de k)+k+1)(mod10)h(k) = \left(\left(\sum \text{dígitos de } k\right) + k + 1\right) \pmod{10}

Ejemplo: h(43)=((4+3)+43+1)(mod10)=51(mod10)=1h(43) = ((4 + 3) + 43 + 1) \pmod{10} = 51 \pmod{10} = 1.

Aplica dicha secuencia y describe de forma razonada la situación que se produce en cada instante, detallando el estado de ambas estructuras según sus particularidades y explicando brevemente cada casuística nueva que acontezca (primera colisión, eliminación lógica vs física, sobreescritura de clave existente, etc.):

a)

Tabla 1 (dispersión abierta): Se representa mediante un array de listas enlazadas que almacenan pares (clave, valor). En caso de colisión, los nuevos elementos se añaden por la cabecera (o final, según corresponda de forma consistente). Si una clave ya existe, se actualiza su valor asociado.

b)

Tabla 2 (dispersión cerrada): Vector de tripletas (clave, valor, marca) (marcas: libre, ocupado, borrado) con resolución cuadrática definida por:

hi(k)=(h(k)+i2+1)(mod10)para i=0,1,2,…h_i(k) = (h(k) + i^2 + 1) \pmod{10} \quad \text{para } i = 0, 1, 2, \dots

Enunciado: Pregunta 2 · Programació II UDL 2022

Solución

Según los criterios oficiales de corrección

a) Tabla 1 (dispersión abierta): simulación paso a paso y estado final

Solución: Cálculo previo de hash primario: - k=100k = 100: h(100)=(1+100+1)(mod10)=102(mod10)=2h(100) = (1 + 100 + 1) \pmod{10} = 102 \pmod{10} = 2 - k=10k = 10: h(10)=(1+10+1)(mod10)=12(mod10)=2h(10) = (1 + 10 + 1) \pmod{10} = 12 \pmod{10} = 2 - k=31k = 31: h(31)=(4+31+1)(mod10)=36(mod10)=6h(31) = (4 + 31 + 1) \pmod{10} = 36 \pmod{10} = 6 - k=55k = 55: h(55)=(10+55+1)(mod10)=66(mod10)=6h(55) = (10 + 55 + 1) \pmod{10} = 66 \pmod{10} = 6 - k=5k = 5: h(5)=(5+5+1)(mod10)=11(mod10)=1h(5) = (5 + 5 + 1) \pmod{10} = 11 \pmod{10} = 1 - k=1000k = 1000: h(1000)=(1+1000+1)(mod10)=1002(mod10)=2h(1000) = (1 + 1000 + 1) \pmod{10} = 1002 \pmod{10} = 2 - k=320k = 320: h(320)=(5+320+1)(mod10)=326(mod10)=6h(320) = (5 + 320 + 1) \pmod{10} = 326 \pmod{10} = 6 Secuencia paso a paso: - Op 1: Inserta (100, 1000) en posición 2. - Op 2: Inserta (10, 100) en posición 2 (colisión: se encadena a la lista de la cubeta 2). - Op 3: Inserta (31, 310) en posición 6. - Op 4: Inserta (55, 550) en posición 6 (colisión: se encadena a la lista de la cubeta 6). - Op 5: Eliminar 10: se desenlaza físicamente de la lista de la posición 2. - Op 6: Inserta (5, 50) en posición 1. - Op 7: Eliminar 31: se desenlaza físicamente de la cubeta 6. - Op 8: Inserta (1000, 10000) en posición 2 (se enlaza en la cubeta 2). - Op 9: Inserta (100, 90) en posición 2: la clave 100 ya existe, se actualiza su valor asociado de 1000 a 90. - Op 10: Inserta (320, 3200) en posición 6 (se añade a la lista tras 55). Estado final: - Índice 1: [5, 50] - Índice 2: [100, 90] → [1000, 10000] - Índice 6: [55, 550] → [320, 3200] - Resto de índices (0, 3, 4, 5, 7, 8, 9): vacía.

b) Tabla 2 (dispersión cerrada): simulación paso a paso y estado final

Solución: Fórmula: hi(k)=(h(k)+i2+1)(mod10)h_i(k) = (h(k) + i^2 + 1) \pmod{10} - Op 1: Clave 100. i=0:h0(100)=(2+0+1)(mod10)=3i=0: h_0(100) = (2+0+1) \pmod{10} = 3 (Libre →\rightarrow Ocupado con (100, 1000)). - Op 2: Clave 10. i=0:h0(10)=3i=0: h_0(10) = 3 (Ocupada). i=1:h1(10)=(2+1+1)(mod10)=4i=1: h_1(10) = (2+1+1) \pmod{10} = 4 (Libre →\rightarrow Ocupado con (10, 100)). - Op 3: Clave 31. i=0:h0(31)=(6+0+1)(mod10)=7i=0: h_0(31) = (6+0+1) \pmod{10} = 7 (Libre →\rightarrow Ocupado con (31, 310)). - Op 4: Clave 55. i=0:h0(55)=7i=0: h_0(55) = 7 (Ocupada). i=1:h1(55)=(6+1+1)(mod10)=8i=1: h_1(55) = (6+1+1) \pmod{10} = 8 (Libre →\rightarrow Ocupado con (55, 550)). - Op 5: Eliminar 10. Se busca (h0(10)=3h_0(10)=3, h1(10)=4h_1(10)=4). Se marca la celda 4 como Borrado. - Op 6: Clave 5. i=0:h0(5)=(1+0+1)(mod10)=2i=0: h_0(5) = (1+0+1) \pmod{10} = 2 (Libre →\rightarrow Ocupado con (5, 50)). - Op 7: Eliminar 31. h0(31)=7h_0(31)=7. Se marca la celda 7 como Borrado. - Op 8: Clave 1000. h0(1000)=3h_0(1000)=3 (ocupada por 100). i=1:h1(1000)=4i=1: h_1(1000)=4 (marcada como Borrado →\rightarrow se reutiliza: Ocupado con (1000, 10000)). - Op 9: Clave 100. En h0(100)=3h_0(100)=3 se encuentra la clave. Se actualiza el valor: (100, 90, Ocupado). - Op 10: Clave 320. i=0:h0(320)=(6+0+1)(mod10)=7i=0: h_0(320) = (6+0+1) \pmod{10} = 7 (marcada como Borrado →\rightarrow se reutiliza: Ocupado con (320, 3200)). Estado final: - Posición 2: Clave 5, Valor 50, Ocupado - Posición 3: Clave 100, Valor 90, Ocupado - Posición 4: Clave 1000, Valor 10000, Ocupado - Posición 7: Clave 320, Valor 3200, Ocupado - Posición 8: Clave 55, Valor 550, Ocupado - Posiciones 0, 1, 5, 6, 9: Libres.

La explicación paso a paso, hecha con IA, es Premium. Premium

Resuélvelo aquí mismo: corrección automática, pistas y solución paso a paso.