- 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
No hay comentarios:
Publicar un comentario