Teorico Hashing

Hashing
Es el mecanismo que trata de asegurar una recuperación rápida de registros, en un solo acceso promedio, lleva el nombre de dispersión o hashing.

Definiciones:
1) Técnica para generar una dirección base única para una clave dada. La dispersión se usa cuando se requiere acceso rápido mediante una clave.
2) Técnica que convierte la clave asociada a un registro de datos en un númeroaleatorio, el cual posteriormente es utilizado para determinar donde se almacena dicho registro.
3) Técnica de almacenamiento y recuperación que usa una función para mapear registros en direcciones de almacenamiento en memoria secundaria.

Las tres definiciones pueden resumirse en que la llave primero se convierte en un número, sobre el cual puede aplicarse la función de hash, que permite obtener ladirección donde el registro se almacenara dentro del archivo.

La técnica de dispersión presenta una seria de atributos:
No se requiere almacenamiento adicional. Esto significa que cuando se elige la opción de dispersión como método de organización de archivos, es el archivo de datos el que resulta disperso. Esta dispersión se genera a partir de la clave o llave primaria del archivo, y el registro quecontiene la información relacionada con la clave es ubicado en el espacio resultante de aplicar la función de hash. Así, no es necesario tener una estructura auxiliar que actúe como soporte para acceder rápidamente a la información.
Facilita la inserción y eliminación rápida de registros en el archivo. El proceso de inserción y borrado de información se realiza de una forma más eficiente entérminos de accesos a disco. En general, con un solo acceso a disco, un registro puede ser insertado o borrado del archivo.
Localiza registros dentro del archivo con un solo acceso a disco. La gran mayoría de las búsquedas serán efectivamente satisfechas con un acceso a disco.

Sin embargo, el método de dispersión presenta limitaciones, como por ej:
No es posible aplicar la técnica de dispersión enarchivos con registros de longitud fija. Esto debe a que cada dirección física obtenida debe tener capacidad para almacenar un registro de tamaño conocido.
No es posible obtener un orden lógico de los datos. Utilizando índices como metodología de acceso a datos, no solo la búsqueda es eficiente, sino que además presenta la característica de mantener los registros ordenados. Bajo la técnica de hashingno es posible preservar la propiedad de orden. Los registros son esparcidos en el archivo de datos.
No es posible tratar con claves duplicadas. Así, no es aplicable la función de hash sobre una clave secundaria. Una clave secundaria puede repetirse, por lo tanto, dos registros diferentes con la misma clave secundaria, aplicando la función de hash, tendrían como resultado la misma dirección dememoria. Cada registro debe residir en direcciones diferentes, y si se trabajara con claves secundarias, esta propiedad no se cumpliría.

Tipos de dispersión:
El método de hashing presenta 2 alternativas para su implantación, tratamiento de espacio en forma estática y tratamiento de espacio en forma dinámica.

Hashing con espacio de direccionamiento estático es aquella política donde el espaciodisponible para dispersar los registros de un archivo de datos está fijado previamente. Así, la función de hash aplicada a una clave da como resultado una dirección física posible dentro del espacio disponible para el archivo.
Hashing con espacio de direccionamiento dinámico es aquella política donde el espacio disponible para dispersar los registros de un archivo de datos aumenta o disminuye en funciónde las necesidades de espacio que en cada momento tiene el archivo. Así, la función de hash aplicada a una clave da como resultado un valor intermedio, que será utilizado para obtener una dirección física posible para el archivo. Estas direcciones son generadas de manera dinámica.

Parámetros de dispersión:
El método de dispersión cuando se utiliza con direccionamiento estático, presenta 4...