Tablas de Disperción (Puntos extra)

 ¿Qué es?

Es una técnica que se utiliza para implementar inserciones, eliminaciones y búsquedas en un tiempo medio constante.

Elementos

La estructura hash se construye con tres elementos básicos:

• Un vector direccionable mediante números de posición capaz de almacenar N elementos.
• Una función de dispersión que nos permita a partir de la clave,obtener el índice donde estará el dato asociado a esa clave.
• una función de resolución de colisiones.

Las tablas hash se suelen implementar sobre arreglos de una dimensión aunque se pueden hacer implementaciones multi-dimensionales basadas en varias claves, las tablas hash proveen tiempo constante de busqueda promedio, sin importar el número de elementos de la tabla. Sin embargo, en casos particularmente malos el tiempo de búsqueda puede llegar a O(n) , es decír, en función del
numero de elementos.

Otras estructuras como arboles binarios son más rápidos en promedio ( tiempo de búsqueda(log n))
pero la información está ordenada en todo momento.

 Un ejemplo

Un diccionario es una estructura de datos abstracta para conjuntos dinámicos en los cuales se aplican las operaciones INSERCION, SUPRESION y BUSQUEDA.

Bibilografía:

http://www.slideshare.net/salomonkarr/tablas-de-dispersin
http://delta.cs.cinvestav.mx/~adiaz/anadis/hash-pdf2.pdf