Linear probing
Linear probing és un esquema de programació informàtica per a resoldre colisions en taules hash, estructures de senyes per a mantindre una colecció de parells clau-valor i buscar el valor associat a una clau determinada. Va ser inventat en 1954 per Gene Amdahl, Elaine M. McGraw i Arthur Samuel i analisat per primera volta en 1963 per Donald Knuth.
Junt en el sondeig quadràtic i el hashing doble, linear probing és una forma de direccionament obert. En estos esquemes, cada cela d'una taula hash almagasena un únic parell clau-valor. Quan la funció hash provoca una colisió en assignar una nova clau a una cela de la taula hash que ya està ocupada per una atra clau, el linear probing busca en la taula la següent ubicació lliure més propenca i inserta allí la nova clau. Les busques es realisen de la mateixa manera, buscant en la taula secuencialmente a partir de la posició donada per la funció hash, fins a trobar una cela en una clau coincidente o una cela buida.
Com escriuen Thorup i Zhang (2012), "les taules hash són les estructures de senyes no trivials més utilisades, i l'implementació més popular en hardware estàndar utilisa el linear probing, que és ràpit i senzill".[1] El linear probing pot proporcionar un alt rendiment per la seua bona localitat de referència, pero és més sensible a la calitat de la seua funció hash que atres esquemes de resolució de colisions. Requerix un temps esperat constant per busca, inserció o borrat quan s'implementa utilisant una funció hash aleatòria, una funció hash independent de 5 o un hashing de tabulació. En la pràctica, també es poden obtindre bons resultats en atres funcions hash, com MurmurHash.[2]
Operacions
[editar | editar còdic]El linear probing és un component dels esquemes de direccionament obert per a utilisar una taula hash per a resoldre el problema del diccionari. En el problema del diccionari, una estructura de senyes deu mantindre una colecció de parells clau-valor subjecta a operacions que inserten o borren parells de la colecció o que busquen el valor associat a una clau donada. En les solucions de direccionament obert a este problema, l'estructura de senyes és una matriu T (la taula hash) les celes de la qual T[i] (quan no estan buides) almagasenen cada una un únic parell clau-valor. S'utilisa una funció hash per a assignar cada clau a la cela de T en la que deu almagasenar-se, normalment codificant les claus per a que les claus en valors similars no es coloquen prop unixques d'atres en la taula. Una colisió hash es produïx quan la funció hash assigna una clau a una cela que ya està ocupada per una clau diferent. El linear probing és una estratègia per a resoldre les colisions, colocant la nova clau en la cela buida més pròxima.[3][4]
Busca
[editar | editar còdic]Per a buscar una clau x donada, s'examinen les celes de T, escomençant per la cela d'índex h(x) (a on h és la funció hash) i continuant per les celes adjacents h(x) + 1, h(x) + 2, ..., fins a trobar una cela buida o una cela que la seua clau almagasenada siga x. Si es troba una cela que conté la clau, la busca torna el valor d'eixa cela. En cas contrari, si es troba una cela buida, la clau no pot estar en la taula, perque s'hauria colocat en eixa cela en preferència a qualsevol cela posterior en la que encara no s'haja buscat. En este cas, la busca torna com a resultat que la clau no està present en el diccionari.[3][4]
Inserció
[editar | editar còdic]Per a insertar un parell clau-valor (x,v) en la taula (possiblement substituint qualsevol parell existent en la mateixa clau), l'algoritme d'inserció seguix la mateixa seqüència de celes que se seguiria per a una busca, fins a trobar una cela buida o una cela que la seua clau almagasenada siga x. El nou parell clau-valor es coloca llavors en eixa cela.[3][4]
Si l'inserció fera que el factor de càrrega de la taula (la seua fracció de celes ocupades) creixquera per damunt d'algun llindar preestablit, tota la taula pot ser substituïda per una nova taula, més gran per un factor constant, en una nova funció hash, com en un array dinàmic. Establir este llindar prop de zero i utilisar una taxa de creiximent alta per al tamany de la taula conduïx a operacions de taula hash més ràpides pero en un major us de memòria que els valors de llindar propencs a un i taxes de creiximent baixes. Una opció comuna seria duplicar el tamany de la taula quan el factor de càrrega superara 1/2, fent que el factor de càrrega es mantinguera entre 1/4 i 1/2.[5]
Borrat
[editar | editar còdic]
També és possible eliminar un parell clau-valor del diccionari. No obstant, no n'hi ha prou en buidar la seua cela. Açò afectaria a les busques d'atres claus que tenen un valor hash anterior a la cela buidada, pero que estan almagasenades en una posició posterior a la cela buidada. La cela buidada provocaria que eixes busques informaren incorrectament de que la clau no està present.
En el seu lloc, quan es buida una cela i, és necessari buscar en les següents celes de la taula fins a trobar una atra cela buida o una clau que es puga moure a la cela i (és dir, una clau el valor de la qual hash siga igual o anterior a i). Quan es troba una cela buida, el buidat de la cela i és segur i el procés de borrat termina. Pero, quan la busca troba una clau que pot moure's a la cela i, realisa este moviment. Açò té l'efecte d'accelerar les busques posteriors de la clau moguda, pero també buida una atra cela, més alvance en el mateix bloc de celes ocupades. La busca d'una clau moguda continua per la nova cela buidada, de la mateixa manera, fins que termina en aplegar a una cela que ya estava buida. En este procés de trasllat de claus a celes anteriors, cada clau s'examina una sola volta. Per lo tant, el temps per a completar tot el procés és proporcional a la llongitut del bloc de celes ocupades que conté la clau eliminada, igualant el temps d'eixecució de les demés operacions de la taula hash.[3]
Alternativament, és possible utilisar una estratègia de borrat pereós en la que un parell clau-valor s'elimina substituint el valor per un valor de bandera especial que indica una clau borrada. No obstant, estos valors de bandera contribuiran al factor de càrrega de la taula hash. En esta estratègia, pot ser necessari netejar els valors de les banderes de la matriu i tornar a almagasenar tots els parells clau-valor restants una volta que una fracció massa gran de la matriu estiga ocupada per claus eliminades.[3][4]
Propietats
[editar | editar còdic]El linear probing proporciona una bona localitat de referència, lo que fa que requerixca pocs accessos a memòria no almagasenada per operació. Per açò, per a factors de càrrega de baixos a moderats, pot proporcionar un rendiment molt alt. No obstant, en comparació a atres estratègies de direccionament obert, el seu rendiment es degrada més ràpidament en factors de càrrega alts per l'agrupació primària, una tendència d'una colisió a causar més colisions propenques.[3]Ademés, conseguir un bon rendiment en este método requerix una funció hash de major calitat que per a atres esquemes de resolució de colisions.[6] Quan s'utilisa en funcions hash de baixa calitat que no eliminen la falta d'uniformitat en la distribució d'entrada, el linear probing pot ser més llent que atres estratègies de direccionament obert, com el doble hashing, que sondeja una seqüència de celes la separació de les quals ve determinada per una segona funció hash, o el sondeig quadràtic, en el que el tamany de cada pas varia en funció de la seua posició dins de la seqüència de sondeig.[7]
Referències
[editar | editar còdic]- ↑ Thorup, Mikkel; Zhang, Yin (2012), "Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation", SIAM Journal on Computing, 41 (2): 293–331, doi:10.1137/100800774, MR 2914329
- ↑ Richter, Stefan; Alvarez, Victor; Dittrich, Jens (2015), "A seven-dimensional analysis of hashing methods and its implications on query processing" (PDF), Proceedings of the VLDB Endowment, 9 (3): 293–331, doi:10.14778/2850583.2850585
- ↑ 3,0 3,1 3,2 3,3 3,4 3,5 Goodrich, Michael T.; Tamassia, Roberto (2015), "Section 6.3.3: Linear Probing", Algorithm Design and Applications, Wiley, pp. 200–203
- ↑ 4,0 4,1 4,2 4,3 Morin, Pat (February 22, 2014), "Section 5.2: LinearHashTable: Linear Probing", Open Data Structures (in pseudocode) (0.1G&x3B2; ed.), pp. 108–116, retrieved 2016-01-15
- ↑ Sedgewick, Robert; Wayne, Kevin (2011), Algorithms (4th ed.), Addison-Wesley Professional, p. 471, ISBN 9780321573513 Sedgewick i Wayne també reduïxen a la mitat el tamany de la taula quan una eliminació faria que el factor de càrrega fora massa baix, lo que els du a utilisar un ranc més ampli [1/8,1/2] en els possibles valors del factor de càrrega.
- ↑ Pătraşcu, Mihai; Thorup, Mikkel (2010), "On the k-independence required by linear probing and minwise independence" (PDF), Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, Juliol6-10, 2010, Proceedings, Part I, Lecture Notes in Computer Science, vol. 6198, Springer, pp. 715-726, arXiv:1302.5127, doi:10.1007/978-3-642-14165-2_60
- ↑ Heileman, Gregory L.; Luo, Wenbin (2005), "How caching affects hashing" (PDF), Seventh Workshop on Algorithm Engineering and Experiments (ALENEX 2005), pp. 141–154
- Este artícul conté una traducció derivada de «Linear probing» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.