Un HashTable reprezintă o structură de date al cărui index pentru elementele stocate este generat pe baza unei funcții de hash. Unde index reprezintă un număr folosit pentru identificarea și accesarea individuală a elementelor.
Nu înțelegi ce-i aceea o funcție hash și la ce ajută sau chiar nici măcar ce e o structură de date?
Nicio problemă, îți explic.
Ce este o structură de date
În informatică, o structură de date reprezintă un mod de a organiza, stoca și gestiona date pentru a putea fi utilizate eficient. Există structuri de date care sunt optimizate pentru acțiuni diferite, cum ar fi: căutare, sortare, adăugare sau ștergere de elemente.
Structurile de date sunt concepte transverse în toate limbajele de programare existente, nu sunt specifice unui limbaj anume.
Uite câteva exemple de structuri de date:
- Array (Matrice/mulțime)
- Linked List (Listă înlanțuită)
- Stack (Stivă)
- Queue (Coadă)
Ce este HashTable
Un HashTable e o structură de date ce stochează elemente de tip perechi, cheie și valoare, astfel încât să se asigure unicitatea elementelor stocate, întrucât nu pot exista 2 elemente cu aceeași cheie.
Aceeași structură de date poate fi întâlnită și sub denumirea de “Dicționar”.
Indexul și funcția hash
Așa cum spuneam și anterior, indexul nu este altceva decât un număr de ordine al elementelor stocate. Valoarea lui e întotdeauna de tip număr întreg.
Acest index de asemenea folosit pentru a accesa și identifica în mod direct elementele.
Într-o structură de date ceva mai simplistă, precum un Array, acest index este incrementat automat cu 1 la fiecare nouă adăugare, astfel că el reprezintă ordinea în care elementele au fost adăugate, de la primul până la ultimul.
Într-un HashTable obținerea indexului se face puțin diferit și nu este incrementat la fiecare adăugare. Indexul este generat prin trecerea valorii ce urmează a fi stocate printr-o funcție ce poartă numele de funcție hash.
Există diferite implementări de funcții hash, dar în principiu ele reprezintă secvențe de operații logice și/sau matematice ce transformă o valoare ce poate fi numerică sau text (string) într-un număr ce poartă numele de cod hash (hash code).
În cazul unui HashTable, indexul este generat de o funcție hash, de aici și numele structurii de date.
Uite câteva caracteristici cheie pe care o funcție hash trebuie să le aibă:
- Să fie deterministică - întotdeauna aceleași date de intrare ar trebui să producă aceleași date de ieșire
- Extrem de rapidă - timpul de execuție să fie minim
- Să facă distribuire uniformă a valorilor, pentru a evita generarea de grupuri de valori
- Rată minimă de coliziuni - generarea aceluiași hash pentru două valori diferite
- Ireversibilă - să nu poți inversa procedeul și obține valoarea originală pornind de la hash
Coliziunile
Deși funcțiile hash sunt extrem de optimizate, există totuși posibilitatea ca două valori complet distincte să genereze aceeași valoare de hash, ceea ce produce o coliziune, adică două valori trebuie stocate sub același index.
Asta nu înseamnă că dacă funcția hash produce același index, valorile respective, deși distincte, nu pot fi stocate în același HashTable.
Există implementări diferite pentru rezolvarea acestui tip de problemă, dar cel mai cunoscut este folosirea unui LinkedList pentru a stoca valorile respective pe același index.
Astfel că la pozițiile indecșilor, nu vom mai avea valorile concrete, ci vom avea liste înlănțuite ce vor stoca toate valorile al căror index coincide. Terminologia folosită în cazul ăsta e aceea de buckets (găleți/recipiente). Spunem că valorile sunt stocate într-un bucket cu indexul 5.
Avantajele utilizării unui HashTable
Acum poate te întrebi care e rostul tuturor acestor operațiuni, de ce să irosim atât de mult efort încercând să generăm un index numeric, când numerotarea secvențială ar putea funcționa foarte bine.
Ei bine, problema apare atunci când într-o astfel de structură de date, cu valori secvențiale pentru indecși, trebuie să facem o căutare a unei valori, iar structura respectivă are milioane de elemente stocate.
Procesul de căutare nu se poate implementa altfel decât prin iterarea prin toate elementele existente, până la identificarea valorii căutate, ceea ce este extrem de neperformant și consumator de resurse.
Pe când, în cazul unui HashTable, funcția hash va genera index-ul și vom putea identifica existența valorii printr-o singură acțiune, fără să fie nevoie să inspectăm alte valori de pe alți indecși.
Asta face un HashTable extrem de performant, prin comparație, de exemplu, cu un classic Array, sau orice altă structură de date care nu implementează o funcție hash.
Dacă vrei o analogie pentru a înțelege mai ușor mecanismele interne ale unui HashTable, gândește-te la următoarea situație:
Trebuie să cauți un produs anume într-un depozit imens cu zeci sau sute de mii de produse pe rafturi.
Dacă nu îți este dat niciun fel de indiciu legat de locația unde s-ar putea afla produsul respectiv, tot ce poți să faci e să iei toate rafturile rând pe rând, produs cu produs și să-l cauți.
Așa-i că ți-ar lua enorm de mult să-l găsești?
Dar dacă ți s-ar spune: produsul e pe culoarul 12, coloana 25, nivelul 1. Atunci durata de obținere a produsului e egală cu viteza ta până la locația respectivă.
În primul caz, în schimb, durata creștea o dată cu numărul de produse existente în depozit, pentru că ar fi trebuit să treci prin toate, depinzând de noroc.
În exemplul dat, locația produsului ar reprezenta indexul generat de funcția hash.
Cazurile de utilizare ale unui HashTable
Aplicațiile software moderne folosesc destul de intensiv structurile de date de tip HashTable, mai ales în operațiunile ce țin de identificarea unui element într-o colecție foarte mare, cu milioane de elemente.
Faptul că obținem într-un mod foarte rapid indexul elementului pe care vrem să îl accesăm e un avantaj major în fața altor structuri de date prin care, așa cum spuneam, trebuie de multe ori să iterăm cu câte un element o dată pentru a-l identifica pe cel căutat.
Uite câteva situații interesante în care se folosește HashTable:
- Compilatoarele limbajelor de programare.
Compilatoarele limbajelor de programare folosesc ceea ce se cheamă Symbol Table (tabel de simboluri) pentru a lega numele variabilelor și locația lor în memorie.
- Tabele de rutare în rețelistică
Un router păstrează date legate de alegerea celei mai bune rute atunci când încercăm, de exemplu, să accesăm o pagină web. Pe baza IP-ului destinație, router-ul caută cea mai bună rută, dacă a fost anterior determinată, într-un HashTable.
- Cache-ul unui browser pentru identificarea IP-ului pentru un nume de domeniu
Browser-ele moderne salvează în propriul cache extrem de multe date pentru a ne oferi performanța de care avem parte, care nu stă, desigur, doar în lățimea de bandă a conexiunii la internet.
Unul din seturile de date pe care un browser le salvează în cache e acela legat de numele de domeniu și IP-ul de destinație pentru a nu mai face apelul către un server DNS.
Sper că te-am ajutat să înțelegi mai bine acum modul de funcționare al unui HashTable și de ce e important să știi asta ca inginer software.
Atât pentru azi, pe data viitoare.
