Tablas de Dispersión
Las tablas de dispersión o hashing tables (en inglés) es una técnica que se utiliza para implementar inserciones, eliminaciones y búsquedas en un tiempo medio constante.
La estructura de datos central de esta técnica es la tabla de hashing (tabla de dispersión.)
Planteamiento inicial
La estructura de datos ideal para la tabla de dispersión es un arreglo de tamaño fijo que contiene las claves (elementos de la tabla). Una clave suele ser una cadena de caracteres (o de números) con un valor asociado Si el tamaño de la tabla es MAX_T, la tabla se declara entre 0 y MAX_T-1. A cada clave se le hará corresponder un número entre 0 y MAX_T-1 y se colocará en la celda correspondiente.
La relación entre la llave y la posición en la tabla es lo que se llama función de dispersión.
Las operaciones básicas implementadas en las tablas hash son:
Inserción (llave, valor)
Búsqueda (llave) que devuelve valor
La mayoría de las implementaciones también incluyen borrar(llave). También se pueden ofrecer funciones como iteración en la tabla, crecimiento y vaciado. Algunas tablas hash permiten almacenar múltiples valores bajo la misma clave.
Para usar una tabla hash se necesita:
- Una estructura de acceso directo (normalmente un array).
- Una estructura de datos con una clave
- Una función resumen (hash) cuyo dominio sea el espacio de claves y su imagen (o rango) los números naturales.
Inserción
- Para almacenar un elemento en la tabla hash se ha de convertir su clave a un número. Esto se consigue aplicando la función resumen (hash) a la clave del elemento.
- El resultado de la función resumen ha de mapearse al espacio de direcciones del arreglo que se emplea como soporte, lo cual se consigue con la función módulo. Tras este paso se obtiene un índice válido para la tabla.
- El elemento se almacena en la posición de la tabla obtenido en el paso anterior.
- Si en la posición de la tabla ya había otro elemento, se ha producido una colisión. Este problema se puede solucionar asociando una lista a cada posición de la tabla, aplicando otra función o buscando el siguiente elemento libre. Estas posibilidades han de considerarse a la hora de recuperar los datos.
Búsqueda
- Para recuperar los datos, es necesario únicamente conocer la clave del elemento, a la cual se le aplica la función resumen.
- El valor obtenido se mapea al espacio de direcciones de la tabla.
- Si el elemento existente en la posición indicada en el paso anterior tiene la misma clave que la empleada en la búsqueda, entonces es el deseado. Si la clave es distinta, se ha de buscar el elemento según la técnica empleada para resolver el problema de las colisiones al almacenar el elemento.
Ventajas e inconvenientes de las tablas hash
Una tabla hash tiene como principal ventaja que el acceso a los datos suele ser muy rápido si se cumplen las siguientes condiciones:
- Una razón de ocupación no muy elevada (a partir del 75% de ocupación se producen demasiadas colisiones y la tabla se vuelve ineficiente).
- Una función resumen que distribuya uniformemente las claves. Si la función está mal diseñada, se producirán muchas colisiones.
Los inconvenientes de las tablas hash son:
- Necesidad de ampliar el espacio de la tabla si el volumen de datos almacenados crece. Se trata de una operación costosa.
- Dificultad para recorrer todos los elementos. Se suelen emplear listas para procesar la totalidad de los elementos.
- Desaprovechamiento de la memoria. Si se reserva espacio para todos los posibles elementos, se consume más memoria de la necesaria; se suele resolver reservando espacio únicamente para punteros a los elementos.
Bien; 7.
ResponderEliminar