El hash lineal ( LH ) es una estructura de datos dinámica que implementa una tabla hash y aumenta o reduce un depósito 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 varios esquemas conocidos como hash dinámico [3] [4] como el hash lineal con extensiones parciales de Larson, [5] el hash lineal con división de prioridad, [6] el hash lineal con expansiones parciales y prioridad División, [7] o hash lineal recursivo. [8]
La estructura de archivos de una estructura de datos hash dinámica 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 al dividir un depósito predeterminado en dos y se contrae al fusionar dos depósitos predeterminados en uno. El desencadenante de una reconstrucción depende del estilo del esquema; podría ser un desbordamiento en un cubo o un factor de carga (número de registros sobre el número de cubos) que se mueve fuera de un rango predeterminado. [1]
El hash lineal también se ha convertido en una estructura de datos distribuida escalable, LH * . En LH *, cada depósito reside en un servidor diferente. [9] El propio LH * se ha ampliado para proporcionar disponibilidad de datos en presencia de depósitos 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 cubos y, por lo tanto, de registros. [1] [10]
Detalles del algoritmo
Los registros en LH o LH * constan de una clave y un contenido, este último básicamente todos los demás atributos del registro. [1] [10] Se almacenan en cubos. Por ejemplo, en la implementación de Ellis, un depósito es una lista vinculada de registros. [2] El archivo permite que las operaciones CRUD basadas en claves creen o inserten, lean, actualicen y eliminen, así como operaciones de escaneo que escanean todos los registros, por ejemplo, para hacer una operación de selección de base de datos en un atributo que no es clave. [10] Los registros se almacenan en depósitos cuya numeración comienza con 0. [10]
Funciones hash
Para acceder a un registro con clave , una familia de funciones hash, llamadas colectivamente una función hash dinámica que se aplica a la clave . En cualquier momento, como máximo dos funciones hash y son usados. Un ejemplo típico usa la operación de división módulo x. Si el número original de cubetas es, entonces la familia de funciones hash es [10]
Expansión de archivos
A medida que el archivo crece a través de inserciones, se expande con gracia al dividir un depósito en dos depósitos. La secuencia de cubetas para dividir está predeterminada. Esta es la diferencia fundamental con esquemas como el hash extensible de Fagin. [11] Para los dos nuevos depósitos, la función hash es reemplazado por . El número del depósito que se dividirá es parte del estado del archivo y se denomina puntero dividido.. [10]
Control dividido
Se puede realizar una división siempre que se desborde un cubo. Esta es una división incontrolada. Alternativamente, el archivo puede monitorear el factor de carga y realiza una división cada vez que el factor de carga excede un umbral. Esto fue una división controlada. [10]
Direccionamiento
El direccionamiento se basa en el estado del archivo, que consta del puntero dividido y el nivel . Si el nivel es, entonces las funciones hash utilizadas son y .
El algoritmo LH para la clave hash es [10]
Si
Terrible
Cuando se divide un cubo, el puntero de división y posiblemente el nivel se actualizan de acuerdo con [10]
Si :
Contracción de archivo
Si la división bajo control, el factor de carga desciende por debajo de un umbral, se activa una operación de combinación. La operación de combinación deshace la última división y también restablece el estado del archivo. [10]
Cálculo del estado del archivo
El estado del archivo consta de puntero dividido y nivel . Si el archivo original comenzaba con cubos, luego el número de cubos y el estado del archivo están relacionados a través de [12]
LH *
La principal contribución de LH * es permitir que un cliente de un archivo LH * encuentre el depósito 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 depósito, a saber, el depósito 0. Según el estado de su archivo, un cliente calcula la dirección de una clave y envía una solicitud a ese depósito. En el depósito, se comprueba la solicitud y, si el registro no está en el depósito, se reenvía. En un sistema razonablemente estable, es decir, si solo hay una división o fusión mientras se procesa la solicitud, se puede demostrar que hay como máximo dos reenvíos. Después de un reenvío, el depósito final envía un mensaje de ajuste de imagen al cliente cuyo estado ahora está más cerca del estado del archivo distribuido. [10] Si bien los reenvíos son bastante raros para los clientes activos, su número puede reducirse aún más mediante el intercambio de información adicional entre servidores y clientes [12]
Adopción en sistemas lingüísticos
Griswold y Townsend [13] discutieron la adopción del hash lineal en el lenguaje Icon . Discutieron las alternativas de implementación del algoritmo de matriz dinámica utilizado en el 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 de Berkeley (BDB) , que a su vez es utilizado por muchos sistemas de software como OpenLDAP, utilizando una implementación de C derivada del artículo CACM y publicado por primera vez en Usenet en 1988 por Esmond Pitt.
Referencias
- ^ a b c d Litwin, Witold (1980), "Hash lineal: una nueva herramienta para el direccionamiento de archivos y tablas" (PDF) , Proc. Sexta conferencia sobre bases de datos muy grandes : 212–223
- ^ a b Ellis, Carla Schlatter (junio de 1987), "Concurrencia en el hash lineal", ACM Transactions on Database Systems , 12 (2): 195-217
- ^ a b Baeza-Yates, Ricardo; Soza-Pollman, Hector (1998), "Analysis of Linear Hashing Revised" (PDF) , Nordic Journal of Computing : 70–85, archivado desde el original (PDF) el 7 de marzo de 2019
- ^ a b Enbody, Richard; Du, HC (junio de 1988), "Esquemas de hash dinámico", Encuestas de computación de ACM , 20 (2): 85-113
- ^ Larson, Per-Åke (abril de 1988), "Dynamic Hash Tables", Communications of the ACM , 31 (4): 446–457, doi : 10.1145 / 42404.42410
- ^ 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 de Ingeniería de Datos de IEEE : 2-9
- ^ Manolopoulos, Yannis; Lorentzos, N. (1994), "Rendimiento de esquemas de hash lineal para la recuperación de claves primarias", Information Systems , 19 (5): 433–446
- ^ Ramamohanarao, K .; Sacks-Davis, R. (septiembre de 1984), "Hash lineal recursivo", ACM Transactions on Databases , 9 (3): 369–391
- ^ Litwin, Witold; Neimat, Marie-Anne; Schneider, Donavan A. (1993), "Hashing lineal para archivos distribuidos", Actas SIGMOD 93 Conferencia internacional sobre gestión de datos : 327–336
- ^ a b c d e f g h yo j k l Litwin, Witold; Moussa, Rim; Schwarz, Thomas (septiembre de 2005), "LH * RS: una estructura de datos distribuida escalable de alta disponibilidad", ACM Transactions on Database Systems , 30 (3): 769–811
- ^ Fagin, Ronald; Nievergelt, Jurg; Pippenger, Nicholas; Strong, Raymond (septiembre de 1979), "Hash extensible: un método de acceso rápido para archivos dinámicos", Transacciones de ACM en sistemas de bases de datos , 4 (2): 315–344
- ^ a b Chabkinian, Juan; Schwarz, Thomas (2016), "Fast LH *", Revista Internacional de Programación Paralela , 44 (4): 709–734
- ^ Griswold, William G .; Townsend, Gregg M. (abril de 1993), "El diseño e implementación de hash dinámico para conjuntos y tablas en Icon" , Software: práctica y experiencia , 23 (4): 351–367
enlaces externos
- Implementación de TommyDS, C de un Hashtable lineal
- Una implementación en Memory Go con explicación
- Una implementación en C ++ de Hashtable lineal que admite tanto el sistema de archivos como el almacenamiento en memoria
Ver también
- Hash extensible
- Hash consistente