Hashing lineal

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 deben 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]

Detalles del algoritmo

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]

Funciones hash

La función hash devuelve el índice basado en 0 del depósito que contiene el registro con la 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. $h_{i}(c)$ ${\estilo de visualización c}$ $estilo de visualización h_{i}}$ $estilo de visualización h_{i}}$ $estilo de visualización h_{i+1}}$ $estilo de visualización h_{l}}$ $estilo de visualización h_{l+1}}$ ${\estilo de visualización l}$ $h_{i}(c)$

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, . ${\estilo de visualización i}$ $estilo de visualización h_{i}}$ ${\estilo de visualización c}$ ${\textstyle h_{i}(c)\mapsto (c{\bmod {2}}^{i})}$ $i=0$

Complete los cálculos a continuación para determinar la función hash correcta para la clave hash dada . ^[10] ${\estilo de visualización c}$

# 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 )

Control dividido

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]

Puntero dividido

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] ${\estilo de visualización s}$ $estilo de visualización h_{l}}$ $estilo de visualización h_{l+1}}$

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

LH*

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] .}

Otras propiedades

Cálculo del estado del archivo

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] ${\estilo de visualización s}$ ${\estilo de visualización l}$ ${\estilo de visualización N=1}$ ${\estilo de visualización n}$

$n=2^{l}+s$ .

Adopción en sistemas lingüísticos

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.

Adopción en sistemas de bases de datos

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.

Referencias

^ abcd Litwin, Witold (1980), "Hash lineal: una nueva herramienta para el direccionamiento de archivos y tablas" (PDF) , Proc. 6th Conference on Very Large Databases : 212–223
^ ab Ellis, Carla Schlatter (junio de 1987), "Concurrencia en hash lineal", ACM Transactions on Database Systems , 12 (2): 195–217, doi : 10.1145/22952.22954 , S2CID 14260177
^ ab Baeza-Yates, Ricardo; Soza-Pollman, Hector (1998), "Análisis de hash lineal revisado" (PDF) , Nordic Journal of Computing : 70–85, S2CID 7497598, archivado desde el original (PDF) el 2019-03-07
^ ab Enbody, Richard; Du, HC (junio de 1988), "Esquemas de hash dinámicos", ACM Computing Surveys , 20 (2): 85–113, doi : 10.1145/46157.330532 , S2CID 1437123
^ ab Larson, Per-Åke (abril de 1988), "Tablas hash dinámicas", Communications of the ACM , 31 (4): 446–457, doi : 10.1145/42404.42410 , S2CID 207548097
^ Ruchte, Willard; Tharp, Alan (febrero de 1987), "Hash lineal con división de prioridad: un método para mejorar el rendimiento de recuperación del hash lineal", Tercera Conferencia Internacional sobre Ingeniería de Datos del IEEE : 2–9
^ Manolopoulos, Yannis; Lorentzos, N. (1994), "Rendimiento de esquemas de hash lineales para la recuperación de claves primarias", Information Systems , 19 (5): 433–446, doi :10.1016/0306-4379(94)90005-1
^ Ramamohanarao, K.; Sacks-Davis, R. (septiembre de 1984), "Hash lineal recursivo", ACM Transactions on Databases , 9 (3): 369–391, doi : 10.1145/1270.1285 , S2CID 18577730
^ Litwin, Witold; Neimat, Marie-Anne; Schneider, Donavan A. (1993), "LH: Hashing lineal para archivos distribuidos", ACM SIGMOD Record , 22 (2): 327–336, doi :10.1145/170036.170084, S2CID 259938726
^ abcdefghijk Litwin, Witold; Moussa, Rim; Schwarz, Thomas (septiembre de 2005), "LH*RS: una estructura de datos distribuida escalable y de alta disponibilidad", ACM Transactions on Database Systems , 30 (3): 769–811, doi :10.1145/1093382.1093386, S2CID 1802386
^ Fagin, Ronald; Nievergelt, Jurg; Pippenger, Nicholas; Strong, Raymond (septiembre de 1979), "Hash extensible: un método de acceso rápido para archivos dinámicos", ACM Transactions on Database Systems , 4 (2): 315–344, doi :10.1145/320083.320092, S2CID 2723596
^ ab Silberschatz, Abraham; Korth, Henry F.; Sudarshan, S. (2020). Conceptos de sistemas de bases de datos (séptima edición). Nueva York, NY: McGraw-Hill Education. ISBN 978-1-260-08450-4.
^ ab Chabkinian, Juan; Schwarz, Thomas (2016), "Fast LH*", Revista internacional de programación paralela , 44 (4): 709–734, doi :10.1007/s10766-015-0371-8, S2CID 7448240
^ Griswold, William G. ; Townsend, Gregg M. (abril de 1993), "El diseño y la implementación de hash dinámico para conjuntos y tablas en Icon", Software: Practice and Experience , 23 (4): 351–367, doi :10.1002/spe.4380230402, S2CID 11595927

Enlaces externos

TommyDS, implementación en C de una tabla hash lineal
Una implementación de Go en memoria con explicación
Una implementación en C++ de una tabla hash lineal que admite tanto el almacenamiento en memoria como en el sistema de archivos