Saltar al contenido
wandres.dev
Iniciar sesión

Simulación

Recolocar cada clave

La tabla tiene capacidad 8 y estas claves (con hash(k) = k): 5, 13, 21, 2. Todas salvo el 2 están en la cubeta 5. Crece a capacidad 16.

Cada clave va a k mod 16, que puede ser distinto de k mod 8. A esto se le llama rehash: volver a calcular el índice de cada clave con la capacidad nueva.

Rehash de capacidad 8 a capacidad 16A la izquierda, la tabla de capacidad 8: la clave 2 en la cubeta 2 y las claves 5, 13 y 21 en la cubeta 5. A la derecha, la tabla de capacidad 16 después del rehash: 2 sigue en la cubeta 2, 5 y 21 en la cubeta 5, y 13 pasa a la cubeta 13, porque 13 mod 16 = 13.Antes: capacidad 801223455132167Después: capacidad 16012234552167891011121313*1415k mod 16: 5 → 5, 13 → 13, 21 → 5, 2 → 2Solo el 13 cambia de cubeta (antes 13 mod 8 = 5).
La clave 13 cambió de cubeta: la posición depende de la capacidad, por eso hay que recalcular cada índice.
Una tabla de capacidad 8 con hash(k) = k guarda 3, 11, 19, 6 y 14 (las tres primeras en la cubeta 3, las otras dos en la 6). Crece a capacidad 16 con rehash. ¿Cómo quedan las cubetas con claves?