Hash

Solo disponible en BuenasTareas
  • Páginas : 2 (331 palabras )
  • Descarga(s) : 0
  • Publicado : 26 de febrero de 2012
Leer documento completo
Vista previa del texto
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|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]...
tracking img