Una tabla hash o mapa hash es una estructura de datos que asocia llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el acceso a los elementos almacenados a partir de una clave generada. Funciona transformando la clave con una función hash en un hash, un número que la tabla hash utiliza para localizar el valor deseado.

Aquí te damos un ejemplo de la implementación de una Tabla Hash en C++.

Puedes descargar el código fuente:

  • Tipo de Archivo: Comprimido RAR
  • Descarga: 2.17 kB

Download Ejemplo TablaHash C++ Ejemplo TablaHash C++ (419)

La descarga contiene dos archivos: TablaHash.cpp yTablaHash.h los cuales son los siguientes:

TablaHash.cpp

PLAIN TEXT
C++:
  1. /* TablaHash.cpp
  2. *
  3. * Demostración de como se usa TablaHash.h
  4. * Pide al usuario cuantas veces quiere realizar la demostración y al final despliega las estadisticas.
  5. *
  6. * Autor: Taboo
  7. */
  8.  
  9.  
  10. #include <stdlib.h>
  11. #include "TablaHash.h"
  12.  
  13. int main()
  14. {
  15.       int size;
  16.       int modulo;
  17.       int veces;
  18.       double promedioColisiones = 0;
  19.       double promedioDatos = 0;
  20.       int promedioPrimeraColision = 0;
  21.       TablaHash *prueba;
  22.       TablaHash yo(1000,773);
  23.  
  24.       cout <<"Esta es una simulacion del rendimiento de Tablas Hash" <<endl;
  25.    //   cout <<"De que tamano desea la tabla?" <<endl;
  26.      // cin>> size;
  27.       //cout <<"Cual sera el divisor para calcular la llave? (llave = dato / divisor) " <<endl;
  28.       //cin>> modulo;
  29.       //prueba = new TablaHash(size,modulo);
  30.       cout <<"Cuantas veces desea correr la simulacion?" <<endl;
  31.       cin>> veces;
  32.  
  33.  
  34.  
  35.     for(int i = 0; i <veces; i++)
  36.       {
  37.         yo.insertaRandom();
  38.         promedioColisiones += yo._colisiones();
  39.         promedioDatos += yo.datos();
  40.         promedioPrimeraColision += yo._primeraColision();
  41.         yo.inicializa();
  42.       }
  43.         promedioColisiones = promedioColisiones/veces;
  44.         promedioDatos = promedioDatos;
  45.         promedioPrimeraColision = static_cast<int>(promedioPrimeraColision/veces);
  46.         double ocupacion = (promedioDatos/size)*100;
  47.  
  48.  
  49.         cout <<"Resultados" <<endl;
  50.         cout <<"Una tabla Hash de tamano " <<yo._size() <<" y con un divisor de " <<yo._divisor() <<endl;
  51.         cout <<"Tiene el siguiente rendimiento despues de insertar datos aleatoriamente durante " <<veces;
  52.         cout <<" veces." <<endl;
  53.         cout <<"Promedio de colisiones " <<promedioColisiones <<endl;
  54.         cout <<"Promedio de datos insertados " <<promedioDatos <<endl;
  55.         cout <<"Promedio de primeras colisiones " << promedioPrimeraColision <<endl;
  56.         cout <<"Promedio de ocupacion de la Tabla " <<ocupacion <<endl;
  57.         cout <<"El criterio de paro para dejar de insertar datos es que el numero de colisiones sea menor al";
  58.         cout <<" 70% del tamano total de la tabla" <<endl;
  59.  
  60.  
  61.       system("PAUSE");
  62.       return 0;
  63. }

TablaHash.h

PLAIN TEXT
C++:
  1. #include <iostream.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. class TablaHash
  6. {
  7.       private:
  8.               int size;
  9.               int divisor;
  10.               int intentos;
  11.               int *contenedor;
  12.               int primeraColision;
  13.               int colisiones;
  14.       public:
  15.             //contenedor sin tamaño especificado
  16.             TablaHash():size(0), intentos(0), primeraColision(0), colisiones(0){}
  17.  
  18.             //contenedor con un tamaño especifico, sin divisor
  19.             TablaHash(int a): size(a), intentos(0), primeraColision(0), colisiones(0)
  20.             {
  21.                   contenedor = new int[a];
  22.                   for(int i = 0; i <a; i++)
  23.                       contenedor[i] = -1;
  24.             }
  25.  
  26.             //contenedor con tamaño especifico y divisor
  27.             TablaHash(int a, int b): size(a), divisor(b), intentos(0), primeraColision(0), colisiones(0)
  28.             {
  29.                  contenedor = new int[a];
  30.                  if(!esPrimo(divisor))
  31.                    {
  32.                       char respuesta;
  33.                       cout <<"El modulo que dio no es primo. Desea utilizarlo de todos modos? (s/n)" <<endl;
  34.                       cin>> respuesta;
  35.                       if(respuesta == 's')
  36.                         {
  37.                           for(int i = 0; i <a; i++)
  38.                            contenedor[i] = -1;
  39.                           return;
  40.                         }
  41.                       cout <<"El numero primo mas cercano es " <<siguientePrimo(divisor);
  42.                       cout <<". Se utilizara ese valor." <<endl;
  43.                             divisor = siguientePrimo(divisor);
  44.                    }//if 1
  45.  
  46.                     for(int i = 0; i <a; i++)
  47.                       contenedor[i] = -1;
  48.             }
  49.  
  50.             bool esPrimo(int a)
  51.             {
  52.               for(int i = 2; i <a; i++)
  53.                  {
  54.                          if(a%i==0)
  55.                             return false;
  56.                  }
  57.                return true;
  58.             }
  59.  
  60.             int siguientePrimo(int a)
  61.             {
  62.                 if(esPrimo(a))
  63.                    return a;
  64.  
  65.                 int resultado = a;
  66.  
  67.                 while(!esPrimo(++resultado));
  68.                 return resultado;
  69.             }
  70.  
  71.             inline int llave(int a){ return a%divisor; }
  72.  
  73.             bool inserta(int a, int b)
  74.             {
  75.                 // cout <<"Tratando de insertar : " <<b <<" en [" <<a <<"]" <<endl;
  76.                  if(contenedor[a] == -1)
  77.                      {
  78.                          contenedor[a] = b;
  79.                          intentos++;
  80.                          return true;
  81.                      }
  82.                  else
  83.                      colisiones++;
  84.                      intentos++;
  85.                      if(primeraColision == 0)
  86.                         primeraColision = intentos;
  87.  
  88.                      return false;
  89.             }
  90.  
  91.             void insertaRandom()
  92.             {
  93.                  srand(time(0));
  94.                  int i = rand();
  95.                  int posicion;
  96.  
  97.                  int condicion = (colisiones*100)/size;
  98.                  while(colisiones <(size * 0.7))// && intentos <size)
  99.                  {
  100.                     i = rand();
  101.                     posicion = llave(i);
  102.                     while(!inserta(posicion,i))
  103.                     {
  104.                        // cout <<"Colision insertando el valor " <<i <<" en localidad [" <<posicion <<"]" <<endl;
  105.  
  106.                         if(posicion <size-2)
  107.                            posicion++;
  108.                         else
  109.                             posicion = 0;
  110.                     }
  111.  
  112.                  }
  113.             }
  114.  
  115.             int _intentos(){ return intentos; }
  116.             int _size() { return size; }
  117.             int at(int a){ return contenedor[a]; }
  118.             int _colisiones(){ return colisiones; }
  119.             int _primeraColision() { return primeraColision; }
  120.             int _divisor() { return divisor; }
  121.  
  122.             friend ostream& operator <<(ostream &out, TablaHash &rhs)
  123.             {
  124.                    int datos = 0;
  125.                    for(int i = 0; i <rhs._size(); i++)
  126.                    {
  127.                       if( rhs.at(i) != -1)
  128.                           {
  129.                               out <<"[" <<i <<"] " <<"= " <<rhs.at(i) <<endl;
  130.                               datos++;
  131.                           }
  132.                    }
  133.                    out <<"Total de datos insertados satisfactoriamente: " <<datos <<endl;
  134.                    out <<"Total de Colisiones: " <<rhs._colisiones() <<endl;
  135.                    out <<"La primera Colision se dio en el intento: " <<rhs._primeraColision() <<endl;
  136.                    //out <<"Total de intentos: " <<rhs._intentos() <<endl;
  137.                    out <<"Tamano de la tabla: " <<rhs._size() <<endl;
  138.                    return out;
  139.             }
  140.  
  141.             void inicializa()
  142.             {
  143.                  for(int i = 0; i<size; i++)
  144.                    contenedor[i] = -1;
  145.             }
  146.  
  147.             int datos()
  148.             {
  149.               int dato = 0;
  150.               for(int i = 0; i <size; i++)
  151.                  {
  152.                       if(contenedor[i] != -1)
  153.                          dato++;
  154.                  }
  155.  
  156.                return dato;
  157.             }
  158.  
  159.             void operator =(TablaHash &rhs)
  160.             {
  161.                  size = rhs._size();
  162.                  intentos  = rhs._intentos();
  163.                  primeraColision = rhs._primeraColision();
  164.                  colisiones  = rhs._colisiones();
  165.                  contenedor = new int[size];
  166.                  divisor = rhs._divisor();
  167.             }
  168.  
  169. };

Popularidad: 100%