martes, 12 de julio de 2011

Extra ANSI C , Tablas de Dispersion y Usos

- Las tablas de dispersion sirven para realizar inserciones, eliminaciones y busquedas en tiempo promedio constante. 

- Son estructuras de datos que se usan en aplicaciones que manejan una secuencia de elementos, de tal forma que cada elemento tiene asociado un valor clave .

- Estructura de datos ideal: un vector con tamano fijo N.
 
- Una funcion de dispersion establece la correspondencia
de cada clave con algun numero en el intervalo [0 . . . N − 1].

- Esta funcion tiene que ser facil de calcular, y asegurar que
dos claves distintas se correspondan con celdas diferentes.

- Como esto ultimo es imposible, buscamos una funcion que distribuya homogeneamente las claves entre las celdas.

- Resta escoger una funcion y decidir el tamano de la tabla y que hacer cuando dos claves caen en la misma celda.

- Si al insertar un elemento, este se dispersa en el mismo valor que un elemento ya insertado tenemos una colision y hay que resolverla.


- Las tablas hash se suelen implementar sobre vectores de una dimensión, aunque se pueden hacer implementaciones multi-dimensionales basadas en varias claves

- Las tablas de dispersion se usan para representar diccionarios en los que se busca una clave y se devuelve su definicion.

REFERENCIAS:
www.madsgroup.org/docencia/alg/tablas_de_dispersion.pd
http://www.ie.uia.mx/acad/atortole/progra2/hash.html 

1 comentario: