Una tabla Hash es un contenedorsociativo (tipo Diccionario) que permite un almacenamiento y posterior recuperacin eficiente de elementos (denominados valores)
a partir de otros objetos, llamados claves; la podemos ver como un conjunto de entradas, cada entra tiene una clave nica, esto implica que una clave identifica univocamente a una entrada en una tabla hash. (Sergio Sama Villanueva, 2008) Las tablas hash aparecen para conseguir una bsqueda e insercin muy rpidas; para ello se hace uso de un array, con lo que volvemos a la estructura bsica de almacenamiento. Sin embargo, hay una diferencia importante que es lo que hace que sea mejor que el array en cuanto a rapidez: a cada dato se le asigna, mediante una frmula matemtica denominada funcin hash, una posicin nica en la tabla, con lo que la bsqueda, la insercin y el borrado son inmediatos (Miranda, 2004) Las tablas Hash esta compuestas por dos componentes, la propia clave y la informacin que se almacena en dicha entrada.
(Tiwari, 2010) FUNCIONES HASH La idea bsica de un valor hash es que sirva como una representacin compacta de la cadena de entrada. Por esta razn decimos que estas funciones resumen datos del conjunto dominio. Hasing Multiplicativo. Esta tcnica trabaja multiplicando la clave k por s misma o por una constante, usando despus alguna porcin de los bits del producto como una localizacin de la tabla hash. Otro mtodo multiplicativo, que evita las restricciones anteriores consiste en calcular h(k) = Int[M * Frac(C*k)] donde M es el tamao de la tabla y 0 <= C <= 1, siendo importante elegir C con cuidado para evitar efectos negativos como que una clave alfabtica K sea sinnima a otras claves obtenidas permutando los caracteres de k. Knuth (ver bibliografa) prueba que un valor recomendable es:
Hasing por Divisin. En este caso la funcin se calcula simplemente como h(k) = k mod M usando el 0 como el primer ndice de la tabla hash de tamao M.
Insertar Para insertar un elemento hay que introducir, en el campo de texto del dilogo lanzado al pulsar el botn Insertar, el valor deseado. Este valor puede ser un nmero entero o una cadena de caracteres.
Borrar El borrado en una tabla hash es muy sencillo y se realiza de forma muy eficiente. Una vez indicada la clave del objeto a borrar, se proceder a eliminar el valor asociado a dicha clave de la tabla. Si sobre la tabla resultante de la insercin del elemento azul realizamos el borrado del elemento negro, la tabla resultante sera la siguiente:
Otras operaciones Una de las principales operaciones que se pueden realizar en las tablas hash es la redispersin. La redispersin se suele realizar cuando el factor de carga(nmero de elementos / capacidad de la tabla) de la tabla supera cierto umbral. La redispersin consiste en pasar todos los elementos de la tabla original a una nueva tabla de un tamao mayor. De esta forma, se reduce el factor de carga de la tabla. (Lpez, 2012) Vaciar lista: Esta accin elimina todos los elementos presentes en la tabla Utilizacin de tablas hash Las dos principales ventajas que aportan las tablas hash son las siguientes: Almacenamiento asociativo Recuperacin eficiente de la informacin
Por lo tanto las tablas hash son muy tiles cuando el tiempo de acceso a la informacin es crtico. La gran eficiencia que proporcionan estas tablas hacen que sean las estructuras de datos escogidas en situaciones tales como la implementacin de la tabla de smbolos de un compilador. Esta es una tarea para la cual se adaptan a la perfeccin gracias a su carcter asociativo y su eficiencia.
Linkografa Lpez, D. (Abril de 2012). ETSII. Obtenido de http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/tablash.html Miranda, J. (16 de Mayo de 2004). IUMA. Recuperado http://www.iuma.ulpgc.es/users/jmiranda/docencia/programacion/Tema8_ne.pdf de Marzo de 2004 el
Sergio Sama Villanueva. (18 de Junio de 2008). DSTool. Obtenido de http://www.hci.uniovi.es/Products/DSTool/hash/hashqueSon.html Tiwari, H. (2010). Wikipedia. Obtenido de http://es.wikipedia.org/wiki/Funci%C3%B3n_hash
