Salutare dragilor,
Acum câteva săptămâni am discutat despre mai multe implementări de liste în Java și am evidențiat câteva dintre cele mai importante asemănări și deosebiri. Astăzi, rămânem la capitolul colecții, dar vom vorbi despre Map-uri.
Structurile de date sunt foarte importante în fiecare limbaj de programare în parte. De ce? Pentru că cu ajutorul lor vom putea stoca date de care are nevoie aplicația noastră. Ca să fiu sincer, nu am întâlnit aplicații care să nu aibă o listă sau un map under the hood. Dacă în cazul unei liste, aceasta era folosită pentru a stoca o serie de valori, în cazul unui map, vorbim de stocarea unor perechi de chei și valori. Cu alte cuvinte, vorbim de posibilitatea de a asocia o cheie unei valori. Una dintre cele mai cunoscute implementări de map în Java este HashMap. HashMap-ul are și un frate - Hashtable - poate mai puțin cunoscut, dar care ar trebui prezentat numai în scop didactic, pentru că odată cu apariția ConcurrentHashMap, ar trebui să nu mai fie folosită în nicio aplicație.
Organizarea în memorie a unui HashMap
Cum este organizat un map în memorie? Păi foarte simplu. La prima vedere, am putea vedea un map ca fiind o listă de liste. Nice, nu? Ne folosim de un concept, pe care îl ducem la alt nivel, pentru a explica alt concept. Vă aduceți aminte de ArrayList? Fără să vrem și în cazul unui ArrayList putem vorbi de o asociere de chei și valori. Cum așa? Păi să spunem că într-un ArrayList am avea o succesiune de 10 persoane care așteaptă la un rând. Prima persoană din listă avea asociat indexul 0, a doua persoană indexul 1 și tot așa. În acest caz, vorbim de o cheie determinată de indexul persoanei și de o valoare asociată dată de persoana în cauză. Clar?! Ce ar fi dacă am pune o listă ca și valoare în fiecare element dintr-un ArrayList?
O listă de liste ar însemna la prima vedere o matrice, dar după cum se poate vedea nu este chiar așa pentru că numărul de coloane diferă pe fiecare linie. Dacă ar fi să revenim puțin la implementările de liste pe care le-am studiat, exemplul de mai sus se potrivește de minune cu un ArrayList (de 4 elemente) care are la rândul său 4 LinkedList. Fiecare element din LinkedList este o combinație de (cheie, valoare) și are un pointer către elementul următor - next. Next pointează către null atunci când ne mai există un element următor.
Acum, întrebarea pe care ar trebui să o puneți este cum am pus eu aceste elemente? De ce k1 și k2 sunt pe prima linie și k3 pe linia a doua? De ce nu invers? Răspunsul la această întrebare este simplu. Depinde de proprietățile pe care le are cheia respectivă. Dacă aș fi avut o singură linie, în final aș fi ajuns să am o listă.
Până la a studia în detaliu organizarea în memorie a datelor, vom evidenția puțin cerințele pe care ni le-am dori de la un map. Am zis că avem de-a face cu o asociere de chei și valori, dar foarte important este faptul că ne propunem să căutăm valori folosind cheile asociate lor. Dacă la un ArrayList, pentru a compara o valoarea dată cu una din listă, trebuia să iterăm după fiecare și să folosim funcția equals pentru a decide dacă e sau nu valoarea noastră (complexitate liniară), aici am vrea ca lucrurile să fie mai rapide. Și bineînțeles să folosim o cheie pentru a obține valoarea. La fel ca și la operația de lookup, ne dorim să avem un timp constant și pentru operația de adăugare - put(key, value).
Pentru determinarea liniei unde va ajunge o cheie și o valoare în map-ul nostru se va folosi o funcție specială - numită hashCode. Această funcție se va aplica peste cheia noastră și va produce un întreg asupra căruia se aplică un modulo N iar rezultatul va reprezintă cumva bucketul în care va ajunge pair-ul nostru. În cazul de mai sus, numărul de bucket-uri este de 4. Observăm că un bucket poate avea și null. Foarte important acest aspect, pentru că de fapt maximum un bucket poate avea acestă proprietate. De ce? Pentru că dacă am avea două chei egale cu null, ele ar avea același hashCode și implicit ar ajunge în același bucket. Bun, dar pot avea mai multe valori null în map? Răspunsul este afirmativ. De ce? Pentru că valoarea nu contează, doar cheia se folosește pentru a căuta valoarea pe care trebuie să o returnăm...
Coliziuni
Pot exista coliziuni într-un map? Adică să avem două chei distincte care să aibă același hashCode? Răspunsul este afirmativ și în acest caz. Implementarea funcției de calcul al hashCode-ului este lasată de latitudinea dezvoltatorului. Să luăm un exemplu de coliziune... Să zicem că avem o funcție de hashCode care va returna fix numărul de caractere prezent în string-ul din cheie (presupunem că cheia noastră e un string). Dacă k1 = "Mama" și k2 = "Tata", ne vom afla în situația în care hashCode("Mama") = hashCode("Tata") = 4. Cu alte cuvinte, atât k1 cât și k2 vor ajunge în același bucket, la fel ca și în figura noastră. De ce acest lucru e rău? Haideți să ne gândim la căutarea cheii k2. Pentru lookup, mai întâi vom determina hashCode(k2), adică bucketul unde ar trebui să fie cheia, după care va trebui să luăm toate cheile prezente în bucket și folosind funcția equals să iterăm peste toate și să întoarcem valoarea corespondentă a cheii noastre. Dacă determinarea bucketului se face în timp constant - O(1), din păcate selectarea valorii din listă se va face în timp liniar - O(n). Având în vedere toate aceste aspecte, lookup-ul într-un map se face în timp constant doar dacă nu avem coliziuni.
Cum procedăm pentru a nu avea coliziuni? Răspunsul este cât se poate de intuitiv. Trebuie să ne asigurăm că funcția de hashCode are o implementare în așa fel încât pentru două chei diferite nu va avea același rezultat. Vorbim așadar de o funcție de hashing clasică, în care nu ne dorim ca două parole diferite să aibă același hash în baza de date și să ne trezim că un utilizator se poate loga în aplicația noastră folosind o altă parolă decât cea specificată inițial. Cu ajutorul matematicii acest lucru e posibil. Nu voi intra acum în detaliu legat de acest aspect, doar aș vrea să menționez faptul că începând cu Java 7, există o funcție prin care se poate calcula hashCode-ul unui obiect - Objects.hash().
Ordonare
Într-un map nu există noțiunea de ordonare. De fapt, într-un HashMap. Dacă ordonarea este importantă în cazul dvs. aveți la dispoziție LinkedHashMap sau TreeMap. În cadrul acestui articol am zis doar să le menționez fără să intru în detaliu. De aceea, dacă doriți mai multe informații legate de modul de funcționare, vă invit să aruncați o privire asupra documentației oficiale.
Cheie imutabilă
Să revenim la HashMap-ul nostru. Și anume la cheie. O altă recomandare în privința ei este să fie imutabilă. De ce? O întrebare des întâlnită pe la interviuri, mai ales sub forma unor mici exerciții. Dacă cheia nu este imutabilă, se pot întâmpla lucruri mai puțin plăcute la căutarea sau chiar ștergerea din map. Las la plăcerea cititorului să se gândească de ce o cheie mutabilă poate provoca multe probleme...
Despre numărul de bucket-uri
Numărul inițial de bucket-uri într-un HashMap este de 16. Acest număr crește în funcție de numărul de elemente din map. În momentul în care inserăm elemente prin care se depășește 75% din numărul de bucket-uri, numărul de bucket-uri se va dubla. 75% din 16 = 12. Cu alte cuvinte, în momentul în care am inserat al 12-lea pair de chei și valori în map, numărul de bucket-uri va deveni automat 32. Putem vorbi așadar de o capacitate și un load factor care este setat la 75% din capacitate. Această redimensionare necesită bineînețeles și recalcularea hash-urilor. La crearea unui obiect de tipul HashMap, dezvoltatorul are posibilitatea de a specifica o capacitate inițială și un load factor:
Map<String, String> mapWithCapacityAndLoadFactor = new HashMap<>(10, 0.75f);HashMap-ul este sau nu thread-safe?
HashMap-ul nu este thread-safe. Ca și implementare thread-safe se poate folosi Hashtable - care are fiecare operație de read și write sincronizată, dar și o implementare mai nouă - ConcurrentHahMap - disponibilă din Java 7. De ce Hashtable nu este indicată? Pentru că în cazul în care avem multe fire de execuție care citesc din map și doar câteva care scriu, operația de read va fi sincronizată în continuare și toate citirile se vor face secvențial. This is bad...
ConcurrentHashMap vs Hashtable vs HashMap
O variantă de a face un HashMap thread-safe este că sincronizăm accesul la orice operație de read sau write. Exact asta face Hashtable. Întrebarea este dacă se poate face ceva mai inteligent? Răspunsul este că da. În loc de a folosi un singur lock, putem folosi mai multe lock-uri - ceva de genul: un lock per bucket.
Modificări importante aduse o dată cu Java 8
Câteva modificări importante au fost aduse în modul în care funcționează un HashMap o dată cu Java 8. În momentul în care existau coliziuni, am zis că e posibil două sau mai multe chei să ajungă în același bucket și în acest caz se crea un LinkedList pentru a stoca intrările. În această situație, căutarea unui element după o cheie se făcea într-un timp liniar, which is bad. În plus, LinkedList consumă și destul de multă memorie. Întrebarea ar fi dacă am putea face ceva în acest caz pentru a îmbunătăți situația? Din Java 8, în cazul în care numărul de elementele din LinkedList depășește o anumită valoare, structura de date folosită va fi un binary tree. Să ne aducem aminte faptul că în binary tree căutarea se face în timp logaritmic - O(logn). Mai rămâne totuși o întrebare și anume cum sunt puse elementele în binary tree? Păi în principiu se folosește hasCode-ul fiecărei chei în parte pentru a le compara și dacă au același hashCode se vor compare cheile așa cum sunt. Din acest motiv, este indicat ca fiecare cheie să implementeze Comparable.
Happy coding! :)
