Ce este un hash și cum este utilizat în dicționarele…

Hash (sau valoare hash) este o valoare numerică de lungime fixă calculată pe baza conținutului unui obiect folosind o funcție hash. O funcție hash bună asigură determinismul (același obiect produce întotdeauna același hash) și urmărește o distribuție uniformă a hash-urilor pentru diferite obiecte.

În Python, dicționarele (tipul dict) utilizează hashing pentru a stoca și căuta eficient perechi de tip "cheie-valoare". Cheile trebuie să fie hashabile, adică să dețină metoda __hash__() și să fie imutable sau să aibă o implementare de __eq__() și __hash__() care să garanteze că obiectele egale după __eq__() au același hash.

Procesul de funcționare al unui dicționar cu hash-uri:

Inserare: La adăugarea unui cuplu (cheie, valoare), se calculează hash-ul cheii. Pe baza hash-ului, se determină un loc aproximativ (coș sau "bucket") pentru stocarea acestui cuplu în memorie. Dacă mai multe chei au același hash (coliziune), cuplurile sunt stocate în acest coș, adesea sub formă de listă înlănțuită sau alt mecanism de rezolvare a coliziunilor.
Căutare: La căutarea unei valori după cheie, se calculează hash-ul cheii furnizate. Folosind hash-ul, dicționarul găsește rapid coșul corespunzător. Apoi, în interiorul acestui coș, se compară cheile (folosind metoda __eq__) pentru a găsi cheia corectă și a extrage valoarea asociată.

Avantajele utilizării hash-urilor:

Eficiență: În medie, operațiile de inserare, ștergere și căutare într-un dicționar se realizează cu o complexitate de timp constantă O(1), indiferent de dimensiunea dicționarului.
Acces rapid: Hash-ul permite accesul rapid la locația presupusă a datelor, evitând parcurgerea tuturor elementelor.

Limitări și caracteristici:

Chei hashabile: Așa cum s-a menționat, cheile trebuie să fie hashabile. Tipurile mutabile, precum listele (list) și mulțimile (set), nu sunt hashabile implicit și nu pot fi folosite ca chei de dicționar.
Coliziuni: Deși funcțiile hash încearcă să minimizeze coliziunile, acestea pot apărea, ceea ce poate încetini ușor operațiile în cel mai rău caz (influențează constanta în O(1)).
Ordine: Până la Python 3.7, ordinea elementelor din dicționar depindea de ordinea inserției și de hash-urile cheilor. Începând cu Python 3.7, dicționarele păstrează ordinea inserției cheilor ca un efect secundar al implementării, dar acest lucru nu face parte din mecanismul de hash.

Exemplu de obiect hashabil și nehashabil:

# Obiect hashabil (imutable)
string_key = "salut"
int_key = 123
tuple_key = (1, 2)

print(hash(string_key))
print(hash(int_key))
print(hash(tuple_key))

# Obiect nehashabil (mutabil)
list_key = [1, 2]
# print(hash(list_key)) # Va genera o eroare de tip

# Exemplu de utilizare într-un dicționar
my_dict = {
    string_key: "lume",
    int_key: 456,
    tuple_key: "un tuple"
}

print(my_dict[string_key])
print(my_dict[int_key])
print(my_dict[tuple_key])

Astfel, hash-ul este un mecanism fundamental care permite dicționarelor în Python să atingă performanțe ridicate în operațiile lor, bazat pe calculul rapid al reprezentării numerice a cheii.

Ce este un hash și cum este utilizat în dicționarele din Python?