Búscalo aquí:

Tablas Hash [código]

Las Tablas Hash son unas de las estructuras de datos más comunmente usadas para realizar tareas de asociación de claves puesto que permiten el acceso a los datos almacenados en dicha estructura usando como claves de acceso a los mismos datos que mantienen almacenados.


Las tablas hash se suelen implementar sobre arrays de una dimensión, aunque se pueden hacer implementaciones multi-dimensionales basadas en varias claves. Como en el caso de los arrays, las tablas hash proveen tiempo constante de búsqueda promedio, sin importar el número de elementos en la tabla. Sin embargo, en casos particularmente malos el tiempo de búsqueda puede llegar a O(n), es decir, tomar un tiempo lineal de búsqueda en función del número de elemementos almacenado en la tabla hash [1].

A continuación presentaremos el código en C++ de la implementación de una Tabla Hash, en la cual se presentan dos funciones hash diferentes así como dos funciones de inserción, además se colocan funciones de captura de tiempo (como QueryPerformanceCounter por ejemplo) para hacer la medición de la performance del funcionamiento de la inserción en la Tabla Hash.

  1. /*
  2. Name: TablaHash.h
  3. Author: Shiguihara Juárez Pedro
  4. Author: Valverde Rebaza Jorge
  5. Description: Implementación de una Tabla Hash
  6. */
  7. #include<stdio.h>
  8. /* Declaracion de la tabla Hash */
  9. class TablaHash{
  10. public:
  11. TablaHash();
  12. TablaHash(int );
  13. TablaHash(int ,char *);
  14. ~TablaHash();
  15. void reportar();
  16. bool insertar(char *);
  17. bool insertar2(char *);
  18. int getDominio();
  19. int hash (char *);
  20. int hash2(char *);
  21. private:
  22. NodoT *celdas;
  23. int numeroNodos;
  24. char *defecto;
  25. double secsPrimario;
  26. double secsSecundario;
  27. };
  28. // Constructor 1
  29. // @nElementos: la dimension de la tabla para generarse en memoria
  30. TablaHash::TablaHash(int nElementos)
  31. {
  32. int i=0;
  33. celdas = new NodoT[nElementos];
  34. numeroNodos = nElementos;
  35. defecto = "nada";
  36. for(i=0; i <numeroNodos; i++ )
  37. celdas[i] = NodoT(defecto);
  38. //printf("\nEspacio creado satisfactoriamente...\n");
  39. secsPrimario=0.0;
  40. secsSecundario=0.0;
  41. }
  42. //Constructor 2
  43. // @defec: Cadena con la que se inicializan todas las
  44. //celdas indicando que esta vacia
  45. TablaHash::TablaHash(int nElementos, char *defec)
  46. {
  47. int i=0;
  48. celdas = new NodoT[nElementos];
  49. numeroNodos = nElementos;
  50. defecto = defec;
  51. for(i=0; i <numeroNodos; i++)
  52. celdas[i] = NodoT(defecto);
  53. //printf("\nEspacio creado satisfactoriamente...\n");
  54. secsPrimario=0.0;
  55. secsSecundario=0.0;
  56. }
  57. //Destructor
  58. TablaHash::~TablaHash()
  59. {
  60. //delete[] celdas;
  61. //delete celdas;
  62. NodoT *aux;
  63. NodoT *aux2;
  64. int i=0;
  65. int cantidadPrimario=0;
  66. int cantidadSecundario=0;
  67. //printf("\nIniciando destruccion\n");
  68. for(i=0; i<numeroNodos; i++)
  69. {
  70. //Primero verificamos que la celda este vacia para borrarla
  71. //directamente de memoria
  72. //apuntaCelda = apuntaCelda + i;
  73. if(stricmp(celdas[i].valor,defecto)!=0 )
  74. {
  75. aux = celdas;
  76. aux = aux + i;
  77. aux2 = aux->siguiente;
  78. while(aux2)
  79. {
  80. cantidadSecundario++;
  81. aux = aux2;
  82. aux2 = aux2->siguiente;
  83. delete aux;
  84. aux = NULL;
  85. }
  86. cantidadPrimario++;
  87. }
  88. }
  89. printf("\nAccesos primarios: %i",cantidadPrimario);
  90. printf("\nAccesos secundarios: %i",cantidadSecundario);
  91. printf("\nTiempo: Insercion directa Hash: %.16g ms",
  92. secsPrimario * 1000.0);
  93. printf("\nTiempo: Insercion por colision Hash: %.16g ms\n",
  94. secsSecundario * 1000.0);
  95. aux = NULL;
  96. aux2 = NULL;
  97. delete[] celdas;
  98. delete celdas;
  99. }
  100. //devuelve el dominio de la tabla hash
  101. int TablaHash::getDominio()
  102. {
  103. return numeroNodos;
  104. }
  105. //Reporte de todas las celdas
  106. void TablaHash::reportar()
  107. {
  108. printf("\nReporte de tabla hash\n");
  109. printf("-----------------------------------------------------\n");
  110. int i=0;
  111. for(i=0; i <numeroNodos; i++)
  112. printf("\nT [%i] = %s",i , celdas[i].valor);
  113. }
  114. bool TablaHash::insertar2(char *v)
  115. {
  116. int idNuevo = hash2(v);
  117. bool cortarBucle = false;
  118. NodoT *aux;
  119. //printf("\nID HASH: %i",idNuevo);
  120. //secsPrimario=0.0;
  121. //secsSecundario=0.0;
  122. LARGE_INTEGER t_iniPrim, t_finPrim;
  123. LARGE_INTEGER t_iniSec, t_finSec;
  124. double secs=0.0;
  125. double secs2=0.0;
  126. if(stricmp(celdas[idNuevo].valor, defecto)==0)
  127. {
  128. QueryPerformanceCounter(&t_iniPrim);
  129. celdas[idNuevo].modificarValor(v);
  130. QueryPerformanceCounter(&t_finPrim);
  131. secs = performancecounter_diff(&t_finPrim, &t_iniPrim);
  132. secsPrimario = secsPrimario + secs;
  133. return true;
  134. }
  135. else if(stricmp(celdas[idNuevo].valor, v)!=0)
  136. {
  137. QueryPerformanceCounter(&t_iniSec);
  138. //printf("\nHubo colisión en la posición %i",idNuevo);
  139. aux = celdas;
  140. aux = aux + idNuevo;
  141. //printf("\nPuntero avanzo: %s",aux->valor);
  142. cortarBucle = false;
  143. while( aux->siguiente && cortarBucle == false)
  144. {
  145. if(stricmp(aux->siguiente->valor, v)==0)
  146. cortarBucle = true;
  147. aux = aux->siguiente;
  148. }
  149. if(cortarBucle == false)
  150. {
  151. aux->siguiente = new NodoT(v);
  152. aux = NULL;
  153. QueryPerformanceCounter(&t_finSec);
  154. secs2 = performancecounter_diff(&t_finSec, &t_iniSec);
  155. secsSecundario = secsSecundario + secs2;
  156. return true;
  157. }
  158. QueryPerformanceCounter(&t_finSec);
  159. secs2 = performancecounter_diff(&t_finSec, &t_iniSec);
  160. secsSecundario = secsSecundario + secs2;
  161. //printf("La palabra ya existe en secundario: %s",v);
  162. aux = NULL;
  163. return false;
  164. }
  165. else
  166. {
  167. //printf("La palabra ya existe en primario: %s",v);
  168. return false;
  169. }
  170. }
  171. bool TablaHash::insertar(char *v)
  172. {
  173. int idNuevo = hash2(v);
  174. if(stricmp(celdas[idNuevo].valor, defecto)==0)
  175. {
  176. celdas[idNuevo].modificarValor(v);
  177. return true;
  178. }
  179. else
  180. return false;
  181. }
  182. // Funcion hash que calcula una posicion de la tabla dado
  183. //un valor ingresado como parametro
  184. int TablaHash::hash(char *v)
  185. {
  186. int contador = 0;
  187. int n = strlen(v);
  188. int i=0;
  189. for(i=0; i<n; i++)
  190. contador = contador + v[i]*i;
  191. contador = contador % numeroNodos;
  192. return contador;
  193. }
  194. // Funcion hash que calcula una posicion de la tabla dado un
  195. //valor ingresado como parametro
  196. int TablaHash::hash2(char *v)
  197. {
  198. // int primo = 1009;
  199. // int primo = 500009;
  200. // int primo = 50021;
  201. //int primo = 500009;
  202. int primo = 200003;
  203. int n = strlen(v);
  204. const char *d = v;
  205. int h = 0;
  206. for(int i=0; i<n; i++,d++ )
  207. h = (h<<2)+ *d;
  208. return ((h >= 0) ? (h % primo) : (-h % primo));
  209. }

En la Tabla Hash presentada se hace uso de la estructura NodoT. Esta estructura, asi como un ejemplo de uso de la tabla hash presentada se mostrará en el post Tablas Hash 2 [código].


Quieres leer más post como éste???...suscribete aquí!!!

3 comentarios:

  1. Hey gracias por la info y por ejemplo, me sirvio mucho....

    Saludos...

    F. luismiguelrocker@yahoo.es

    ResponderEliminar
  2. hey esta bueno, gracias por colgarlo.
    Universida de El salvador
    El Salvador

    F. manuel

    ResponderEliminar
  3. Gracias me sirvio en verdad mucho...

    ResponderEliminar

Bienvenido a jcGeorge's Blog!!!

Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

Gracias por leer este blog!!!

Related Posts Plugin for WordPress, Blogger...