Cos'è una tabella hash?

Una tabella hash è una struttura dati che implementa un array associativo (dizionario). Essa memorizza coppie "chiave-valore", dove le chiavi sono uniche.

Principi di base:

• Funzione hash: Trasforma la chiave in un numero (codice hash o indice). Questo indice indica il luogo di memorizzazione del valore nell'array (cestino).
• Array (cestini): Memorizzazione reale delle coppie "chiave-valore".
• Collisioni: Situazione in cui chiavi diverse generano lo stesso codice hash.

Soluzione alle collisioni:

• Metodo di chaining (separate chaining): In ogni cestino si memorizza una lista (o altra struttura dati) di elementi con lo stesso codice hash.
• Indirizzamento aperto (open addressing): In caso di collisione, si cerca un cestino libero utilizzando diverse strategie (sondaggio lineare, sondaggio quadratico, doppio hashing).

Caratteristiche:

• Accesso rapido: Nel caso ideale O(1) per operazioni di inserimento, ricerca e cancellazione.
• Dipendenza dalla funzione hash: La qualità della funzione hash e la strategia di risoluzione delle collisioni influenzano molto le prestazioni.
• Utilizzo della memoria: Richiede memoria aggiuntiva per l'array dei cestini.

Utilizzo in QA:

• Memorizzazione di dati di test (chiave - nome del parametro, valore - valore atteso o reale).
• Verifica dell'unicità degli elementi (ad esempio, ID utenti).
• Implementazione di cache.