Tabella hash — Come funziona l'hashing e la risoluzione delle collisioni

Una tabella hash memorizza coppie chiave-valore applicando una funzione di hash a ogni chiave per ottenere un indice di un array. Questo permette alla tabella di andare subito vicino alla posizione giusta invece di scorrere tutti gli elementi memorizzati uno per uno.

Per questo motivo, in media le tabelle hash hanno spesso complessità vicina a $O(1)$ per ricerca, inserimento ed eliminazione. Ma c'è una condizione importante: la funzione di hash deve distribuire le chiavi in modo ragionevolmente uniforme, e la tabella deve comunque avere una regola per gestire le collisioni.

Cosa fa una tabella hash

Una tabella hash memorizza coppie chiave-valore come "name" -> "Ada" oppure 42 -> "blue". Ha due parti principali:

• un array di slot o bucket
• una funzione di hash che associa ogni chiave a uno di questi slot

Se l'array ha $m$ slot, puoi pensare alla funzione di hash come a una regola che produce un indice da $0$ a $m-1$.

Per un piccolo esempio con interi, la regola potrebbe essere

$$h(k) = k \bmod 8$$

Allora la chiave $10$ va nello slot $2$ perché $10 \bmod 8 = 2$.

Le vere funzioni di hash sono progettate con più attenzione, soprattutto per stringhe e insiemi di dati più grandi. Ma l'idea di base resta la stessa: calcolare rapidamente un indice e poi controllare l'elemento memorizzato lì.

Perché le collisioni hash sono inevitabili

Una collisione si verifica quando due chiavi diverse vengono associate allo stesso slot.

È normale, perché di solito la tabella ha meno slot del numero di chiavi possibili. Con

$$h(k) = k \bmod 8$$

le chiavi $10$, $18$ e $26$ finiscono tutte nello slot $2$. Quindi, anche se la funzione sta lavorando esattamente come definita, la tabella ha comunque un conflitto da risolvere.

Perciò una tabella hash non garantisce uno slot unico per ogni chiave. Garantisce un modo veloce per restringere la ricerca, a patto che le collisioni siano gestite bene.

Esempio svolto: una tabella, una collisione

Supponiamo che una tabella abbia $8$ slot e usi

$$h(k) = k \bmod 8$$

Inserisci le chiavi $10$, $18$ e $7$.

Per prima cosa, $10$ va nello slot $2$ perché $10 \bmod 8 = 2$.

Poi anche $18$ produce hash nello slot $2$, quindi si verifica una collisione.

Infine $7$ va nello slot $7$, quindi quell'inserimento non collide.

Lo schema utile è sempre lo stesso:

1. Calcola l'hash della chiave.
2. Vai allo slot suggerito.
3. Se lì c'è già una chiave diversa, applica la regola di gestione delle collisioni.

Una volta chiarito questo schema, le due principali strategie di gestione delle collisioni diventano più facili da capire.

Concatenamento vs. indirizzamento aperto

Il concatenamento mantiene un bucket in ogni slot

Nel concatenamento, ogni slot memorizza una piccola collezione di elementi invece di uno solo.

Se $10$ e $18$ finiscono entrambi nello slot $2$, il bucket $2$ potrebbe contenere

• $(10, \text{value}_1)$
• $(18, \text{value}_2)$

Per trovare la chiave $18$, la tabella va direttamente al bucket $2$ e confronta solo gli elementi presenti in quel bucket.

Il concatenamento è concettualmente semplice, e l'eliminazione di solito è più facile che nell'indirizzamento aperto. Lo svantaggio è che bucket lunghi rendono le operazioni più lente.

L'indirizzamento aperto resta dentro l'array

Nell'indirizzamento aperto, ogni slot dell'array contiene al massimo un elemento. Se lo slot iniziale è occupato, la tabella prova altri slot secondo una regola fissa.

Una regola comune è il linear probing: se lo slot $2$ è occupato, si prova il $3$, poi il $4$, poi il $5$, tornando all'inizio se necessario.

Questo evita liste di bucket separate, ma gli slot occupati vicini possono accumularsi formando cluster. Un altro dettaglio è che ricerca ed eliminazione devono rispettare la stessa regola di probing usata durante l'inserimento.

Quando $O(1)$ è un'affermazione corretta

Le tabelle hash sono spesso descritte come strutture con ricerca, inserimento ed eliminazione in $O(1)$ in media. Questa affermazione sul caso medio dipende da alcune condizioni:

• la funzione di hash distribuisce le chiavi in modo ragionevolmente uniforme
• il fattore di carico resta sotto controllo
• la strategia di gestione delle collisioni è implementata correttamente

Il fattore di carico è il rapporto

$$\text{load factor} = \frac{\text{number of stored entries}}{\text{number of slots}}$$

Se la tabella diventa troppo piena, le collisioni diventano più frequenti e le prestazioni peggiorano. Per questo molte implementazioni ridimensionano l'array man mano che si riempie.

Nel caso peggiore, le prestazioni possono comunque degradare verso $O(n)$ se troppe chiavi si accumulano nella stessa zona.

Errori comuni con le tabelle hash

Pensare che le collisioni significhino che la funzione di hash ha fallito

Non è così. Le collisioni sono previste. La vera domanda è se la tabella le gestisce in modo efficiente.

Trattare $O(1)$ come se fosse incondizionato

$O(1)$ di solito è un'affermazione sul caso medio, non una promessa valida per ogni input e in ogni momento.

Confondere questo hashing con la crittografia

Una funzione di hash, nel contesto base delle strutture dati, serve soprattutto per l'indicizzazione veloce, non per la segretezza. Sono obiettivi diversi.

Dimenticare di confrontare la chiave reale

Due chiavi possono avere lo stesso risultato di hash. Dopo essere arrivata nel bucket giusto o nella posizione giusta del probing, la tabella deve comunque verificare se la chiave corrisponde davvero.

Quando si usano le tabelle hash

Le tabelle hash si usano ogni volta che è importante una ricerca veloce basata su chiave. Esempi comuni sono dizionari, tabelle dei simboli, cache, indicizzazione e conteggio delle frequenze nei dati.

Sono una scelta molto adatta quando la ricerca esatta per chiave è più importante del mantenere gli elementi in ordine. Se ti servono attraversamento ordinato, query su intervalli o valori più vicini, può essere migliore un'altra struttura.

Prova un esempio simile di collisione

Prendi un piccolo array con $8$ slot e usa $h(k)=k \bmod 8$. Inserisci alcune chiavi come $3$, $11$, $19$ e $27$. Poi risolvi le collisioni una volta con il concatenamento e una volta con il linear probing.

Questo semplice esercizio rende molto concreta l'idea principale: le collisioni sono inevitabili, e la regola usata per gestirle cambia il comportamento della tabella. Se vuoi fare un passo utile in più, prova una tua versione con una dimensione diversa della tabella e osserva come cambiano le collisioni.