Metodo De Dispersion Hashing En C

Metodo de Dispersion (Hashing) en C++
                 

Despues de tiempo de no postear, aqui les traigo un tema  que lleve el curso de Organizacion de Archivos que un metodo de acceso directo al archivo a conticuacion gare una explicacion mas detallada, acompañenme durante la explicacion de este metodo. Al final del post encontraran la implementacion en lenguaje C++

El término hash proviene,aparentemente, de la analogía con el significado estándar(en inglés)de dicha palabra en el mundo real: picar y mezclar.

Definición
Es un método que permite encontrar, con el mínimo esfuerzo, una clave dada dentro de un conjunto de elementos. También se denomina método de "transformación de claves", "direccionamiento calculado","direccionamiento asociativo" o de "dispersión".En la técnica dehashing se aplican cálculos o transformaciones aritméticas sobre la clave para producir directamente una dirección en una tabla o archivo de acceso directo. Por ejemplo:


El método de direccionamiento por hashing tiene las siguientes características generales:
Buena velocidad de búsqueda sin necesidad de tener los datos ordenados.
El tiempo de búsqueda es prácticamente independiente de la cantidad dedatos.
Dentro del espacio de direccionamiento, hay posiciones vacías.
Conceptos de hashing

a) Clave: La clave contiene el valor que permite ubicar, mediante la función Hash, la posicióno registro que contiene el resto de información asociada. Normalmente la clave es el campo que identifica en forma única la información. Por ejemplo:
Cédula de Identidad
Registro de Información Fiscal
Placa oMatrícula de Vehículo

b) Función Hash: Es un algoritmo o transformación que, aplicado a la clave, devuelve la posición del destino en donde podemos ubicar o recuperar el elemento que contiene dicha clave. Normalmente consta de tres partes:

1. Transformación: Si la clave no es numérica se convierte en un número. Con frecuenciase utiliza el valor ASCII de cada carácter y luego se aplican operacionesmatemáticas para obtener un número entero.
2. Generación: El número generado se procesa con un algoritmo que trata deuniformizar la distribución de las claves en el rango de direcciones.
3. Compresión: Se comprime el número obtenido multiplicándolo por un factor para adecuarlo a la capacidad de almacenamiento disponible.La función Hash debe definirse al momento de diseñar el sistema y su seleccióntiene gran incidencia en rendimiento del sistema. Una buena función Hash debe tener las siguientes características:
 Sencilla, de manera que sea fácil de codificar y minimice el tiempo de cálculo.
Distribución Uniforme de las direcciones tratando que la generación distribuya en forma aleatoria las claves y evite agrupamientos.
La idea es seleccionar una función que permita obtener una distribucióncon el mayor grado de uniformidad posible para evitar colisiones.

El codigo implementado consiste en crear un archivo llamado dispersion.txt donde se gurdan los respetivos registros en su posicion de acuuerdo a la clave generada por la funcion hashing(); que manipula los caracteres de la clave mediante codigo ASCII y devuelve un entero que seria el numero de registro. Si al devolver la funcionhashing se repite(hay una colision) el numero de registro, este registro pasa a ser insertado en el archivo colisiones.txt

Otro punto importante es que cada registro escrito en el archivo siempre tiene un puntero (llamado SR) que guarda el numero de registro del siguiente creando asi una lista. Alli en la imagen podemos apreciar la estructura de como se guarda los registros en el archivo.Finalmente aclaro que para este programa considere como clave como el nombre de una persona y la data su apellido, ustedes pueden acomodarle de acuerdo a sus necesidades.
 
Implementación:
233 234

#include
#include
#include
#include

using namespace std;
 
struct registro{
int nr;
char clave[8];
char data[8];
int sr;
}r, a, s;
 
struct...

Leer documento completo

Regístrate para leer el documento completo.