Hashing lineal

El hashing lineal (en inglés: linear hashing) es un algoritmo dinámico de tabla hash inventado por Witold Litwin (1980),​​ y más tarde popularizado por Paul Larson. El hashing lineal permite la expansión de la tabla hash un espacio a la vez.

La frecuente expansión de solo un espacio puede controlar de manera muy eficaz la cantidad de colisión de cadenas. El costo de la expansión de una tabla hash se propaga por cada operación de inserción en la tabla hash, en lugar de ser incurridos todos a la vez,​ por lo tanto, el hashing' lineal es muy adecuado para aplicaciones interactivas.

Detalles del algoritmo

En primer lugar, la tabla hash inicial se configura con un número arbitrario de cubos. De los siguientes valores debe mantenerse un registro:

• $N$: El número inicial de cubos.
• $L$: El nivel actual, que es un número entero que indica en una escala logarítmica aproximadamente cuántos cubos la tabla ha crecido. Este es en un principio $0$.
• $S$: Un puntero que apunta a un cubo. Inicialmente apunta a la primera cubeta en la tabla.

Las colisiones de los cubos pueden ser manejados en una variedad de maneras, pero es típico de tener espacio para dos elementos de cada cubo y añadir más cubos cada vez que un cubo se desborda. Más de dos elementos pueden ser utilizados una vez que se depura la aplicación. Las direcciones se calculan de la siguiente manera:

• Aplicar una función hash para la clave y llamar al resultado $H$.
• Si $Hmod(N*2^{L})$ es una dirección que viene antes de $S$, la dirección es $Hmod(N*2^{L+1})$.
• Si $Hmod(N*2^{L})$ es $S$ o una dirección que viene después de $S$, la dirección es $Hmod(N*2^{L})$.

Para agregar un cubo:

• Asignar un nuevo cubo al final de la tabla.
• Si $S$ apunta al $N*2^{L}$ º cubo en la tabla, resetear $S$ e incrementa $L$.
• De lo contrario incrementar $S$.

El efecto de todo esto es que la tabla se divide en tres secciones; la sección antes de $S$, la sección de $S$ a $N*2^{L}$, y la sección después de $N*2^{L}$. Las primeras y últimas secciones se almacenan utilizando $Hmod(N*2^{L})$ y la sección central se almacena utilizando $Hmod(N*2^{L})$. Cada vez que $S$ alcances $N*2^{L}$ de la tabla se ha duplicado en tamaño.

Puntos para reflexionar

• Cubos llenos no necesariamente se separaron y se requiere un espacio de contención para cubos con desbordamiento temporal. En almacenamiento externo, esto podría significar un segundo archivo.
• No se dividen necesariamente todos los cubos
• Cada cubo se dividirá tarde o temprano, y así todos los desbordamientos se recuperarán.
• El puntero para la división s decide qué balde dividir
  • s es independiente del cubo desbordado
  • A nivel i, s es entre 0 y 2 ^ i
  • S se incrementa y si está al final, se pone a 0.
  • Desde que un cubo en s se divide entonces s se incrementa, solo los cubos antes de s tienen el segundo espacio de hash duplicado.
  • Un buen número seudo aleatorio x grande se obtiene primero, y luego es bit- enmascarado con (2 ^ i) -1 o (2 ^ (i + 1)) -1, pero este último solo se aplica si x fue bit-enmascarado antes con (2 ^ i) - 1 y es menor que S, por lo que la gama más amplia de valores de hash solo se aplican a cubos que ya han sido divididos.
  • Ejem. Para bit-enmascarar un número, utilice x & 0111, en donde & es el operador AND, 111 es binario 7, donde 7 = 8 - 1 y 8 es 2 ^ 3 y i = 3.
  • ¿Y si s aterriza en un cubo que tiene 1 o más cubos completamente desbordados? La división solo reducirá el número de cubo desbordados por 1, y los cubos de desbordamiento restantes tendrán que ser recreados para ver cuál de los nuevos 2 cubos, o a sus cubos de desbordados, las entradas de los desbordados pertenecen.
• H _i (k) = h (k) mod (2 ^ i n)
• H _{i + 1} duplica el rango de h _i

Algoritmo para insertar 'k' y comprobar la condición de desbordamiento

• B = h ₀ (k)
• Si b <puntero de división entonces
• B = h ₁ (k)

Buscando en la tabla hash para 'k'

• B = h ₀ (k)
• Si b <puntero de división entonces
• B = h ₁ (k)
• Leer balde b y buscar allí

Adopción en sistemas de lenguaje

Griswold y Townsend​ comentaron sobre la adopción del hashing lineal en el lenguaje de programación Icon. Hablaron de las alternativas de implementación de matriz dinámica algoritmo utilizado en el hashing lineal, y presentaron comparaciones de rendimiento utilizando una lista de Icon de aplicaciones de referencia.

Adopción en sistemas de bases de datos

El hashing lineal se utiliza en el sistema de base de datos de Berkeley, que a su vez es utilizado por muchos sistemas de software como OpenLDAP, utilizando una aplicación C derivado del artículo MCCA y publicado por primera vez en Usenet en 1988 por Esmond Pitt.

Enlaces externos

• TommyDS, implementación en C de una tabla hash lineal (en inglés)
• Implementación en Go en memoria, con explicación (en inglés)
• A C ++ Implementación de una tabla hash lineal compatible tanto con almacenamiento en sistema de ficheros como con almacenamiento en memoria (en inglés)

• Datos: Q6553456