Metodo de Dispersion (Hashing) en C++
El trmino hash proviene, aparentemente, de la analoga con el significado estndar(en ingls)de dicha palabra en
el mundo real: picar y mezclar.
Definicin
Es un mtodo que permite encontrar, con el mnimo esfuerzo, una clave dada dentro de un conjunto de
elementos. Tambin se denomina mtodo de "transformacin de claves", "direccionamiento
calculado","direccionamiento asociativo" o de "dispersin".En la tcnica de hashing se aplican clculos o
transformaciones aritmticas sobre la clave para producir directamente una direccin en una tabla o archivo de
acceso directo. Por ejemplo:
El mtodo de direccionamiento por hashing tiene las siguientes caractersticas generales:
Buena velocidad de bsqueda sin necesidad de tener los datos ordenados.
El tiempo de bsqueda es prcticamente independiente de la cantidad de datos.
Dentro del espacio de direccionamiento, hay posiciones vacas.
Conceptos de hashing
a) Clave: La clave contiene el valor que permite ubicar, mediante la funcin Hash, la posicino registro que
contiene el resto de informacin asociada. Normalmente la clave es el campo que identifica en forma nica la
informacin. Por ejemplo:
Cdula de Identidad
Registro de Informacin Fiscal
Placa o Matrcula de Vehculo
b) Funcin Hash: Es un algoritmo o transformacin que, aplicado a la clave, devuelve la posicin del destino en
donde podemos ubicar o recuperar el elemento que contiene dicha clave. Normalmente consta de tres partes:
Transformacin: Si la clave no es numrica se convierte en un nmero. Con frecuenciase utiliza el valor ASCII de
cada carcter y luego se aplican operaciones matemticas para obtener un nmero entero.
Generacin: El nmero generado se procesa con un algoritmo que trata deuniformizar la distribucin de las claves
en el rango de direcciones.
Compresin: Se comprime el nmero obtenido multiplicndolo por un factor para adecuarlo a la capacidad de
almacenamiento [Link] funcin Hash debe definirse al momento de disear el sistema y su seleccin tiene
gran incidencia en rendimiento del sistema. Una buena funcin Hash debe tener las siguientes caractersticas:
Sencilla, de manera que sea fcil de codificar y minimice el tiempo de clculo.
Distribucin Uniforme de las direcciones tratando que la generacin distribuya en forma aleatoria las claves y
evite agrupamientos.
La idea es seleccionar una funcin que permita obtener una distribucin con el mayor grado de uniformidad
posible para evitar colisiones.
El codigo implementado consiste en crear un archivo llamado [Link] 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 funcion
hashing se repite(hay una colision) el numero de registro, este registro pasa a ser insertado en el
archivo [Link]
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.
Implementacion en C++
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
using namespace std;
struct registro{
int nr;
char clave[8];
char data[8];
int sr;
}r, a, s;
struct encabezado{
int nrs;
}ed, ec; /// encabezado de dispersion y colisiones
FILE *fdd, *fdc;
int lr, le;
int fh( char *clave )
{
int nr = 0;
for(int i=0; i<strlen(clave); i++)
{
nr += int(clave[i]);
}
nr = nr%10 + 1;
return nr;
}
/********************** Funcion Escribir ***********************/
void escribir()
{
int pos, x;
char rpt;
bool band;
fdd = fopen("[Link]", "w+");
if(fdd==NULL){
cout << " No se pudo crear [Link]" << endl;
return;
}
fdc = fopen("[Link]", "w+");
if(fdc==NULL){
cout << " No se pudo crear [Link]" << endl;
return;
}
/// Inicializando variables
[Link] = 0;
[Link] = 0;
fwrite(&ed, le, 1, fdd);
fwrite(&ec, le, 1, fdc);
/// Bucle para insertar varios registros
do
{
fflush(stdin);
cout << " Clave: "; gets([Link]);
cout << " Data : "; gets([Link]);
fflush(stdin);
[Link] = -1;
[Link] = fh([Link]);
cout << " Clave = "<< [Link] << endl;
pos = ([Link]-1)*lr + le;
fseek(fdd, pos, 0);
fread(&s, lr, 1, fdd);
if(strcmp([Link], "")==0)
{
fseek(fdd, pos, 0);
fwrite(&r, lr, 1, fdd);
++[Link];
}
else
{
band = false;
x = [Link];
/// entramos al archivo de colisiones
while(x != -1)
{
band = true;
pos = (x-1)*lr + le;
fseek(fdc, pos, 0);
fread(&s, lr, 1, fdc);
a = s;
x = [Link];
}
/// Listas de en el archivo de colision
if(band==true)
{
[Link] = ++[Link];
[Link] = [Link];
fseek(fdc, pos, 0);
fwrite(&a, lr, 1, fdc);
fseek(fdc, 0, 2);
fwrite(&r, lr, 1, fdc);
}
if(band==false)
{
[Link] = ++[Link];
[Link] = [Link];
fseek(fdd, pos, 0);
fwrite(&s, lr, 1, fdd);
fseek(fdc, 0, 2);
fwrite(&r, lr, 1, fdc);
}
}
cout << " Mas registros [s/n] : "; cin >> rpt; cout << endl;
}while(rpt!='n');
fseek(fdd, 0, 0);
fwrite(&ed, le, 1, fdd); /// actualizamos la cabezera del archivo
DISPERSION
fseek(fdc, 0, 0);
fwrite(&ec, le, 1, fdc); /// actualizamos la cabezera del archivo
COLISIONES
fclose(fdd);
fclose(fdc);
}
/********************** Funcion Leer ***********************/
void buscar()
{
int pos, x, nr;
char v_clave[10];
bool band;
fdd = fopen("[Link]", "r");
if(fdd==NULL){
cout << " No se pudo abrir [Link]" << endl; return;
}
fdc = fopen("[Link]", "r");
if(fdc==NULL){
cout << " No se pudo abrir [Link] " << endl; return;
}
fflush(stdin);
cout << " Ingrese clave : "; gets(v_clave);
nr = fh(v_clave);
pos = (nr-1)*lr + le;
fseek(fdd, pos, 0);
fread(&r, lr, 1, fdd);
if(strcmp(v_clave, [Link])==0)
{
cout << " Su data es: " << [Link] << endl;
return;
}
else
{
band = false;
x = [Link];
while( x != -1 )
{
pos = (x-1)*lr + le;
fseek(fdc, pos, 0);
fread(&r, lr, 1, fdc);
if(strcmp(v_clave, [Link])==0)
{
band = true;
cout << " Su data es : " << [Link] << endl;
break;
}
}
if(band == false)
{
cout << " No esta registrado..!" << endl;
}
}
fclose(fdd);
fclose(fdc);
}
void mostrar_archivos()
{
fdd = fopen("[Link]", "r");
if(fdd==NULL){
cout << " No se pudo abrir [Link]" << endl; return;
}
fdc = fopen("[Link]", "r");
if(fdc==NULL){
cout << " No se pudo abrir [Link] " << endl; return;
}
fread(&ed, le, 1, fdd);
cout << " Longitud Registro : " << lr << endl;
cout << " Longitud de encabezado: " << le << endl;
cout << "\nArchivo [Link] \n";
cout << "----------------------------------- \n";
cout << " NR CLAVE DATA SR \n";
while( fread(&s, lr, 1, fdd)!=NULL)
{
cout << setw(4) << [Link] << setw(10) << [Link] << setw(10);
cout << [Link] << setw(6) << [Link] << endl;
}
fread(&ed, le, 1, fdc);
cout << "\nArchivo [Link] \n";
cout << "----------------------------------- \n";
cout << " NR CLAVE DATA SR \n";
while( fread(&s, lr, 1, fdc)!=NULL)
{
cout << setw(4) << [Link] << setw(10) << [Link] << setw(10);
cout << [Link] << setw(6) << [Link] << endl;
}
fclose(fdd);
fclose(fdc);
}
void menu()
{
cout << "\t\t METODO DE DISPERSION - HASHING \n\n";
cout << "\t 1. Escribir \n";
cout << "\t 2. Buscar Registro \n";
cout << "\t 3. Mostrar Archivo \n";
cout << "\t 4. Salir \n";
cout << "\t >> Ingrese opcion: ";
}
/********************** Funcion Principal ***********************/
int main()
{
int op;
lr = sizeof(struct registro);
le = sizeof( struct encabezado);
do
{
menu(); cin >> op;
cout<<endl;
switch(op)
{
case 1:
escribir(); break;
case 2:
buscar(); break;
case 3:
mostrar_archivos();
case 4:
exit(0);
}
cout <<"\n\n ";
system("pause"); system("cls");
}while(op>0);
return 0;
}
