Ir al contenido principal

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 de hashing 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 de datos.
  • Dentro del espacio de direccionamiento, hay posiciones vacías.
Conceptos de hashing
  • Clave: La clave contiene el valor que permite ubicar, mediante la función Hash, la posicionó 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 o Matrícula de Vehículo
  • 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:
    • Transformación: Si la clave no es numérica se convierte en un número. Con frecuencias utiliza el valor ASCII de cada carácter y luego se aplican operaciones matemáticas para obtener un número entero.
    • Generación: El número generado se procesa con un algoritmo que trata desuniformizar la distribución de las claves en el rango de direcciones.
    • 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ón tiene 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ón con el mayor grado de uniformidad posible para evitar colisiones.

El código implementado consiste en crear un archivo llamado dispersion.txt donde se guardan los respectivos registros en su posición de acuerdo a la clave generada por la función 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 función hashing se repite(hay una colisión) 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 así una lista. Allí 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:

Entradas populares de este blog

Obtener numeros aleatorios en C++ (rand, srand)

Es algo muy frecuente, cuando ya dominas todo eso de pedir y almacenar datos, ahora tu profesor te pedirá que tus programas generen números aleatorios para automatizar el proceso de llenar arreglos y todo eso.
Así que lo primero que tenemos que hacer es incluir la librería:
#include<stdlib.h>

Necesitamos esta libreria para usar la función time()
#include<time.h>

Luego inicializar los números aleatorios incluyendo esto:
srand(time(NULL));

Luego guardar el número aleatorio en alguna parte:
num = rand();

Para ajustar el rango de número aleatorios podemos hacer varias cosas.

- Número aleatorios entre 0 y 50:
  num=rand()%51;

- Número aleatorios entre 1 y 100:
  num=1+rand()%(101-1);

- Número aleatorios entre 250 y 420:
  num=250+rand()%(421-250);

De forma general es:
variable = limite_inferior + rand() % (limite_superior +1 - limite_inferior) ;

Así que un programa que muestre 10 números aleatorios entre 1 y 10 quedaría así:

Serie de Fibonacci en C++

Una sucesión de Fibonacci es aquella cuya ley de recurrencia es: an = an-1 + an-2. Es decir, cada término de la sucesión se obtiene sumando los dos anteriores. Para empezar a construirla necesitamos, por tanto, dos números de partida, a1 y a2. De esta forma, a3 sería a2 + a1 ; a4 sería a3 + a2 y así sucesivamente.


La más conocida es la que tiene a1 = 1 y a2 = 1, cuyos términos son: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 ... números que son conocidos como Números de Fibonacci.

Los términos de cualquier sucesión de Fibonacci tienen la particularidad de que el cociente entre dos términos consecutivos se aproxima al Número de Oro (1.6180339887499...), es decir, el límite de los cocientes an+1/an tiende al Número de Oro cuando n tiende a infinito.

Además, las series de Fibonacci cumplen otras curiosas propiedades, como por ejemplo, que la suma de n términos es igual al término n+2 menos uno:

a1 + a2 + a3 + a4 + ..... + an-1 + an = an+2 - 1

Implementación

Árboles Binarios de Búsqueda en C++ | Recorrido por niveles (Amplitud)

Hola a todos en esta ocasión compartiré sobre este tema de Arboles Binarios de Búsqueda, como un poco de teoría para su mejor entendimiento seguidamente mostraré la implementación en lenguaje de programación C++. Primero una breve introducción a árboles.

¿Qué es un árbol?


Un árbol es una estructura de datos no lineal puesto que cada elemento apunta a uno o varios elementos del mismo tipo; esto es dado un elemento, no hay un único camino a seguir. El elemento que apunta a otro es llamado padre, mientras que el elemento apuntado se conoce como hijo. Todos los elementos tienen un padre a excepción de la raíz. Puede decirse que un árbol esta formado por subárboles resaltando así su naturaleza recursiva.

¿Qué es un árbol binario?

Un árbol binario es aquel es el que cada elemento apunta como máximo a otros 2 elementos, comúnmente llamados hijo izquierdo y hijo derecho.

¿Qué es un árbol binario de búsqueda?

Un árbol binario de buque da o ABB, es un árbol binario en el cual para todo elemento, …