Vorbește despre tabelele hash și principiul lor de funcționare principal.

Tabela de hash (mapă hash) este o structură de date care implementează un array asociativ, mapând cheile la valori.

Principiul de funcționare:

1. Hashing: Pentru fiecare cheie, se calculează un cod hash — o valoare numerică de dimensiune fixă folosind o funcție hash. O funcție hash bună distribuie codurile hash uniform pe întregul interval de ieșiri.
2. Indexare: Codul hash calculat este folosit pentru a determina indexul (poziția) în array unde va fi stocată valoarea corespunzătoare. De obicei, hash(key) % dimensiunea_array dă indexul final.
3. Stocare: În array, la indexul calculat, se stochează un cuplu (cheie, valoare).
4. Căutare: Pentru a găsi o valoare după cheie, se calculează din nou codul hash al cheii, se determină indexul, și se extrage valoarea de la acel index.
5. Coliziuni: Apare atunci când chei diferite au același cod hash. Există mai multe metode de rezolvare a coliziunilor:
   • Metoda lanțurilor (Separate Chaining): La fiecare index al array-ului se păstrează o listă (sau altă structură de date) care conține toate cuplurile (cheie, valoare) ale căror coduri hash conduc la acel index.
   • Metoda adresării deschise (Open Addressing): Când apare o coliziune, se caută alt loc liber în array conform unei reguli stabilite (sondare liniară, sondare pătratică, dublu hash).

Avantaje:

• În medie, operațiile de inserare, ștergere și căutare au complexitate O(1), dacă funcția hash este bună și coliziunile sunt rare.

Dezavantaje:

• Cazul cel mai rău în performanță poate fi O(n), dacă toate cheile sunt hash-uite în același index (de exemplu, cu o funcție hash slabă sau multe coliziuni).
• Este nevoie de memorie suplimentară pentru array și, posibil, pentru rezolvarea coliziunilor.

În Swift, tabelele de hash sunt implementate cu tipul Dictionary.

// Exemplu de utilizare a Dictionary în Swift
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Acces după cheie
let value = myDictionary["banana"] // Obține Optional(2)

// Adăugare/actualizare
myDictionary["grape"] = 4 // Adaugă un nou cuplu
myDictionary["apple"] = 10 // Actualizează valoarea pentru cheia "apple"

// Ștergere
myDictionary["orange"] = nil // Șterge cuplul cu cheia "orange"