- INTRODUCCION.
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.
- HASH
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.
Hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un registro, archivo, documentó, etc.
- FUNCIONES DE HASH
Una función de hash es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo).
- 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
- COLISIONES EN HASH
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.
- 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.
- FUNCIONES EN HASH MAS COMUNES
Residuo de la división.
Dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo de la división como dirección relativa para el registro (dirección = llave módulo divisor).
Medio del cuadrado.
La llave es elevada al cuadrado, después algunos dígitos específicos se extraen de la mitad del resultado para constituir la dirección relativa.
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.
- OPERACIONES BASICAS
- INSERCION.
- BUSQUEDA.
- ELIMINAR.
