tablas HASH

Benemérita Universidad Autónoma de Puebla


Facultad de Ciencias de la Computación


Ingeniería en Ciencias de la Computación


Algoritmos y estructuras de datos


Alfonso


TrabajoFinal:
Aplicaciones de tipos Abstractos
Transformaciones de llaves (Hash)




Edder Ramírez mata 200428521
Francisco Javier Juárez Pérez 200419349










11de Mayo de 2007 Primavera 2007


Tablas Hash

En muchas ocasiones, nuestras aplicaciones requieren acceder a los datos utilizando como clave para el accesoparte de esos mismos datos. Esta necesidad de acceso asociativo es una situación muy común en el mundo real. Vamos a introducir un sencillo ejemplo que nos ayude a comprender las explicaciones venideras:Las tablas Hash o tablas de dispersión solucionan satisfactoriamente nuestro problema: nos permiten acceder asociativamente a la información y, además, lo hacen en un tiempo medio constante, esdecir, que el tiempo necesario para acceder a un elemento, no va a depender del número de elementos que almacene la estructura.

Una estructura Hash se construye con tres elementos básicos :
1. Unvector direccionable mediante número de posición (un array) capaz de almacenar N elementos.
2. Una función de dispersión que nos permita a partir de la clave obtener el índice donde estará el datoasociado a esa clave .Es frecuente que existan dos claves distintas para las que la función de dispersión produzca el mismo índice. Esto se denomina colisión, y las dos claves distintas que dieron lugaral mismo índice, se dicen sinónimas respecto a la función de dispersión utilizada.
3. Una función de resolución de colisiones.

Función de dispersión

Con respecto a la función de dispersión, suelección es clave para el buen funcionamiento de la estructura y la discusión sobre cual utilizar se escapa del objetivo de este artículo. Simplemente reseñar que ha de cumplir las siguientes...