Che cos'è una tabella hash?

Una tabella hash è una struttura dati che memorizza coppie chiave-valore, come un dizionario che cerca le voci in base alla chiave. La magia sta nella velocità: una tabella hash ben realizzata trova, inserisce o rimuove una voce in tempo medio O(1), indipendentemente dal numero di voci che contiene.

Il trucco sta nella funzione hash. Ogni chiave viene convertita in un indice di bucket, così sappiamo esattamente dove cercare senza esaminare l'intera tabella. Quando due chiavi diverse finiscono nello stesso bucket (una collisione), le teniamo insieme in una lista in quel bucket. Questa strategia si chiama concatenamento.

Le cinque operazioni principali su una tabella hash sono:

1. Put: memorizza una coppia chiave-valore oppure aggiorna il valore se la chiave esiste già.
2. Get: cerca il valore associato a una determinata chiave.
3. ContainsKey: verifica se una chiave è memorizzata nella tabella.
4. Remove: elimina una coppia chiave-valore.
5. Size: restituisce il numero di coppie attualmente memorizzate.

Creiamo una classe HashMap!