Da quali componenti è composta una tabella hash?

Una tabella hash è composta da:

1. Array (o lista): La struttura dati principale in cui vengono memorizzati gli elementi. A volte vengono chiamati "secchi" (buckets) o "slot".
2. Funzione hash: Funzione che prende una chiave come input e restituisce un indice (numero intero) nell'array. Una buona funzione hash garantisce una distribuzione uniforme delle chiavi nell'array, minimizzando le collisioni.
3. Meccanismo di gestione delle collisioni: Metodo per risolvere la situazione in cui la funzione hash genera lo stesso indice per chiavi diverse. Due metodi principali:
   • Chaining (Concatenamento): Ogni elemento dell'array memorizza un puntatore a una lista (lista collegata, albero B, ecc.) di elementi hashati in quell'indice.
   • Open Addressing (Indirizzamento aperto): In caso di collisione, si cerca un altro spazio libero nell'array per posizionare l'elemento. Strategie di ricerca:
     • Probing lineare (Linear Probing)
     • Probing quadratico (Quadratic Probing)
     • Double hashing (Double Hashing)
4. Operazioni: Implementazione delle operazioni di base: inserimento (insert), ricerca (search), cancellazione (delete). Queste operazioni usano la funzione hash per determinare la posizione degli elementi nell'array e il meccanismo di gestione delle collisioni se necessario.