TABLAS DE DISPERSION

Es una estructura de datos que asocia claves con valores. Estas tablas se utilizan para hacer búsquedas permitiendo el acceso a los elementos almacenados a partir de una clave generada, también se utiliza para implentar insercciones y eliminaciones. También son llamadas tablas hash.

Las tablas de dispersión son mas útiles cuando tienes que almacenar grandes cantidades de elementos y también se utilizan para los vectores de una dimensión y también para vectores multidimensionales.

Una estructura de dispersión se compone de 3 elementos:

1. Un vector con dirección que pueda almacenar "n" elementos.
2. Una función de dispersión que nos permita a partir de una clave, obtener el índice donde esta el dato con la clave.
3. Una función de resolución de colisiones.

Las operaciones básicas de las tablas son:

• Inserccion

1. Al almacenar un elemento en la tabla de dispersión se tiene que convertir su clave a un número, para esto se utiliza la función resumen (hash) a la clave del elemento.
2. El resultado de dicha función debe de dirigirse al espacio de direcciones del arreglo que se emplea como soporte, esto se obtiene con la función modulo. Después de este paso se obtendrá un índice válido para la tabla.
3. El elemento se almacena en la posición obtenida en el paso anterior. Si en dicha posición ya se encuentra otro elemento, se produce una colisión. Esto se soluciona asociando una lista a cada posición de la tabla, aplicando otra función o buscando otro elemento libre.

• Búsqueda

1. Para recuperar los datos, se necesita conocer la clave del elemento, a esto se le aplica la función resumen.
2. El valor que se obtiene se manda al espacio de direcciones de la tabla.
3. Si este elemento tiene la misma clave empleada en la búsqueda, entonces es el que buscamos. Si la clave es distinta, se tiene que buscar el elemento por el método empleado para resolver el problema de las colisiones al almacenar el elemento.

Para tener un buen rendimiento de una tabla hash es necesario una buena función hash. Las colisiones son resueltas por algún tipo de búsqueda lineal.





Las funciones hash más utilizadas son:

• Hash de División.

• Hash de Multiplicación.

Si dos claves generan un hash apuntando hacia el mismo índice, los registros no pueden almacenarse en la misma posición. Así que cuando una casilla ya está ocupada, se debe buscar otra ubicación para almacenar el nuevo elemento.


 
Espero que les sirva:)