• Author / Uploaded
• William CJ

Citation preview

Tabla hash Una tabla hash, mapa hash, tabla de dispersión o tabla fragmentada 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 (teléfono y dirección, por ejemplo) almacenados a partir de una clave generada (usando el nombre o número de cuenta, por ejemplo). Funciona transformando la clave con una función hash en un hash, un número que identifica la posición (casilla o cubeta) donde la tabla hash localiza el valor deseado. Un ejemplo práctico para ilustrar que es una tabla hash es el siguiente: Se necesita organizar los periódicos que llegan diariamente de tal forma que se puedan ubicar de forma rápida, entonces se hace de la siguiente forma - se hace una gran caja para guardar todos los periódicos (una tabla), y se divide en 31 contenedores (ahora es una "hash table" o tabla fragmentada), y la clave para guardar los periódicos es el día de publicación (índice). Cuando se requiere buscar un periódico se busca por el día que fue publicado y así se sabe en que zócalo (bucket) está. Varios periódicos quedarán guardados en el mismo zócalo (es decir colisionan al ser almacenados), lo que implica buscar en la sub-lista que se guarda en cada zócalo. De esta forma se reduce el tamaño de las búsquedas de O(n) a, en el mejor de los casos, O(1) y, en el peor, a O(log(n)).

Ejemplo de tabla hash.

Las tablas hash se suelen implementar sobre vectores 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 O(1),1 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, en función del número de elementos. Comparada con otras estructuras de arrays asociadas, las tablas hash son más útiles cuando se almacenan grandes cantidades de información. Las tablas hash almacenan la información en posiciones pseudo-aleatorias, así que el acceso ordenado a su contenido es bastante lento. Otras estructuras como árboles binarios autobalanceables tienen un tiempo promedio de búsqueda mayor (tiempo de búsqueda O(log n)), pero la información está ordenada en todo momento.

#include 1. #include 2. 3. #define MAXC 10//MAXIMO TAMAÑO DE UNA CADENA 4. #define MAXA 10//TAMAÑO DE LA TABLA 5. 6. struct nodo 7. { 8.

char *cadena;

9.

struct nodo *siguiente;

10.

};

11. 12.

int clave (char cadenaux[MAXC])//OBTIENE LA SUMA DE LOS VALORES ASCII DE CADA CARACTER DE LA CADENA

13.

{

14.

int clave=0, ascii, i=0;

15. 16.

while((ascii=cadenaux[i++])!='')

17.

clave+=ascii;

18. 19. 20.

return clave; }

21.

int hash (int clave)//SE DETERMINA LA POSICIO EN LA QUE SE GUARDARA LA CADENA

22.

{

23.

int posicion=clave%MAXA;

24. 25. 26.

return posicion; }

27. 28.

void insertar(struct nodo **ptabla, char cadena[MAXC])//INSERTAR NUEVO ELEMENTO EN UNA LISTA

29.

{

30.

struct nodo *nuevo = (struct nodo*) malloc(sizeof(struct nodo));//CREAMOS EL NUEVO NODO

31.

nuevo->cadena = cadena;//GUARDAMOS CADENA

32.

nuevo->siguiente = NULL;//COMO SE VA A INSERTAR AL FINAL, SERA EL QUE APUNTE A NULL

33.

struct nodo *actual=*ptabla;//CREAMOS UN PUNTERO AUXILIAR A NODO

34. 35.

if (*ptabla==NULL)

36.

{

37.

*ptabla=nuevo;//SI LISTA VACIA, ENTONCES: NUEVO ES EL PRIMER ELEMENTO

38.

}

39.

else

40.

{

41.

while (actual->siguiente != NULL)

42.

{

43.

printf("n %s n", actual->cadena);

44.

actual = actual->siguiente;//SI NO ESTA VACIA, SE RECORRE LA LISTA

45.

}

46.

actual->siguiente =nuevo;//EL ULTIMO NODO AHORA ANTECEDE AL NUEVO

47.

}

48.

}

49. 50.

void mostrar(struct nodo *ptabla)//IMPRIMIR LA TABLA

51.

{

52.

struct nodo *actual=ptabla;//ACTUAL ES UN PUNTERO AUXILIAR PARA RECORRER LA LISTA

53. 54.

while (actual!=NULL)//MIENTRAS NO SEA EL FINAL DE LA LISTA

55.

{

56.

printf("[ %s ]->", actual->cadena);//IMPRIME EL DATO DEL NODO CORRESPONDIENTE

57.

actual = actual->siguiente;//AVANZAMOS AL SIGUIENTE NODO

58.

}

59.

printf("NULLnn");

60.

}

61. 62.

main()

63.

{

64.

struct nodo *ptabla[MAXA];//ARREGLO DE PUNTEROS PARA NODOS

65.

char cadenaux[MAXC];//ARREGLO AUXILIAR PARA GUARDAR CADENA INTRODUCIDA

66.

int op, clavecadena, pos;//VARIABLES USADAS PARA MENU Y POSICION EN EL ARREGLO

67. 68.

for(pos=0;pos