Mapeo de Claves
Hashing
(Organización y Manejo de Archivos)
2005
MAPEO DE CLAVES.
Como ya se indicó los registros de un archivo pueden quedar
ordenados de acuerdo al valor de algún campo o grupo de campos,
denominados clave o llave.
ACCESO DIRECTO
El acceso directo implica necesariamente un direccionamiento
(permitir la identificación de un registro específico que se encuentra
en el interior de un archivo).
Existen 3 técnicas de direccionamiento fundamentales utilizadas
para mapear claves (asociar una dirección con el registro en
cuestión).
Sea R una función de mapeo:
R (valor de la clave)  Dirección física
TÉCNICAS DE MAPEO DIRECTAS
La técnica de mapeo más simple para traducir una clave a una
dirección de almacenamiento es el mapeo directo (técnica no muy
utilizada)
DIRECCIONAMIENTO ABSOLUTO
Para esto basta con tener
Valor_de_la_clave = Dirección
El valor de la clave entregado por el usuario es igual a la dirección
real del registro.
Ventajas
La función de mapeo R es sencilla.
No se requiere de tiempo de proceso para determinar la localidad
del registro en el almacenamiento secundario.
Desventajas
Las consideraciones lógicas y físicas no son independientes del
direccionamiento absoluto, el usuario debe conocer exactamente
como están almacenados los registros.
Las direcciones absolutas dependen de los dispositivos.
Las direcciones absolutas dependen del espacio direccionable.
DIRECCIONAMIENTO RELATIVO
Es un método sencillo que tiene las mismas ventajas que el
direccionamiento absoluto y que reduce el número de desventajas.
Valor_de_la_Clave = Dirección Relativa
La dirección relativa de un registro en un archivo es el número
ordinal del registro dentro del archivo.
Un archivo con espacio para N registros tiene direcciones relativas
que están en el conjunto { 1, 2, 3, …, N-1, N}.
El i-esimo registro tiene dirección relativa i.
VENTAJAS
La función de mapeo R es sencilla.
No se requiere de tiempo de proceso para determinar la localidad
del registro en el almacenamiento secundario.(Generalmente es
transparente para el usuario).
En el direccionamiento relativo la función de mapeo R corresponde
a:
Dirección_física = Dirección_base + Tamaño_registro(Clave-1)
Las direcciones relativas no dependen tanto del dispositivo como
las direcciones absolutas, lo cual elimina una de las desventajas
mencionadas.
Sin embargo las direcciones relativas dependen del espacio de
direcciones.
Algunos valores naturales de clave no son apropiados para usarse
como dirección relativa (Ej. Nombres, RUT).
¿Por que no es bueno el RUT para este tipo de
direccionamiento?
¿Qué pasaría en una empresa con 2000 empleados?
¿Qué espacio de direcciones debe reservarse?
¿Cual es el porcentaje del archivo vacío?
¿Por que no es bueno el RUT para este tipo de direccionamiento?
¿Qué pasaría en una empresa con 2000 empleados?
¿Qué espacio de direcciones debe reservarse?
¿Cual es el porcentaje del archivo vacío?
Un enfoque para resolver el problema del espacio de clave es
identificar o inventar una clave cuyo rango de valores este altamente
poblado.
Ejemplo: Supongamos un archivo que contiene el inventario de partes
de un computador.
¿Plantee una posible solución.?
TECNICAS DE BUSQUEDA EN UN DIRECTORIO
Este enfoque utilizado de manera frecuente, toma ventaja de los
beneficios del mapeo directo mientras que elimina sus desventajas,
pero introduce dos nuevos costos.
La idea básica del método de búsqueda en directorio es la de tener
una tabla o directorio de valores de clave: pares de direcciones (o
pares de direcciones relativas).
Para encontrar un registro en un archivo relativo se localiza su valor
de clave en el directorio y después, la dirección indicada para
encontrar el registro almacenado.
En su forma más sencilla el directorio es creado como un arreglo de
valores de clave y registro de direcciones. Las entradas del
directorio están ordenadas por el valor de la clave, de tal forma que
pueda usarse una búsqueda binaria para localizar la clave objetivo.
Generalmente las entradas al archivo relativo no están en orden
consecutivo.
ALMACENAMIENTO DE REGISTROS
Recuperar un registro es bastante directo usando el esquema de
búsqueda en directorio.
La pregunta a responder es ¿Cómo se almacenan los registros en
este esquema?
Una manera es asignar una dirección a cada valor posible de la
clave, de esta manera el directorio inicialmente esta completo. Las
direcciones pueden asignarse utilizando cualquier función.
Un método mas usual es el de determinar si existe espacio libre
para un registro al momento de almacenarlo. El registro puede ser
ubicado tan cerca del inicio del archivo como sea posible, o tan
cerca del registro con un valor de clave tan similar como sea
posible, o al azar.
TECNICAS DE CÁLCULO DE DIRECCIONES.
Otro Método para implementar:
R (Valor de la clave)  Dirección
El cual realiza un cálculo sobre el valor de la clave, cuyo resultado
sea una dirección relativa.
La idea básica del cálculo de direcciones consiste en aplicar la
función que traduce un conjunto relativamente grande de posibles
valores de la clave a un rango relativamente pequeño de valores de
direcciones relativas.
(Recordar: Desventaja del direccionamiento relativo es que debe
asignar espacio para acomodar el rango completo de valores de la
clave, independientemente de cuantos serán usados realmente.)
El problema potencial encontrado en este proceso, es que la
función antes mencionada no puede ser uno a uno, las direcciones
calculadas pueden no ser únicas:
R(K1) = R(K2) pero K1 <> K2
A esto se le denomina colisión.
K1 y K2 se llaman sinónimos.
En este tipo de técnicas se deben resolver dos problemas:
Cálculo de direcciones
Colisiones
A las técnicas de cálculo de direcciones también se las conoce
como:
•Técnicas de almacenamiento disperso.
•Técnicas aleatorias.
•Método de transformación de clave por dirección.
•Técnicas de direccionamiento directo.
•Método de tabla Hash.
•Método Hashing.
Nosotros utilizaremos el término de Hashing.
La función que hace la transformación de la clave en una dirección
se denomina función Hash.
Ventajas de utilizar Hashing.
1) Se pueden utilizar valores “naturales” para la clave.
2) La independencia lógica y física es lograda, puesto que los
valores de las claves son independientes del espacio de
direcciones. (¿Qué ocurre si el archivo relativo es reorganizado?
¿Con la función y con la clave?).
Costos extras asumidos al utilizar Hashing son:
1) Se requiere tiempo de procesamiento para la función hash.
2) Se requiere tiempo de procesamiento y accesos de I/O para
solucionar las colisiones.
El objetivo fundamental de una función hash es generar pocas
colisiones.
El conjunto de sinónimos corresponde a una clase de equivalencia.
Una buena función hash tiene muchas clases de equivalencia y con
una pequeña cantidad de elementos en cada una de ellas.
Debe ser computacionalmente simple.
Si (La clave está en el directorio) entonces
Aplicar función hash a la clave del registro
Resolver colisiones, si es necesario
Almacenar registros
Agregar al directorio la clave del registro y
la dirección.
Fin Si
Beneficios
1) Evita el recalculo para registros anteriores.
2) Evita las soluciones de colisiones para los registros anteriores.
Costos
1) Almacenamiento del directorio
2) Mantención del directorio.
La eficiencia de una función hash dependen de:
1) Distribución de los valores de la clave que realmente se usan.
2) Numero de valores de la clave que realmente están en uso con
respecto al tamaño del espacio de direcciones.
3) El numero de registros que pueden almacenarse en una
dirección dada sin causar una colisión.
4) La técnica usada para resolver las colisiones.
Funciones de hash más comunes.
A) Hashing por resto de la división.
La idea básica es dividir el valor de la clave por un número
apropiado y después utilizar el resto de la división entera como
dirección para el registro.
Sea d el divisor
Dirección = Clave % d
El problema radica en la correcta elección de d.
Existen varios factores que deben ser considerados en la elección
de “d”.
Recuerde que el rango de Clave % d = [0, d-1]
Esto nos indica que el valor de “d” determina el tamaño del espacio
de direcciones relativas.
Si la cantidad de registros del archivo es N entonces d > N.
El divisor debe seleccionarse de forma tal que la probabilidad de
caer en una clase de equivalencia del resto sea minimizada. Este
es un objetivo difícil de alcanzar. Generalmente se elige un divisor
que mantenga una probabilidad relativamente baja, pero sin
esforzarse demasiado.
Nota:
Investigadores han demostrado que los divisores pares se
comportan pobremente, especialmente en conjunto de valores de
claves que son predominantemente impares.
[Buchholz, 1963] sugiere que el divisor debe ser un número primo.
[Lum, 1971] indica que los divisores no primos trabajan tan bien
como los divisores primos, siempre y cuando los divisores no
primos no contengan números primos pequeños como factores.
Sugieren que seleccionar un número que no contenga ningún factor
primo menor que 20 es probablemente suficiente para asegurar un
buen desempeño.
Descargar

Recursividad