Hashing llineal

El hashing llineal (en inglés: linear hashing) és un algoritme dinàmic de taula hash inventat per Witold Litwin (1980), i més vesprada popularisat per Paul Larson. El hashing llineal permet l'expansió de la taula hash un espai al mateix temps.

La freqüent expansió de solament un espai pot controlar de manera molt eficaç la cantitat de colisió de cadenes. El cost de l'expansió d'una taula hash es propaga per cada operació d'inserció en la taula hash, en lloc de ser incorreguts tots al mateix temps, per lo tant, el hashing' llineal és molt adequat per a aplicacions interactives.

Detalls de l'algoritme

En primer lloc, la taula hash inicial es configura en un número arbitrari de gavetes. Dels següents valors deu mantindre's un registre:

• $N$: El número inicial de gavetes.
• $L$: El nivell actual, que és un número entero que indica en una escala logarítmica aproximadament quantes gavetes la taula ha creixcut. Est és en un principi $0$.
• $S$: Una busca que apunta a una gaveta. Inicialment apunta a la primera cubeta en la taula.

Les colisions de les gavetes poden ser manejats en una varietat de maneres, pero és típic de tindre espai per a dos elements de cada gaveta i afegir més gavetes cada volta que una gaveta es desborda. Més de dos elements poden ser utilisats una volta que es depura l'aplicació. Les direccions es calculen de la següent manera:

• Aplicar una funció hash per a la clau i cridar al resultat $H$.
• Si $Hmod(N*2^L)$ és una direcció que ve abans de $S$, la direcció és $Hmod(N*2^{L+1})$.
• Si $Hmod(N*2^L)$ és $S$ o una direcció que ve despuix de $S$, la direcció és $Hmod(N*2^L)$.

Per a agregar una gaveta:

• Assignar una nova gaveta al final de la taula.
• Si $S$ apunta a el $N*2^L$ º gaveta en la taula, resetear $S$ i incrementa $L$.
• De lo contrari incrementar $S$.

L'efecte de tot açò és que la taula es dividix en tres seccions; la secció abans de $S$, la secció de $S$ a $N*2^L$, i la secció despuix de $N*2^L$. Les primeres i últimes seccions s'almagasenen utilisant $Hmod(N*2^L)$ i la secció central s'almagasena utilisant $Hmod(N*2^L)$. Cada volta que $S$ alcanç $N*2^L$ de la taula s'ha duplicat en tamany.

Punts per a reflexionar

• Gavetes plenes no necessàriament es varen separar i es requerix un espai de contenció per a gavetes en desbordament temporal. En almagasenament extern, açò podria significar un segon archiu.
• No es dividixen necessàriament totes les gavetes
• Cada gaveta es dividirà vesprada o enjorn, i aixina tots els desbordament es recuperaran.
• La busca per a la divisió s decidix qué balde dividir
  • s és independent de la gaveta desbordada
  • A nivell i, s és entre 0 i 2 ^ i
  • S s'incrementa i si està al final, es posa a 0.
  • Des de que una gaveta en s es dividix llavors s s'incrementa, solament les gavetes abans de s tenen el segon espai de hash duplicat.
  • Un bon número seudo aleatori x gran s'obté primer, i despuix és bit- emmaixquerat en (2 ^ i) -1 o (2 ^ (i + 1)) -1, pero este últim solament s'aplica si x va ser bit-emmaixquerat abans en (2 ^ i) - 1 i és menor que S, per lo que la gama més àmplia de valors de hash solament s'apliquen a gavetes que ya han segut dividits.

• • Ejem. Per a bit-emmaixquerar un número, utilise x & 0111, en a on & és l'operador AND, 111 és binari 7, a on 7 = 8 - 1 i 8 és 2 ^ 3 i i = 3.
  • ¿I si s aterrisa en una gaveta que té 1 o més gavetes completament desbordats? La divisió solament reduirà el número de gaveta desbordats per 1, i les gavetes de desbordament restants tindran que ser recreats per a vore quin dels nous 2 gavetes, o a les seues gavetes de desbordats, les entrades dels desbordats pertanyen.
• H _i (k) = h (k) mod (2 ^ i n)
• H _{i + 1} duplica el ranc d'h _i

Algoritme per a insertar 'k' i comprovar la condició de desbordament

• B = h ₀ (k)
• Si b <busca de divisió llavors
• B = h ₁ (k)

Buscant en la taula hash per a 'k'

• B = h ₀ (k)
• Si b <busca de divisió llavors
• B = h ₁ (k)
• Llegir balde b i buscar allí

Adopció en sistemes de llenguage

Griswold i Townsend varen comentar sobre l'adopció del hashing llineal en el llenguage de programació Icon. Varen parlar de les alternatives d'implementació de matriu dinàmica algoritme utilisat en el hashing llineal, i varen presentar comparacions de rendiment utilisant una llista de Icon d'aplicacions de referència.

Adopció en sistemes de bases de senyes

El hashing llineal s'utilisa en el sistema de base de senyes de Berkeley, que a la seua volta és utilisat per molts sistemes de software com OpenLDAP, utilisant una aplicació C derivat de l'artícul MCCA i publicat per primera volta en Usenet en 1988 per Esmond Pitt.