Diferencia entre hash dinámico y estático

En una estructura de datos, el hashing es una técnica para asignar una gran cantidad de elementos de datos a tablas más pequeñas utilizando una función especial llamada función Hash para un acceso más rápido. A veces, la estructura de datos es tan grande que se vuelve casi imposible buscar todos los valores del índice a través de todos los niveles para acceder a un bloque final de datos. Aquí es donde el hashing entra en juego correctamente. Lo que hace es que calcula la ubicación de un registro de datos en el disco directamente sin usar la estructura de índice. La dirección de cada registro se determina mediante un algoritmo hash, que convierte un valor de clave principal en una dirección de registro. Por lo tanto, hay dos categorías de indexación disponibles mediante funciones hash: hash dinámico y hashing estático.

¿Qué es Hashing estático?

Static Hashing es un método hash en el que se asigna un número fijo de cubos a un archivo para almacenar los registros. El número de cubos está preasignado, por lo que cuando se proporciona un valor de clave de búsqueda, la función hash siempre calcula la misma dirección. Un archivo de página se puede ver como una colección de cubos, con una página principal y páginas de desbordamiento adicionales. Con hash estático, el mecanismo de ubicación es la función hash y no hay estructuras de datos involucradas. Aquí, las entradas de índice se aleatorizan de tal manera que el número de entradas de índice en cada cubo es aproximadamente el mismo. Sin embargo, este esquema también tiene ciertas desventajas. Si la cantidad inicial de depósitos es demasiado pequeña y el archivo crece, el rendimiento se degrada debido al desbordamiento del depósito. Por otro lado, si es demasiado grande, se asigna mucho espacio para el crecimiento esperado y se desperdicia una cantidad significativa de espacio.

¿Qué es Hashing Dinámico?

Por otro lado, Dynamic Hashing es una técnica que se utiliza para superar las limitaciones del hashing estático, como el desbordamiento del cubo. A diferencia del hashing estático, permite que la cantidad de depósitos cambie dinámicamente para acomodar el crecimiento o la contracción de los archivos de la base de datos. Permite que la función hash se modifique a pedido, lo cual es bueno para las bases de datos que crecen y se reducen de tamaño. A medida que se agregan y eliminan filas, cambia la cantidad de cubos en consecuencia para minimizar el desbordamiento del cubo. Incrusta dinámicamente el manejo de registros de desbordamiento en su espacio de despacho principal para evitar el manejo del depósito de desbordamiento. Los dos tipos de hashing dinámico comúnmente utilizados son hash lineal y hashing extensible. El hashing extensible es una técnica común que maneja el desbordamiento del depósito dividiendo un depósito por la mitad, distribuyendo los registros entre depósitos antiguos y nuevos. El hash lineal es otro tipo popular de hash dinámico que permite que un archivo hash crezca o se reduzca dinámicamente mediante la asignación de nuevos cubos.

Diferencia entre hash dinámico y estático

Técnica

– Static Hashing es un método hash en el que se asigna un número fijo de cubos a un archivo para almacenar los registros, lo que significa que utiliza una función hash en la que se fija el número de direcciones de cubo. Aquí, las entradas de índice se aleatorizan de tal manera que el número de entradas de índice en cada cubo es aproximadamente el mismo. Por otro lado, Dynamic Hashing permite que la cantidad de cubos cambie dinámicamente para adaptarse al crecimiento o reducción de los archivos de la base de datos.

Actuación

– Si la cantidad inicial de depósitos es demasiado pequeña y los archivos crecen, el rendimiento se degrada debido al desbordamiento del depósito. Por otro lado, si es demasiado grande, se asigna mucho espacio para el crecimiento esperado y se desperdicia una cantidad significativa de espacio. El hashing dinámico, por otro lado, permite que la función hash se modifique dinámicamente, lo cual es bueno para las bases de datos que crecen y se reducen de tamaño. A medida que se agregan y eliminan filas, cambia la cantidad de cubos en consecuencia para minimizar el desbordamiento del cubo.

Implementación

– El hashing estático utiliza una función hash fija para dividir el conjunto de todos los valores de clave de búsqueda posibles en subconjuntos y luego asigna cada subconjunto a un depósito. El hashing dinámico, por otro lado, utiliza el segundo paso del mapeo para determinar el depósito asociado con algún valor de búsqueda clave. El hashing estirable y lineal hace que este mapeo sea muy diferente.

Hashing dinámico frente a estático:

Resumen

El número de cubos se fija en un hash estático y los registros con diferentes valores de clave de búsqueda apuntan al mismo cubo, en cuyo caso puede producirse una colisión. Si necesita encontrar un registro específico en un depósito con muchas claves, debe buscar en todo el depósito secuencialmente. A veces, un cubo tiene más registros de los que puede contener. Entonces, en este caso, se deben invocar algunas técnicas de manejo de desbordamiento. En ese caso, se usa hash dinámico, que utiliza una función de cambio dinámico que permite que la cantidad de cubos asignados crezca y se reduzca en tamaño a medida que se agregan y eliminan filas. Maneja explícitamente el desbordamiento del depósito al anidar dinámicamente los registros de desbordamiento en su dirección principal.