Ejemplo hash extensible

Ejemplo de Hashing con espacio de direccionamiento dinámico – Hash Extensible


Supongamos que las claves que se tienen son las que aparecen en la tabla siguiente y que la función de hashdisponible genera la secuencia de bits indicada:

Orden
Clave
Secuencia de bits
1
Perro
0010 …….
2
Gato
0101 …….
3
Lobo
1001 …….
4
Jirafa
1100 …….
5
Gallina
0001 …….
6
Oso1010 …….
7
Burro
1110 …….
8
Vaca
0110 …….
9
Caballo
0111 …….
10
Ave
1111 …….


Supongamos que cada cubeta tiene dos lugares disponible:

Primer Paso
Llegan Gato y Perro, caben enla única cubeta disponible


Segundo Paso
Llega Lobo, produce overflow, se genera una nueva cubeta, se debe duplicar es espacio de direcciones de la tabla, Gato y Perro quedan endireccionada por 0 y lobo en la direccionada por 1.


Tercer Paso
Llega Jirafa y ocupa un lugar en la dirección 1, que no tiene problemas porque hay lugar:

Cuarto Paso
Ante la llegada de unnuevo elemento se producirá overflow en cualquier cubeta, en este caso Gallina llega a la cubeta 0. Como no hay más direcciones disponibles en la tabla se duplica el espacio. Notar que la cubeta 1pasa a estar direccionada por dos celdas de la tabla:

Quinto Paso
Llega Oso, en la cubeta direccionada por 10 o 11 no hay lugar, Se produce overflow pero en este caso no es necesarioaumentar el espacio de direcciones, dado que dos celdas apuntan a igual cubeta.


Sexto Paso
Llegan Burro y vaca y hay lugar para ellos en sus respectivas cubetas



Septimo paso

Caballogenera overflow en la cubeta direccionada por 01, al no haber más espacio libre en la tabla esta duplica sus direcciones. 00 10 11 no sufren alteración y las cubetas referenciadas por estas tendránahora dos celdas de la tabla que las apunten.



Octavo Paso

Llega Ave, que va a la última cubeta, produce overflow, se crea una cubeta nueva sin aumentar el espacio de direcciones:...