busqueda hash

Búsqueda por hash

Hasta ahora las técnicas de localización de registros vistas, emplean un proceso de búsqueda que implica cierto tiempo y esfuerzo. El siguiente método nos permite encontrar directamente el registro buscado.

La idea básica de este método consiste en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas. Un problema potencial encontrado en este proceso, es que tal función no puede ser uno a uno; las direcciones calculadas pueden no ser todas únicas, cuando R(k1 )= R(k2)
Pero : K1 diferente de K2 decimos que hay una colisión. A dos llaves diferentes que les corresponda la misma dirección relativa se les llama sinónimos.

A las técnicas de calculo de direcciones también se les conoce como :
Técnicas de almacenamiento disperso
Técnicas aleatorias
Métodos de transformación de llave - a- dirección
Técnicas de direccionamiento directo
Métodos de tabla Hash
Métodos de Hashing
Pero el término mas usado es el de hashing. Al cálculo que se realiza para obtener una dirección a partir de una llave se le conoce como función hash.


Ventaja
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.
La eficiencia de una función hash depende de:
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
Las funciones hash mas comunes son:
Residuo de la división
Medio del cuadrado
Pliegue