HashMap este o structură de date care stochează datele în perechi (Cheie, Valoare), similar cu Dicționarul în python dacă vă place asta!
Pentru a înțelege funcționarea internă a Hashmap, să ne familiarizăm cu următorii termeni:
HASHING:
Hashing este procesul de conversie a unei anumite chei într-o altă valoare pe baza unei formule folosind o funcție. O funcție hash este utilizată pentru a genera noua valoare în conformitate cu un algoritm matematic. Rezultatul unei funcții hash este cunoscut sub numele de valoare hash sau, pur și simplu, hash. Este utilizată pentru indexarea și recuperarea elementelor și pentru
algoritmi de criptare.
O adevărată funcție hash trebuie să respecte această regulă –
„Funcția hash trebuie să returneze același cod hash de fiecare dată când funcția este aplicată pe obiecte identice sau egale. Cu alte cuvinte, două obiecte egale trebuie să producă același cod hash în mod consecvent.”
Toate obiectele din Java moștenesc o implementare implicită a funcției hashCode() definită în clasa Object.
COLLISIONS :
Rețineți că două chei pot genera același hash care poate duce la aceeași adresă. Acest fenomen este cunoscut sub numele de coliziune.
Funcții HashMap
1. Public V get(Object key) : adică pentru a prelua o valoare din hartă pe baza cheii.
2. Public V put(K key, V value) : sau pentru a insera o pereche cheie , valoare în hartă.
Nota: În general, este necesar să suprascrieți metoda hashCode() ori de câte ori metoda equals() este suprascrisă, pentru a menține contractul general pentru metoda hashCode(), care prevede că obiectele egale trebuie să aibă coduri hash egale.
HashMap în JAVA
Modalități de instanțiere a unui HashMap în java:
1. Construiește un HashMap gol cu capacitatea inițială
și factorul de încărcare specificate.
public HashMap(int initialCapacity, float loadFactor)
2. Construiește un HashMap gol cu capacitatea inițială
și factorul de încărcare specificat și factorul de încărcare implicit (0,75).
public HashMap(int initialCapacity)
3. Construiește un HashMap gol cu capacitatea inițială implicită (16) și cu factorul de încărcare implicit (0.75).
public HashMap()
Factorul de încărcare și capacitatea inițială.
O instanță de HashMap are doi parametri care îi afectează performanța:
1. Capacitatea inițială
2. Factorul de încărcare.
Capacitatea inițială:
Capacitatea este numărul de găleți din tabelul hash, iar capacitatea inițială este pur și simplu capacitatea din momentul în care este creat tabelul hash.
Factorul de încărcare:
Factorul de încărcare este o măsură a gradului de umplere a tabelului hash înainte de a i se mări automat capacitatea. Atunci când numărul de intrări din tabela hash depășește produsul dintre factorul de încărcare și capacitatea curentă, tabela hash este refăcută (adică structurile de date interne sunt reconstruite) astfel încât tabela hash să aibă aproximativ dublul numărului de găleți.
NOTA:
De regulă, factorul de încărcare implicit (.75) oferă un bun compromis între costurile de timp și spațiu. Valorile mai mari scad cheltuielile de spațiu, dar cresc costul de căutare (reflectat în majoritatea operațiilor clasei HashMap, inclusiv get și put.
Numărul preconizat de intrări în hartă și factorul de încărcare al acesteia trebuie luate în considerare atunci când se stabilește capacitatea inițială a acesteia, astfel încât să se reducă la minimum numărul de operații de rehash. Dacă capacitatea inițială este mai mare decât numărul maxim de intrări împărțit la factorul de încărcare, nu vor avea loc niciodată operații de rehash.
HashMap în Java 8
Un HashMap (din java 8) stochează datele în mai multe liste de intrări legate individual sau în mai multe Red BlacK Trees sau un amestec din ambele , în funcție de prag, numite și găleți sau bins.
Toate listele/arborii sunt înregistrate într-o matrice de intrări (Entry<K,V> table), iar capacitatea implicită a acestei matrice interioare este de 16.
Care dintre înregistrările unice sau o singură pereche de Key și o valoare într-un HashMap se numește Entry<Key,Value>.
Entry
HashMaps utilizează o clasă internă pentru a stoca date: Entry<K, V>.
Această intrare este o simplă pereche cheie-valoare cu două valori suplimentare care sunt următoarele:
1. O referință la o altă intrare, astfel încât un HashMap să poată stoca intrările ca și cum ar fi liste legate individual sau ca un arbore cu noduri stânga și dreapta pentru a oferi o căutare mai bună.
2. O valoare hash care reprezintă valoarea hash a cheii. Această valoare hash este stocată pentru a evita calcularea hash-ului de fiecare dată când HashMap are nevoie de ea.
Intrarea în java 8 poate fi de 2 tipuri Nod LinkedList sau Nod RedBlack Tree.
*dimensiunea acesteia, așa cum s-a discutat mai sus, este fie definită în timpul instanțierii, fie implicit 16. Pe baza factorului de încărcare, aceasta crește la dublul dimensiunii anterioare, astfel încât să poată găzdui intrări suplimentare.
Nod tranzitoriu<K,V> tabel; //conține toate intrările.
În tabel, fiecare index este un nod fie al unei LinkedList, fie al unui RedBlackTree.
Hierarhia intrărilor se prezintă astfel:
Carte.Entry<K,V> → implementează → Node<K,V> → extinde → TreeNode<K,V>
LinkedList Node:
clasa statică Node<K,V> implementează Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; //pentru menținerea unei LinkedList.
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
TreeNode:
HashMap, în java 8 , utilizează RedBlackTree după un anumit prag cunoscut sub numele de TREEIFY_THRESHOLD (valoare implicită 8), deoarece oferă o complexitate de timp în cel mai rău caz de O(log n), în comparație cu LinkedList care oferă căutarea în O(n).
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // legături de arbore roșu-negru
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // necesar pentru a elimina legătura cu next la ștergere
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
Funcțiile HashMap
1. Se verifică dacă cheia este nulă sau nu . Rețineți că nu poate exista decât o singură cheie nulă în HashMap. dacă cheia este nulă , atunci cheile nule se mapează întotdeauna la hash 0, deci la indicele 0 al tabelului.
2. Dacă cheia nu este nulă, atunci metoda apelează metoda hashCode() asupra obiectului cheie (suprascrisă de utilizator în clasa respectivă de chei) și aplică valoarea hash returnată la propria funcție hash statică pentru a găsi o locație de tip bucket (matrice de suport) în care sunt stocate cheile și valorile sub forma unei clase imbricate numită Entry.
Locația bucket este un index al tabelului Entry și anume.
NOTA: calculăm din nou valoarea hash folosind hash(hashValue), deoarece ne apără împotriva unei funcții hash de slabă calitate.
3. Valoarea hash finală este utilizată pentru a găsi locația bucket în care este stocat obiectul Entry.
Complexitatea funcțiilor get() și put() este O(1), presupunând că funcția hash dispersează corect elementele între găleți.
Nota: După cum știm acum, în cazul unei coliziuni hash, obiectele de intrare sunt stocate ca nod într-o listă legată, iar metoda equals() este utilizată pentru a compara cheile. Această comparație pentru a găsi cheia corectă într-o listă legată este o operație liniară, astfel încât, în cel mai rău caz, complexitatea devine O(n).
Pentru a rezolva această problemă, elementele hash Java 8 utilizează arbori echilibrați în loc de liste legate după atingerea unui anumit prag. Ceea ce înseamnă că HashMap începe cu stocarea obiectelor de intrare în liste legate, dar după ce numărul de elemente dintr-un hash devine mai mare decât un anumit prag, hash-ul va trece de la utilizarea unei liste legate la un arbore echilibrat, ceea ce va îmbunătăți performanța în cel mai rău caz de la O(n) la O(log n).
Ce se întâmplă dacă două chei diferite au același cod hash?
4. La un index putem avea mai multe valori, deoarece putem avea coliziuni în hashing. Pentru a ne da seama de care dintre ele avem nevoie, HashMap apelează la ajutorul metodei equals().
Soluție, metoda equals() vine în ajutor. Din moment ce bucket este unul și avem două obiecte cu același cod hash .
Atunci, după ce extrage indexul cheii, extrage primul nod prezent pe acel index. Primul nod este apoi comparat cu cheia folosind equals(), Dacă acesta este nodul dorit, se returnează valoarea direct de aici.
Altfel, se află instanța nodului, pentru a afla dacă datele stocate în acest index sunt în formatul unei liste legate sau al unui arbore RedBlack.
După ce ne dăm seama de acest lucru, parcurgem lista legată sau arborele, comparând cheile din fiecare intrare folosind keys.equals() până când se returnează true. Apoi se returnează valoarea obiectului intrare corespunzătoare.
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {
Node<K,V> tab; //reprezintă Array of Entry
Node<K,V> first, e;
int n; K k;/* Verificarea dacă tabelul are intrări .*/
/* De asemenea, găsirea indexului pe baza hash-ului calculat în etapele anterioare, unde intrarea este stocată fie sub formă de listă, fie sub formă de nod de arbore.*/if ((tab = tabel) != null && (n = tab.length) > 0 &&(first = tab) != null) {
/*Căutarea primului nod din indexul obținut pe baza hash-ului.*/
if (first.hash == hash && /*verifică întotdeauna primul nod*/
((k = first.key) == key||| (key != null && key.equals(k))))
returnează first;/*Dacă primul nod din acel index nu este valoarea pe care o căutăm, atunci se trece la traversare.*/
if ((e = first.next) != null) {
if (first instance of TreeNode)
/*Fetching from Red Black Tree if starting Node on the index if of TreeNode .*/return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {/*Fetching from LinkedList dacă nodul de pornire este de tip Node și nu de Tree.*/
if (e.hash == hash &&((k = e.key) == key ||| (key != null &&key.equals(k))))
return e;
}
while ((e = e.next) != null);
}}}
return null;
}
PUT:
1. Se verifică dacă cheia este nulă sau nu .Dacă cheia este nulă , atunci cheile nule se mapează întotdeauna la hash 0, deci la indexul 0 al tabelului.
2. Dacă cheia nu este nulă, metoda apelează metoda hashCode() asupra obiectului cheie (suprascrisă de utilizator în clasa respectivă de chei) și aplică hashValue returnat la propria funcție hash statică pentru a găsi o locație de tip bucket (matrice de suport) în care cheile și valorile urmează să fie stocate sub forma unei clase imbricate numită Entry.Locația bucket este un index al Entry, și anume al tabelului.
3. Valoarea hash finală este utilizată pentru a găsi locația bucket în care urmează să fie stocat obiectul Entry. Apoi, cheile sunt parcurse în aceeași manieră ca cea descrisă în get(), pentru a verifica dacă cheia există deja; dacă există, valoarea este înlocuită cu noua valoare.
Altfel, se verifică dimensiunea listei,
Dacă aceasta depășește pragul TREEIFY_THRESHOLD (implicit 8), nodurile sunt restructurate în RedBlackTree și noua cheie este stocată cu valoarea din ea.
Dacă pragul nu este depășit, noua Intrare este creată cu cheia-valoare respectivă și este stocată.
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V> tab;
Node<K,V> p;
int n, i;
if ((tab = table) == null ||| (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab) == null)
tab = newNode(hash, key, value, null);
else {
/*SAME traversing as in get()*/
Node<K,V> e; K k;
if (p.hash == hash &&((k = p.key) == key || (key != null &&key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
/*Pentru a verifica dacă TREEIFY_THRESHOLD a fost depășit sau nu.*/if (binCount >= TREEIFY_THRESHOLD – 1) /* -1 pentru 1st*/
treeifyBin(tab, hash);
break;}if (e.hash = hash &&((k = e.key) == key || (key != null &&key.equals(k))))
break;
p = e;
}}}if (e != null) { /* maparea existentă pentru cheie*/
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}}++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;}
Mai multe de citit
Inmutabilitatea cheilor:
De ce Strings și Integers sunt o bună implementare a cheilor pentru HashMap? În principal pentru că sunt imuabile! Dacă alegeți să vă creați propria clasă de chei și nu o faceți imuabilă, s-ar putea să pierdeți date în interiorul HashMap.
Rehashing:
Rehashing este procesul de recalculare a codului hash al intrărilor deja stocate (perechi cheie-valoare), pentru a le muta într-un alt hashmap de dimensiuni mai mari atunci când este atins pragul factorului de încărcare.
Când numărul de elemente din hartă depășește limita factorului de încărcare (Load factor), în acel moment hashmap își dublează capacitatea și se recalculează codul hash al elementelor deja stocate pentru o distribuție uniformă a perechilor cheie-valoare în noile găleți.
De ce este necesar?
După dublarea capacității, ce se face cu perechile cheie-valoare deja prezente în buckets?
Dacă păstrăm perechile cheie-valoare existente așa cum sunt, atunci dublarea capacității poate să nu fie de ajutor, deoarece complexitatea O(1) va fi obținută numai dacă elementele sunt distribuite uniform în toate buckets.
Atunci, pentru fiecare pereche cheie-valoare existentă, codul hash este calculat din nou cu capacitatea crescută a hashmap-ului ca parametru, ceea ce duce fie la plasarea elementului în același bucket, fie în alt bucket.