Hash
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|Oso |1010 ……. |
|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, cabenen la única cubeta disponible
[pic]
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.
[pic]
Tercer Paso
Llega Jirafa y ocupa un lugar en la dirección 1, que no tiene problemas porque hay lugar:
[pic]
Cuarto Paso
Ante lallegada de un nuevo 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 quela cubeta 1 pasa a estar direccionada por dos celdas de la tabla:
[pic]
Quinto Paso
Llega Oso, en la cubeta direccionada por 10 o 11 no hay lugar, Se produce overflow pero en este caso no esnecesario aumentar el espacio de direcciones, dado que dos celdas apuntan a igual cubeta.
[pic]
Sexto Paso
Llegan Burro y vaca y hay lugar para ellos en sus respectivas cubetas
[pic]...
Regístrate para leer el documento completo.