Di cosa è composta una tabella hash?

Una tabella hash è composta da un array di dimensione fissa (bucket o slot) e da una funzione hash.

• Array (Bucket/Slot): Rappresenta una sequenza di celle in cui vengono memporizzate coppie "chiave-valore". La dimensione dell'array determina il numero di possibili posti per memorizzare gli elementi.

• Funzione hash: Trasforma la chiave in un valore intero (codice hash), che viene usato per determinare l'indice della cella nell'array (bucket), dove verrà memorizzato o da cui verrà estratto il valore corrispondente.

Inoltre, può essere presente:

• Strategia di risoluzione delle collisioni: Meccanismo per gestire situazioni in cui chiavi diverse generano lo stesso codice hash e puntano alla stessa cella dell'array. Strategie comuni:
  • Chaining (incatenamento): Ogni cella dell'array memorizza un puntatore a una lista collegata (o altra struttura dati), contenente tutte le coppie "chiave-valore" i cui codici hash puntano a quella cella.
  • Open addressing (indirizzamento aperto): In caso di collisione, si cerca una cella libera nell'array seguendo una regola determinata (ad esempio, sondaggio lineare o quadratico).