Tablas de dispersión

Laboratorio de Lenguajes de Programación

Una tabla de dispersión 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 implementar inserciones, y eliminaciones. También son llamadas tablas hash o en inglés (hashing tables).

Estas tables se utilizan normalmente sobre vectores de una dimensión, aunque también se pueden utilizar en vectores multidimensionales. Comparándolas con los arreglos, las tablas hash son más útiles cuando tienes que almacenar grandes cantidades de elementos.

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

• Un vector con dirección mediante un número de posición que pueda almacenar n elementos.
  
• Una función de dispersión la cual nos permita a partir de una clave, obtener el índice donde está el dato con dicha clave.
  
• Una función de resolución de colisiones.

Las operaciones básicas que se utilizan en las tablas hash son: 

          inserción(clave, valor)

          búsqueda(clave) que devuelve valor

También la mayoría de estas implementaciones incluyen borrar(clave), así como también iteración en la tabla, crecimiento y vaciado.

Inserción

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 otrá 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.

Ventajas y desventajas

La principal ventaja de utilizar estas tablas es el acceso rápido a los datos almacenados, siempre y cuando se cumpla lo siguiente:

• Una no muy elevada razón de ocupación
• La función resumen debe distribuir uniformemente las claves, si esta función esta mal, se producirán muchas colisiones.

Las desventajas de estas tablas son:

• Se tiene que ampliar el espacio de la tabla si el volumen de datos que se almacenaron crece. 
• Es dificil recorrer todos los elementos, casi siempre se usan listas para procesar los elementos.
• Si reservas el espacio para todos los posibles elementos, se consume más memoria de la necesaria. Esto se puede resolver reservando solo el espacio para punteros a los elementos.

En la siguiente imagen se muestra un ejemplo de como se ven las tablas de dispersión.

Bueno esto es todo lo que investigué acerca de las tablas de dispersión, espero que les sirva cualquier duda ya saben que me la pueden hacer saber:) saludos.