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 DIRECTOEl 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 direccionesColisiones

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) entoncesAplicar función hash a la clave del registroResolver colisiones, si es necesarioAlmacenar registrosAgregar 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 directorio2) 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 divisorDirecció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.