El hash lineal ( LH ) es una estructura de datos dinámica que implementa una tabla hash y crece o se reduce un contenedor a la vez. Fue inventado por Witold Litwin en 1980. [1] [2] Ha sido analizado por Baeza-Yates y Soza-Pollman. [3] Es el primero de una serie de esquemas conocidos como hash dinámico [3] [4] como el hash lineal de Larson con extensiones parciales, [5] el hash lineal con división de prioridad, [6] el hash lineal con expansiones parciales y división de prioridad, [7] o el hash lineal recursivo. [8]
La estructura de archivo de una estructura de datos de hash dinámico se adapta a los cambios en el tamaño del archivo, por lo que se evita la costosa reorganización periódica de archivos. [4] Un archivo de hash lineal se expande dividiendo un contenedor predeterminado en dos y se contrae fusionando dos contenedores predeterminados en uno. El desencadenante de una reconstrucción depende del tipo de esquema; podría ser un desbordamiento en un contenedor o un factor de carga (es decir, la cantidad de registros dividido por la cantidad de contenedores) que se mueve fuera de un rango predeterminado. [1] En el hash lineal hay dos tipos de contenedores, los que se van a dividir y los que ya están divididos. Mientras que el hash extensible divide solo los contenedores que se desbordan, el hash en espiral (también conocido como almacenamiento en espiral) distribuye los registros de manera desigual entre los contenedores, de modo que los contenedores con altos costos de inserción, eliminación o recuperación son los primeros en la fila para una división. [5]
El hash lineal también se ha convertido en una estructura de datos distribuida escalable, LH* . En LH*, cada contenedor reside en un servidor diferente. [9] El propio LH* se ha ampliado para proporcionar disponibilidad de datos en presencia de contenedores fallidos. [10] Las operaciones basadas en claves (inserciones, eliminaciones, actualizaciones, lecturas) en LH y LH* toman un tiempo constante máximo independientemente del número de contenedores y, por lo tanto, de registros. [1] [10]
Los registros en LH o LH* consisten en una clave y un contenido, este último básicamente todos los demás atributos del registro. [1] [10] Se almacenan en contenedores. Por ejemplo, en la implementación de Ellis, un contenedor es una lista enlazada de registros. [2] El archivo permite las operaciones CRUD basadas en claves de creación o inserción, lectura, actualización y eliminación, así como operaciones de escaneo que escanean todos los registros, por ejemplo, para realizar una operación de selección de base de datos en un atributo que no es clave. [10] Los registros se almacenan en contenedores cuya numeración comienza con 0. [10]
La distinción clave con respecto a esquemas como el hash extensible de Fagin es que, a medida que el archivo se expande debido a las inserciones, solo se divide un contenedor a la vez, y el orden en que se dividen los contenedores ya está predeterminado. [11]
La función hash devuelve el índice basado en 0 del depósito que contiene el registro con clave . Cuando un depósito que utiliza la función hash se divide en dos nuevos depósitos, la función hash se reemplaza por para ambos nuevos depósitos. En cualquier momento, se utilizan como máximo dos funciones hash y ; de modo que corresponda al nivel actual . La familia de funciones hash también se conoce como función hash dinámica.
Normalmente, el valor de in corresponde a la cantidad de dígitos binarios más a la derecha de la clave que se utilizan para separar los contenedores. Esta función hash dinámica se puede expresar aritméticamente como . Tenga en cuenta que cuando la cantidad total de contenedores es igual a uno, .
Complete los cálculos a continuación para determinar la función hash correcta para la clave hash dada . [10]
# l representa el nivel actual # s representa el índice del puntero de división a = h_l ( c ) si ( a < s ): a = h_ { l + 1 }( c )
Los algoritmos hash lineales pueden utilizar solo divisiones controladas o divisiones controladas y no controladas.
La división controlada se produce si se realiza una división cada vez que el factor de carga , que es monitoreado por el archivo, excede un umbral predeterminado. [10] Si el índice hash utiliza la división controlada, se permite que los contenedores se desborden mediante el uso de bloques de desbordamiento vinculados. Cuando el factor de carga supera un umbral establecido, el contenedor designado del puntero de división se divide. En lugar de utilizar el factor de carga, este umbral también se puede expresar como un porcentaje de ocupación, en cuyo caso, la cantidad máxima de registros en el índice hash es igual a (porcentaje de ocupación) * (máximo de registros por contenedor no desbordado) * (número de contenedores). [12]
Una división no controlada ocurre cuando se realiza una división cada vez que un depósito se desborda, en cuyo caso ese depósito se dividiría en dos depósitos separados.
En algunas implementaciones de algoritmos LH se produce una contracción de archivos si una división controlada hace que el factor de carga caiga por debajo de un umbral. En este caso, se activaría una operación de fusión que desharía la última división y restablecería el estado del archivo. [10]
El índice del siguiente contenedor que se dividirá forma parte del estado del archivo y se denomina puntero de división . El puntero de división corresponde al primer contenedor que utiliza la función hash en lugar de . [10]
Por ejemplo, si se insertan registros numéricos en el índice hash según sus dígitos binarios más a la derecha, el contenedor correspondiente al contenedor adjunto se dividirá. Por lo tanto, si tenemos los contenedores etiquetados como 000, 001, 10, 11, 100, 101, dividiríamos el contenedor 10 porque estamos agregando y creando el siguiente contenedor secuencial 110. Esto nos daría los contenedores 000, 001, 010, 11, 100, 101, 110. [12]
Cuando se divide un depósito, el puntero de división y posiblemente el nivel se actualizan de acuerdo con lo siguiente, de modo que el nivel es 0 cuando el índice hash lineal solo tiene 1 depósito. [10]
# l representa el nivel actual # s representa el índice del puntero dividido s = s + 1 si ( s >= 2 ^ l ): l = l + 1 s = 0
La principal contribución de LH* es permitir que un cliente de un archivo LH* encuentre el contenedor donde reside el registro incluso si el cliente no conoce el estado del archivo. De hecho, los clientes almacenan su versión del estado del archivo, que inicialmente es solo el conocimiento del primer contenedor, es decir, el contenedor 0. Según el estado de su archivo, un cliente calcula la dirección de una clave y envía una solicitud a ese contenedor. En el contenedor, se verifica la solicitud y, si el registro no está en el contenedor, se reenvía. En un sistema razonablemente estable, es decir, si solo hay una división o fusión en curso mientras se procesa la solicitud, se puede demostrar que hay como máximo dos reenvíos. Después de un reenvío, el contenedor final envía un mensaje de ajuste de imagen al cliente cuyo estado ahora es más cercano al estado del archivo distribuido. [10] Si bien los reenvíos son razonablemente raros para los clientes activos, su número se puede reducir aún más mediante un intercambio de información adicional entre servidores y clientes [13].
El estado del archivo consta de un puntero de división y un nivel . Si el archivo original comenzó con contenedores, entonces la cantidad de contenedores y el estado del archivo están relacionados a través de [13]
.
Griswold y Townsend [14] analizaron la adopción del algoritmo hash lineal en el lenguaje Icon . Analizaron las alternativas de implementación del algoritmo de matriz dinámica utilizado en el algoritmo hash lineal y presentaron comparaciones de rendimiento utilizando una lista de aplicaciones de referencia de Icon.
El hash lineal se utiliza en el sistema de base de datos Berkeley (BDB) , que a su vez es utilizado por muchos sistemas de software, utilizando una implementación de C derivada del artículo CACM y publicado por primera vez en Usenet en 1988 por Esmond Pitt.