Hashing
4Am vrut sa scriu primul meu post despre STL, dar am renuntat intrucat nu aveam timpul si nervii necesari (nu faceam altceva decat sa traduc de prin alte parti). Asadar pentru a afla mai multe despre STL (care va putea fi folosit de la anul si la OJI) consultati http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary, http://www.sgi.com/tech/stl/ si mai sunt si altele. Daca aveti ceva intrebari puteti sa le puneti tot aici.
Hashingul (in engleza a toca) este foarte folositor in multe cazuri. Sa presupunem ca trebuie rezolvata urmatoarea aplicatie: Se da o lista cu N elemente (care poate fi de numere, stringuri sau orice altceva). Gasitit duplicatele din acea lista.
Un programator incepator ar cauta pentru fiecare element sa vada daca il mai gaseste in lista => complexitate O(N^2). Pentru N mai mic de 2000-3000 e ok, dar daca N ajunge pe la 10000 executia programului incepe sa dureze foarte mult.
Un programator mediu ar sorta elementele si le-ar compara cu vecinii din lista sortata => complexitate O(N*logN). Pentru N de cateva sute de mii treaba merge ok, dar daca N este de ordinul milioanelor, aplicatia iarasi dureaza foarte mult.
Un programator ceva mai experimentat ar folosi hash-urile pentru a rezolva aceasta problema. Sa presupunem ca toate elementele sunt numere naturale mai mici decat 1000. In acest caz se poate tine un sir de „vizitate”, care ia valoarea 1 sau 0 daca elementul a mai fost intalnit sau nu. Dar daca numerele depasesc 15-20 de milioane, nu se mai poate retine un astfel de sir. Pentru asta s-a „inventat” hashingul.
Nu pot retine un sir de cateva milioane sau miliarde, dar un sir de cateva sute de elemente se poate retine. Cum stim ca A mod B < B, oricat ar fi A, putem retine un sir de B elemente (B trebuie sa fie suficient de mic ca sa putem un sir de B elemente). Astfel putem verifica daca elementul a mai fost intalnitin sir verificand valoarea lui viz[A mod B].
Dar problemele apar cand numarul de elemente este mai mare decat B+1. Conform pricipiului lui Dirichlet, cel putin 2 elemente vor fi congruente modulo B. Aceasta situatie se numeste coliziune. Cum programatorii sunt niste oameni foarte descurcareti, au gasit si solutia acestei situatii. In loc de un sir de vizitate (care ia valori 1 sau 0, daca elementul a mai fost intalnit sau nu), pentru fiecare valoare de la 0 la B se retine o lista (vector) dinamica. Iar cand intalnesc o valoare A, o introduc in lista L[A mod B]. Iar in cazul in care vreau sa caut un element C, doar caut elementul C in lista L[C mod B].
Valoarea lui B trebuie aleasa astfel incat sa asiguram o distributie normala a valorilor modulo B. De aceea se prefera ca B sa fie un numar prim, si in niciun caz putere a lui 2. Cele mai utilizate sunt 666013 (multa lume are o preferinta pentru acest numar), 11677, si altele. Evident, exista mai multe metode de a „hashui” elementele, insa aceasta cu modulo este cea mai utilizata.
Pentru stringuri se procedeaza exact la fel, considerand fiecare litera ca pe un numar.
Astept evenetuale intrebari 😀
Eu in general pentru a evita coliziunile intre hash`uri folosesc lista simplu inlantuite! Mi se pare cea mai simpla implementare.
Operatiile ce se pot face foarte rapid cu hashuri sunt :
Adaugare element : O(1)
Cauta element : O(k), k = numarul de coliziuni
Sterge element(daca exista) : O(1) + O(k), k = numar de coliziuni.
Daca numarul elementelor este mic(aproximativ 1000) si pastram un sir de „vizitate” atunci toate operatiile descrise mai sus se fac in O(1).
Una din aplicabilitati este algoritmul lui Rabin-Karp ce il voi implementa curand,acum avand si baza teoretica pentru hashuri. 🙂
Defapt complexitatea pentru fiecare operatie se considera O(1), acel k fiind in general destul de mic
Da in medie este O(1), insa cu exactitate e O(k), daca functia ce stabileste pozitia este proasta atunci acel k poate fi destul de mare.
Spre exemplu :
Vom avea numere intre 1 si 1 milion,iar functia de dispersie este : h(x) { return x % 2; } va dispera toate elementele in 0 si 1.In aceasta situatie in medie k va fi n/2 elemente daca numerele sunt random si practic cautarea si stergerea unui element va fi O(n/2).
Pentr a avea o functie ce ofera cat mai putine coliziuni este indicat ca numarul ce face dispersia sa fie un numar cat mai indepartat de 2 puteri ale lui 2 si NICIODATA sa nu fie o putere a lui 2.
[…] acestui algoritm consta in rezolvarea in timp liniar folosind algoritmul Rabin-Karp, ce are la baza hashuri.Acest algoritm are timpul de executie […]