¿Qué es la densidad de embalaje en hashing?

Es la relación entre el número de registros del archivo y la capacidad total de las cubetas, calculada como DE = R / (C × N). Indica qué tan llena está la estructura.

¿Cómo funciona la saturación progresiva?

Cuando un nodo se completa, el sistema busca el próximo nodo disponible hasta encontrar uno libre. Es importante que la eliminación de registros no dificulte las búsquedas posteriores.

¿Qué ventaja tiene el hashing dinámico frente al estático?

El hashing dinámico permite reorganizar tablas sin mover gran cantidad de registros y usa bloques físicos que pueden asignarse o liberarse según la necesidad. El estático requiere un número fijo de direcciones, lo que dificulta el crecimiento del sistema.

Gestión de colisiones, overflow y hashing dinámico (hash extensible)

Resumen

El documento explica cómo estimar el desbordamiento (overflow) en tablas hash y las principales técnicas para tratar las colisiones, como la saturación progresiva, la doble dispersión y el encadenamiento en áreas separadas. También compara el hashing estático con el dinámico y describe el funcionamiento del hash extensible. Al final, recoge criterios para elegir la organización de archivos según el tipo de archivo, las operaciones y el hardware.

Puntos clave

La densidad de embalaje se calcula como DE = R / (C × N), donde R son los registros, C la capacidad del nodo y N el número de cubetas.
La probabilidad de que una cubeta reciba I registros se estima con la distribución de Poisson.
La saturación progresiva busca el siguiente nodo libre cuando uno se completa.
La doble dispersión aplica una segunda función a la llave y suma el resultado a la dirección original hasta encontrar espacio libre.
El encadenamiento en áreas separadas mejora inserciones y eliminaciones, pero empeora el tiempo de acceso promedio (TAP).
En el hash extensible, la tabla tiene 2^i entradas, donde i es el número de bits actualmente usados.

Ponte a prueba

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

Se utilizan solo los bits necesarios de acuerdo con la instancia actual del archivo.
Los bits tomados forman la dirección del nodo que se utilizará.
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.
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).