Fundamentos del Hashing: Optimización del Almacenamiento y Recuperación de Datos

Fundamentos del Hashing: Parámetros Esenciales y Soluciones a Problemas Comunes

El método de dispersión (hashing) presenta cuatro parámetros esenciales que definen su comportamiento:

• Función de hash: Algoritmo que transforma una clave en una dirección de almacenamiento.
• Tamaño de cada nodo de almacenamiento: Capacidad de los contenedores de datos.
• Densidad de empaquetamiento: Proporción de espacio utilizado en el archivo.
• Métodos de tratamiento de overflow: Estrategias para manejar el desbordamiento de datos.

La Función de Hash

Una función de hash es una caja negra que, a partir de una clave, obtiene la dirección donde debe estar el registro. Se diferencia de los índices en varios aspectos clave:

• En la dispersión, no hay una relación aparente entre la clave y la dirección.
• Dos claves distintas pueden transformarse en la misma dirección, generando claves sinónimas.

Conceptos Clave: Colisión y Overflow

Colisión:

Situación en la que un registro es asignado a una dirección que ya está utilizada por otro registro.

Overflow:

Situación en la que un registro es asignado a una dirección en la cual no queda espacio para alojarlo.

Soluciones a Colisiones y Overflow

Idealmente, se buscarían algoritmos de dispersión sin colisiones o que estas colisiones nunca produzcan overflow (conocidos como algoritmos perfectos), aunque son imposibles de conseguir en la práctica general.

La solución más común es almacenar los registros de alguna otra forma, esparciéndolos. Las principales estrategias incluyen:

• Esparcir registros: Buscar métodos que distribuyan los registros de la forma más aleatoria y uniforme posible.
• Usar memoria adicional: Distribuir pocos registros en muchas direcciones. Esto tiene las siguientes implicaciones:
  • Disminuye las colisiones y, por ende, el overflow.
  • Desperdicia espacio de almacenamiento.
• Colocar más de un registro por dirección: Direcciones con N claves permiten mejoras notables en la eficiencia.
  • Ejemplo: Si un archivo tiene registros físicos de 512 bytes y el registro a almacenar es de 80 bytes, se pueden almacenar hasta 6 registros por cada dirección de archivo.
  • Cada dirección tolera hasta 5 sinónimos en este caso.
  • Las direcciones que pueden almacenar varios registros de esta forma se denominan nodos, cubetas o compartimentos.

Algoritmos Simples de Dispersión

Para que un algoritmo de dispersión sea eficiente, debe cumplir ciertas condiciones:

• Repartir registros de forma uniforme.
• Ser aleatorio (las claves son independientes y no influyen una sobre la otra).

Pasos para Aplicar una Función de Dispersión

1. Representar la clave en forma numérica (en caso de que no lo sea).
2. Aplicar la función de dispersión.
3. Relacionar el número resultante con el espacio disponible.

Ejemplos de Funciones de Dispersión

• Centros cuadrados: La clave se multiplica por sí misma, y tomando los dígitos centrales del resultado, se ajusta posteriormente al espacio disponible.
• División: La clave se divide por un número aproximadamente igual al número de direcciones. Un número primo tiende a distribuir los residuos de forma más eficiente.
• Desplazamiento: Los dígitos externos de ambos extremos se desplazan hacia adentro, se suman y el resultado se ajusta al espacio disponible.

Tamaño de los Nodos, Cubetas o Compartimentos

Estos contenedores pueden almacenar más de un registro. Un mayor tamaño de nodo implica:

• Menor probabilidad de colisión.
• Mayor fragmentación interna.
• Búsqueda potencialmente más lenta dentro de la cubeta (¿afecta esto significativamente al rendimiento global?).

Densidad de Empaquetamiento

La densidad de empaquetamiento (DE) es la proporción de espacio del archivo asignado que en realidad almacena registros. Se calcula como:

DE = (Número de registros del archivo) / (Capacidad total del archivo)

Una menor densidad de empaquetamiento conlleva:

• Menos overflow.
• Más desperdicio de espacio.