Estrategias de Hashing Dinámico y Tratamiento de Colisiones (Overflow)

Gestión de Colisiones y Desbordamiento (Overflow) en Hashing

Estimación del Overflow

La estimación del desbordamiento (overflow) se realiza considerando los siguientes parámetros:

• N: Número de cubetas.
• C: Capacidad del nodo.
• R: Número de registros del archivo.
• Densidad de Embalaje (DE): $DE = \frac{R}{C \times N}$

La probabilidad de que una cubeta reciba $I$ registros se calcula mediante la distribución de Poisson.

Tratamiento de Colisiones con Overflow

Aunque el porcentaje de overflow se reduce con ciertas técnicas, el problema persiste, ya que es difícil alcanzar un 0%. Algunos métodos comunes para el tratamiento de colisiones son:

• Saturación progresiva.
• Saturación progresiva encadenada.
• Doble dispersión.
• Área de desborde separado.

Saturación Progresiva

Cuando un nodo se completa, se busca el próximo nodo disponible hasta encontrar uno libre. Es crucial que el proceso de eliminación no obstaculice las búsquedas posteriores.

Saturación Progresiva Encadenada

Similar a la saturación progresiva, pero los registros de desbordamiento se encadenan y no ocupan necesariamente posiciones contiguas.

Doble Dispersión (Double Hashing)

La saturación tiende a agrupar registros en zonas contiguas, lo que resulta en búsquedas largas cuando la densidad de embalaje se acerca a uno. La solución es almacenar los registros de overflow en zonas no relacionadas.

Este esquema resuelve los desbordamientos aplicando una segunda función a la llave para producir un número $C$, el cual se suma a la dirección original tantas veces como sea necesario hasta encontrar una dirección con espacio disponible.

Encadenamiento en Áreas Separadas

Esta técnica no utiliza nodos de direcciones para el overflow; los registros desbordados se dirigen a nodos especiales.

• Mejora el tratamiento de inserciones o eliminaciones.
• Empeora el TAP (Tiempo de Acceso Promedio).

Ubicación del Desborde

• A intervalos regulares entre direcciones asignadas.
• Cilindros de desborde.

Hashing Estático vs. Hashing Dinámico

Hashing con Espacio de Direccionamiento Estático

Requiere un número de direcciones fijas, lo cual es virtualmente imposible de mantener en sistemas que crecen. Cuando el archivo se llena, se produce una saturación excesiva, lo que obliga a redispersar (aplicar una nueva función), generando muchos cambios.

Solución: Espacio de Direccionamiento Dinámico

El hashing dinámico permite:

• Reorganizar tablas sin mover una gran cantidad de registros.
• Utilizar técnicas que asumen bloques físicos que pueden ser utilizados o liberados según la necesidad.

Técnicas de Hashing Dinámico

Varias posibilidades dentro del espacio dinámico:

• Hash Virtual.
• Hash Dinámico.
• Hash Extensible.

Hash Extensible

Esta técnica adapta el resultado de la función de hash de acuerdo con el número de registros que contenga el archivo y las cubetas necesarias para su almacenamiento.

La función de hash genera una secuencia de bits (normalmente 32).

Funcionamiento del Hash Extensible

1. Se utilizan solo los bits necesarios de acuerdo con la instancia actual del archivo.
2. Los bits tomados forman la dirección del nodo que se utilizará.
3. Si se intenta insertar en una cubeta llena, deben reubicarse todos los registros contenidos entre el nodo viejo y el nuevo. Para lograr esto, se toma un bit adicional.
4. La tabla tendrá $2^i$ entradas (direcciones de nodos), donde $i$ es el número de bits actuales utilizados por el sistema.

Criterios para la Elección de la Organización de Archivos

Para seleccionar la organización de archivos más adecuada, es fundamental captar los requerimientos del usuario y examinar diversos factores:

Factores a Examinar

• Características del Archivo:
  • Número de registros.
  • Tamaño de los registros.
• Requerimientos del Usuario:
  • Tipos de operaciones (inserción, eliminación, búsqueda).
  • Número de accesos a archivos.
• Características del Hardware:
  • Tamaño de sectores, bloques, pistas, cilindros, etc.

Parámetros de Evaluación

• Tiempo: Necesario para desarrollar y mantener el software, y para procesar los archivos.
• Uso Promedio: (Número de registros usados / Número total de registros).