Cred că va fi mai util dacă voi explica HashMaps în engleză.

Ce este un HashMap?

Un HashMap este o structură de date care este capabilă să mapeze anumite chei la anumite valori. Cheile și valorile pot fi orice. De exemplu, dacă aș face un joc, aș putea lega fiecare nume de utilizator de o listă de prieteni, reprezentată de o listă de șiruri de caractere.

De ce să folosim un HashMap?

HashMap-urile sunt mult mai rapide pentru a prelua date decât array-urile și listele legate. Un array sortat ar putea găsi o anumită valoare în O(log n) cu căutare binară. Cu toate acestea, un HashMap poate verifica dacă conține o anumită cheie în O(1). Toate cheile trebuie să fie unice.

Cum funcționează HashMaps?

HashMaps utilizează o matrice în fundal. Fiecare element din matrice este o altă structură de date (de obicei o listă legată sau un arbore binar de căutare). HashMap utilizează o funcție asupra cheii pentru a determina unde să plaseze valoarea cheii în matrice. De exemplu, dacă HashMap-ul meu acceptă șiruri de caractere… posibilele funcții hash pot fi:

A. Return the ASCII value of the first letter.B. Return the sum of the ASCII values of every character in the String.C. Return the ASCII value of the last character in the String.

Valoarea returnată va determina indexul în care valoarea va fi plasată în tablou.

Dar stați! Există o problemă!

Este posibil ca valoarea returnată să fie în afara limitelor tabloului. Prin urmare, ar trebui să modificăm valoarea returnată cu lungimea array-ului.

return Math.abs(number%hashMapArray.length);

Coliziuni:

Nu este posibil ca mai multe chei să facă funcția hash să genereze același index? Da. De exemplu, dacă am folosit prima funcție hash prezentată mai sus într-o hartă hash de șiruri de caractere… orice două șiruri care încep cu aceeași literă vor primi același index de matrice.

Aceasta se numește coliziune.

Cum gestionăm coliziunile?

O tehnică de tratare a coliziunilor se numește Chaining. Deoarece fiecare element din matrice este o listă legată (sau o structură de date similară), mai multe chei care au aceeași valoare hash vor fi plasate în aceeași listă legată sau „bucket”. Ulterior, harta hash este capabilă să recupereze valorile prin calcularea codului hash cu ajutorul funcției hash și prin căutarea în lista legată respectivă pentru a vedea dacă aceasta conține o valoare cu aceeași cheie.

O bună funcție hash trebuie scrisă pentru a evita coliziunile.

Vantajele înlănțuirii:

-Array-ul nu se poate supraaglomera

-Datele pot fi eliminate cu ușurință

Dezavantajele înlănțuirii:

-Pot suferi o scădere de performanță dacă bucket-urile conțin liste legate foarte lungi.

Numărul total de intrări raportat la numărul de bucket-uri se numește factor de încărcare. Dacă factorul de încărcare este prea mic, se risipește mult spațiu. Dacă factorul de încărcare este prea mare, se pierde avantajul hashing-ului. Un compromis bun pentru factorul de încărcare este 0,75

.