Parla delle tabelle hash e del loro principio di funzionamento principale.

La tabella hash (mappa hash) è una struttura dati che implementa un array associativo, mappando le chiavi ai valori.

Principio di funzionamento:

1. Hashing: Per ogni chiave, si calcola un codice hash, un valore numerico di dimensione fissa tramite una funzione hash. Una buona funzione hash distribuisce i codici hash in modo uniforme su tutto l'intervallo di output.
2. Indicizzazione: Il codice hash calcolato viene usato per determinare l'indice (posizione) nell'array dove verrà memorizzato il valore corrispondente. Spesso, hash(key) % dimensione_array fornisce l'indice finale.
3. Memorizzazione: Nell'array, all'indice calcolato, si memorizza una coppia (chiave, valore).
4. Ricerca: Per trovare un valore tramite la chiave, si ricalcola il codice hash della chiave, si determina l'indice, e a quell'indice si estrae il valore.
5. Collisioni: Si verificano quando chiavi diverse hanno lo stesso codice hash. Esistono vari metodi per risolvere le collisioni:
   • Metodo di chaining (Separate Chaining): Ad ogni indice dell'array si mantiene una lista (o altra struttura dati) contenente tutte le coppie (chiave, valore) i cui codici hash portano a quell'indice.
   • Metodo di open addressing (Open Addressing): Quando si verifica una collisione, si cerca un altro spazio libero nell'array secondo una regola determinata (sondaggio lineare, sondaggio quadratico, doppio hashing).

Vantaggi:

• In media, le operazioni di inserimento, rimozione e ricerca hanno complessità O(1), se la funzione hash è buona e le collisioni sono rare.

Svantaggi:

• Il caso peggiore in termini di prestazioni può essere O(n), se tutte le chiavi vengono hashate nello stesso indice (ad esempio, con una cattiva funzione hash o molte collisioni).
• È richiesta memoria aggiuntiva per l'array e, possibilmente, per risolvere le collisioni.

In Swift, le tabelle hash sono implementate con il tipo Dictionary.

// Esempio di utilizzo di Dictionary in Swift
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Accesso tramite chiave
let value = myDictionary["banana"] // Ottiene Optional(2)

// Aggiunta/aggiornamento
myDictionary["grape"] = 4 // Aggiunge una nuova coppia
myDictionary["apple"] = 10 // Aggiorna il valore per la chiave "apple"

// Rimozione
myDictionary["orange"] = nil // Rimuove la coppia con chiave "orange"