Hash Extensible
Páginas: 2 (278 palabras)
Publicado: 12 de octubre de 2012
Hash Extensible
El objetivo del hash extensible es reducir el número de recorridos secuenciales o encadenados, y proveer un área de saturación separada.
Los datos sealmacenan en bloques que pueden contener M elementos, pero se mantiene en memoria un archivo adicional o directorio, a modo de árbol que permite localizar los bloquesbuscados; este directorio solo contiene las direcciones de los bloques donde queremos encontrar los datos en modo de bits.
Al momento de ocurrir una colisión se duplican loscompartimientos o bloques en memoria, y se duplica el directorio que provee la información necesaria para encontrar los bloques, cada bloque tiene un identificador en bits que lepermite a la función hash retornar un valor equivalente a los primeros bits del valor evaluado. Cada valor binario retornado por la función hash debe tener unacorrespondencia en la tabla de memoria.
Para buscar un dato se gana considerablemente eficiencia ya que con este método solo debe aplicarse la función hash al dato y este retorna losbits menos significativos, lo que nos lleva a un bloque de memoria donde necesariamente debe encontrarse el dato, si el dato no se encuentra no existe.
Al momento de haceruna inserción pueden ocurrir 3 cosas:
1 - Que un bloque tenga que ser desdoblado en dos sin afectar al directorio.
2 - Que el directorio se duplique al duplicarse unbloque (añadiendo un
nuevo bit al espacio de direcciones).
3 - Que directorio y bloques asuman el nuevo dato sin modificaciones.
Como consideraciones finales cabe destacarque es importante elegir una buena función de dispersión ya que si está no es eficiente se pueden estar realizando innecesariamente tareas de duplicar los directorios.
El objetivo del hash extensible es reducir el número de recorridos secuenciales o encadenados, y proveer un área de saturación separada.
Los datos sealmacenan en bloques que pueden contener M elementos, pero se mantiene en memoria un archivo adicional o directorio, a modo de árbol que permite localizar los bloquesbuscados; este directorio solo contiene las direcciones de los bloques donde queremos encontrar los datos en modo de bits.
Al momento de ocurrir una colisión se duplican loscompartimientos o bloques en memoria, y se duplica el directorio que provee la información necesaria para encontrar los bloques, cada bloque tiene un identificador en bits que lepermite a la función hash retornar un valor equivalente a los primeros bits del valor evaluado. Cada valor binario retornado por la función hash debe tener unacorrespondencia en la tabla de memoria.
Para buscar un dato se gana considerablemente eficiencia ya que con este método solo debe aplicarse la función hash al dato y este retorna losbits menos significativos, lo que nos lleva a un bloque de memoria donde necesariamente debe encontrarse el dato, si el dato no se encuentra no existe.
Al momento de haceruna inserción pueden ocurrir 3 cosas:
1 - Que un bloque tenga que ser desdoblado en dos sin afectar al directorio.
2 - Que el directorio se duplique al duplicarse unbloque (añadiendo un
nuevo bit al espacio de direcciones).
3 - Que directorio y bloques asuman el nuevo dato sin modificaciones.
Como consideraciones finales cabe destacarque es importante elegir una buena función de dispersión ya que si está no es eficiente se pueden estar realizando innecesariamente tareas de duplicar los directorios.
Leer documento completo
Regístrate para leer el documento completo.