Milena Matamoros

Manuel Ricardo Cortés

Juan Carlos García

Procedimiento

Método consistente en aplicaruna función que traduce unconjunto de posibles valoresllave en un rango de direccionesrelativas

Casos de Colision

soluciones para reducir el número de colisiones Propagar los registros: Buscar funciones que distribuyan muy

aleatoriamente los registros podemos evitar "agrupaciones" de llaves que produzcan las mismas direcciones

Usar memoria extra: En el ejemplo anterior planteamos tener una dirección de entre 1000 posibles, el uso de memoria extra se basa en proponer un espacio de direcciones posibles mucho más grande que el número de registros a usar, de modo que si vamos a insertar 100 registros un espacio de 500 direcciones nos una mejor opción de esparcir mejor.

Colocar más de un registro en una dirección: A diferencia de los casos anteriores donde cada dirección almacena únicamente un registro, este concepto se basa en "buckets" o cubetas de datos en cada dirección, ahí se colocan algunos (casi todos) los registros que colisionan de manera que al hacer una búsqueda debemos recuperar la cubeta entera y ahi buscar por el registro deseado.

9.3.1 Un Algoritmo de Hash No existe una fórmula "única" para hash, pero el producirla es un algoritmo que básicamente se presenta en 3 pasos:

1) Representar la llave de manera numérica (siempre que no sea de por sí un número)Una buena opción es usar los valores ASCII o bien los Unicode de las letras

LOWELL= L O W E L L _ _ _ _ _ _76 79 87 69 76 76 32 32 32 32 32 32

2) Plegar y AgregarCombinar algunos de estos números para generar pequeños trozos con los que podamos trabajar76 79 | 87 69 | 76 76 | 32 32 | 32 32 | 32 32

De manera que podemos hacer algunas operaciones matemáticas con dichos números para finalmente obtener un número del cual obtendremos la dirección

7679 + 8769 + 7676 + 3232 + 3232 = 30 588

Nota: Respecto a la implementación se puede dar el caso de formar números demasiado grandes, tanto que llegue al overflow del tipo de datos que estemos usando. Para solucionar esto podemos usar funciones como el "mod" intermedias para no tener ese problema.

3) Dividir por un número primo y usar el resultado como direcciónLos archivos de hash por lo general suelen limitarse a un cierto rango de direcciones posibles para aprovechar mejor el concepto de memoria. de manera que podemos concluir nuestro algoritmo con la fórmula:

a= s mod n

donde a es la dirección resultante, s es la suma o resultado de los pasos anteriores y n el número de direcciones posibles en el archivo

Existen innumerables operaciones adicionales que pueden aplicarse en las fórmulas, así como las técnicas para limitar el valor final. Entre ellas se encuentran: elevar a alguna potencia, raíz cuadrada, convertir los números de base (hexadecimal, octal), etc...

Ventajas Se pueden usar los valores naturales de la llave,

puesto que se traducen internamente a direcciones fáciles de localizar

Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones

No se requiere almacenamiento adicional para los índices.

Desventajas No pueden usarse registros de longitud variable

El archivo no esta clasificado

No permite llaves repetidas

Solo permite acceso por una sola llave

Costos Tiempo de procesamiento requerido para la

aplicación de la función hash

Tiempo de procesamiento y los accesos E/S requeridos para solucionar las colisiones.

Factores de Eficiencia La distribución de los valores de llave que realmente se

usan

El numero de valores de llave que realmente están en uso con respecto al tamaño del espacio de direcciones

El numero de registros que pueden almacenarse en una dirección dad sin causar una colisión

La técnica usada para resolver el problema de las colisiones

Tipos de Funcion Hash

Residuo de la división

Medio del cuadrado

Pliegue

Hashing por residuo de división La idea de este método es la de

dividir el valor de la llave entre unnumero apropiado, y después utilizar elresiduo de la división como direcciónrelativa para el registro (dirección =llave módulo divisor).

Consideraciones Independientemente de que tan bueno sea el

divisor, cuando el espacio de direcciones de un archivo esta completamente lleno, la probabilidad de colisión crece dramáticamente. La saturación de archivo de mide mediante su factor de carga, el cual se define como la relación del numero de registros en el archivo contra el numero de registros que el archivo podría contener si estuviese completamente lleno.

Factor de Carga

Todas las funciones hash comienzan a trabajarprobablemente cuando el archivo esta casi lleno. Por logeneral el máximo factor de carga que puede tolerarse enun archivo para un rendimiento razonable es de entre el 70% y 80 %.

Hashing por Elevacion al cuadrado En esta técnica, la llave es elevada al cuadrado, después

algunos dígitos específicos se extraen de la mitad delresultado para constituir la dirección relativa. Si se deseauna dirección de n dígitos, entonces los dígitos se truncanen ambos extremos de la llave elevada al cuadrado,tomando n dígitos intermedios. Las mismas posiciones den dígitos deben extraerse para cada llave.

Utilizando esta función hashing el tamaño del archivoresultante es de 10n donde n es el numero de dígitosextraídos de los valores de la llave elevada al cuadrado.

Hashing por Pliegue En esta técnica el valor de la llave es particionada en

varias partes, cada una de las cuales

(excepto la ultima) tiene el mismo numero de dígitos que tiene la dirección relativa objetivo. Estas particiones son después plegadas una sobre otra y sumadas. El resultado, es la dirección relativa. Igual que para el método del medio del cuadrado, el tamaño del espacio de direcciones relativas es una potencia de 10.