Molte applicazioni informatiche (compilatori, database, cache, dizionari in Python, oggetti in JavaScript) hanno bisogno di memorizzare un insieme dinamico di coppie (chiave, valore) supportando le tre operazioni dell’ADT Dizionario:
insert(k, v): inserisce una nuova coppia;
search(k): recupera il valore associato alla chiave k;
delete(k): rimuove la coppia con chiave k.
Con gli array non ordinati e le liste concatenate la ricerca richiede tempo lineare O(n); con gli array ordinati e gli alberi binari di ricerca bilanciati si scende a O(logn). È possibile abbattere questa barriera e arrivare a un tempo medio costante O(1) (indipendente dal numero di elementi)?
Sì: le Tabelle di Hash (Hash Tables) raggiungono una complessità nel caso medio di Θ(1) per ricerca, inserimento e cancellazione!
Dall’Indirizzamento Diretto alle Funzioni di Hash
Il limite dell’Indirizzamento Diretto
Se le chiavi fossero numeri interi piccoli appartenenti all’universo U={0,1,…,m−1} (ad es. le matricole da 0 a 999), basterebbe allocare un array T[1000] e salvare l’elemento con chiave k direttamente nella cella T[k] in tempo Θ(1) (Tavola a Indirizzamento Diretto).
Tuttavia, nella realtà l’universo delle chiavi possibili U è immenso (es. tutti i codici fiscali di 16 caratteri, tutti gli indirizzi IPv6 o tutte le stringhe di identificatori di un programma), mentre il numero n di chiavi effettivamente memorizzate in un dato momento è molto piccolo (n≪∣U∣). Allocare un array di ∣U∣ celle sarebbe impossibile!
L’idea dell’Hashing
Invece di usare la chiave k direttamente come indice, allochiamo un array (Tabella di Hash) T[0 .. m-1] di dimensione m proporzionale a n, e usiamo una funzione matematica chiamata Funzione di Hash:
h:U⟶{0,1,…,m−1}
che trasforma in tempo Θ(1) qualsiasi chiave k∈U in un indice valido i=h(k) della tabella (detto bucket o slot).
flowchart LR
subgraph Universo["Universo delle Chiavi U (grandissimo)"]
K1["k₁ = 'mario'"]
K2["k₂ = 'anna'"]
K3["k₃ = 'luca'"]
end
H["<b>Funzione di Hash</b><br/>i = h(k) ∈ {0 .. m-1}"]
subgraph Tabella["Tabella di Hash T[0 .. m-1]"]
B0["0: NULL"]
B1["1: ('anna', 28)"]
B2["2: ('mario', 30) / ('luca', 24)<br/><i>Collisione se h(k₁) == h(k₃)!</i>"]
B3["m-1: NULL"]
end
K1 & K2 & K3 --> H
H --> B1 & B2
Il Fattore di Carico α e le Collisioni
Definiamo il Fattore di Carico (Load Factor) α di una tabella di hash come il rapporto tra il numero n di elementi memorizzati e il numero m di slot della tabella:
α=mn
Poiché ∣U∣>m, per il Principio dei Cassetti (Pigeonhole Principle) è matematicamente inevitabile che esistano chiavi distinte k1=k2 che vengono mappate nello stesso indiceh(k1)=h(k2). Questo evento si chiama Collisione (Collision).
Una buona tabella di hash deve quindi combinare due ingredienti:
Una ottima Funzione di Hash che distribuisca le chiavi nel modo più uniforme possibile tra i bucket {0,…,m−1} (Ipotesi di Hashing Uniforme Semplice);
Una strategia deterministica di risoluzione delle collisioni.
Progettazione delle Funzioni di Hash
Una funzione di hash h(k) deve essere deterministica (la stessa chiave k deve dare sempre lo stesso indice h(k)), veloce da calcolare in O(1) e uniforme (deve dipendere da tutti i bit/caratteri della chiave).
1. Metodo della Divisione (per chiavi intere)
h(k)=kmodm
Come scegliere m?
Evitare le potenze di 2 (m=2p): perché kmod2p estrae solo gli ultimi p bit meno significativi di k, ignorando completamente tutti gli altri bit!
Scelta ottima: scegliere per m un numero primo non troppo vicino a una potenza di 2 (ad es. m=97, m=1009).
2. Metodo della Moltiplicazione
Si sceglie una costante reale A∈(0,1) (Knuth suggerisce la sezione aurea coniugata A=25−1≈0.6180339887), si prende la parte frazionaria di k⋅A e la si moltiplica per m:
h(k)=⌊m⋅(k⋅A−⌊k⋅A⌋)⌋
3. Funzioni di Hash per Stringhe (Polinomiale / djb2)
Se la chiave è una stringa s=c0c1…cL−1, sommare semplicemente i codici ASCII (∑cimodm) è una pessima idea, perché tutti gli anagrammi (es. "roma", "amor", "mora") produrrebbero sistematicamente la stessa somma e colliderebbero!
Bisogna pesare la posizione di ciascun carattere con una potenza di una base prima (es. B=31 o B=33, come nel celebre algoritmo djb2 di Dan Bernstein):
/* Funzione di hash polinomiale (djb2) per stringhe C */size_t hash_stringa(const char *s, size_t m) { unsigned long hash = 5381; unsigned char c; while ((c = (unsigned char)*s++) != '\0') { hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ } return (size_t)(hash % m);}
Risoluzione delle Collisioni: i due paradigmi
Metodo 1: Concatenamento (Separate Chaining — Hashing Aperto)
Ogni cella T[i] della tabella non contiene direttamente un singolo elemento, ma è la testa di una lista concatenata che raccoglie tutti gli elementi le cui chiavi hanno indice di hash h(k)=i.
Inserimento (insert): Si calcola i=h(k), si verifica se k è già nella lista T[i] (aggiornandone il valore) e altrimenti si inserisce il nuovo nodo in testa alla lista T[i] in tempo O(1).
Ricerca (search) e Cancellazione (delete): Si calcola i=h(k) e si cerca/rimuove il nodo nella sola lista T[i].
Lunghezza media delle liste e Complessità:
Con n elementi distribuiti uniformemente su m liste, la lunghezza media di ciascuna lista è esattamente pari al fattore di carico α=mn! Pertanto la ricerca costa nel caso medio Θ(1+α) (che è Θ(1) se manteniamo α≤1), mentre nel caso peggiore (tutte le n chiavi collidono nello stesso bucket!) degenera a Θ(n).
Metodo 2: Indirizzamento Aperto (Open Addressing — Hashing Chiuso)
Nell’indirizzamento aperto non si usano liste esterne né puntatori: tutti gli elementi risiedono direttamente dentro l’array T[0 .. m-1] (quindi deve sempre valere n≤m, ovvero α≤1).
Quando vogliamo inserire una chiave k e scopriamo che la cella principale h(k) è già occupata, ispezioniamo (probing) una sequenza deterministica di celle alternative nella tabella:
h(k,j)∈{0,…,m−1}per j=0,1,2,…,m−1
finché non troviamo una cella libera! Esistono tre schemi classici di scansione (probing):
Scansione Lineare (Linear Probing):
h(k,j)=(h(k)+j)modm(j=0,1,2,…)
Se la cella h(k) è occupata, prova la cella successiva h(k)+1, poi h(k)+2, ecc. (ripartendo da 0 dopo m−1).
Difetto: soffre di Addensamento Primario (Primary Clustering): le chiavi che collidono formano lunghi blocchi contigui di celle occupate, aumentando la probabilità di nuove collisioni su quel blocco.
Scansione Quadratica (Quadratic Probing):
h(k,j)=(h(k)+c1j+c2j2)modm
Fa salti quadratici (+1,+4,+9,…) evitando i blocchi contigui dell’addensamento primario.
Doppio Hashing (Double Hashing):
h(k,j)=(h1(k)+j⋅h2(k))modm
Usa una seconda funzione di hashh2(k)=0 (coprima con m) per determinare il passo del salto: così due chiavi che collidono in h1 faranno salti di ampiezza diversa!
Il problema della Cancellazione nell'Indirizzamento Aperto: i Tombstone (DELETED)
Nell’indirizzamento aperto, non possiamo cancellare un elemento rimettendo semplicemente la sua cella a EMPTY (VUOTA)!
Perché? Supponiamo che k1 e k2 abbiano lo stesso hash h(k1)=h(k2)=3: k1 viene inserito in T[3] e k2 scivola per linear probing in T[4]. Se poi cancellassimo k1 mettendo T[3] = EMPTY, una successiva ricerca di k2 partirebbe da T[3], vedrebbe EMPTY e si fermerebbe subito concludendo erroneamente che k2 non esiste!
Soluzione: Si usa la cancellazione logica marcando la cella rimossa con uno stato speciale DELETED (Tombstone / Lapide):
La Ricerca (search) tratta DELETED come “occupata” e continua a scorrere oltre la lapide;
L’Inserimento (insert) tratta DELETED come “libera” e può riutilizzare la cella!
Marcatori, ricostruzione e ipotesi sui costi
Con probing lineare e cinque celle, le chiavi 1 e 6 partono entrambe dalla cella 1 usando chiave % 5. Dopo gli inserimenti occupano le celle 1 e 2. Rimuovendo 1, mettiamo DELETED nella cella 1. Cercando 6 continuiamo oltre quel marcatore. Un’inserzione può ricordare la prima cella cancellata e proseguire per verificare che la chiave non esista più avanti. Ci fermiamo a una cella mai usata o dopo un giro completo.
Il rapporto fra elementi vivi e capacità è il fattore di carico. Nel probing contano anche i marcatori, perché allungano le ricerche. Per un rehash si crea una tabella vuota e si reinseriscono le chiavi vive con gli indici della nuova capacità. I marcatori spariscono. Una soglia di crescita è una scelta di implementazione. Nel concatenamento, il costo atteso Θ(1+α) suppone una distribuzione uniforme e costo costante per hash e confronto. Nel probing, costo medio e clustering dipendono anche dalla sequenza di tentativi. Nel caso peggiore una ricerca può ancora esaminare tutta la tabella.
Un hash per tabelle mira a distribuire le chiavi e rendere le operazioni rapide. Un hash crittografico persegue anche proprietà come resistenza a collisioni trovate intenzionalmente e difficoltà di ricavare un input da un digest. Una funzione come il resto della divisione è utile per calcolare un indice e non offre queste proprietà.
Esempi guidati
Esempio 1: Traccia numerica completa di Concatenamento vs Linear Probing
Problema: Sia data una Tabella di Hash di dimensione m=7 con funzione di hash h(k)=kmod7. Inseriamo nell’ordine le chiavi: 10, 24, 31, 17, 25 sia con Concatenamento sia con Indirizzamento Aperto a Scansione Lineare.
Calcolo degli indici iniziali h(k)=kmod7:
h(10)=10mod7=3
h(24)=24mod7=3(Collisione in 3!)
h(31)=31mod7=3(Collisione in 3!)
h(17)=17mod7=3(Collisione in 3!)
h(25)=25mod7=4
Con Concatenamento (Chaining) (inserimento in testa alle liste):
T[0]: NULL
T[1]: NULL
T[2]: NULL
T[3]: 17 -> 31 -> 24 -> 10 -> NULL
T[4]: 25 -> NULL
T[5], T[6]: NULL.
Con Indirizzamento Aperto (Linear Probingh(k,j)=(h(k)+j)mod7):
Inserisci 25 (h=4): T[4] occupata (da 24! Ecco il Primary Clustering!), T[5] occupata, T[6] occupata → fa il giro circolare a T[0] che è vuota →T[0] = 25!
Tabella finale: T = [ 25, _, _, 10, 24, 31, 17 ].
Esempio 2: Implementazione in C di una Tabella di Hash con Concatenamento
#include <stdio.h>#include <stdlib.h>#include <string.h>#define NUM_BUCKETS 13 /* Numero primo */typedef struct HashNodo { char *chiave; int valore; struct HashNodo *next;} HashNodo;typedef struct { HashNodo *buckets[NUM_BUCKETS]; size_t num_elementi;} HashTable;void ht_init(HashTable *ht) { for (int i = 0; i < NUM_BUCKETS; i++) { ht->buckets[i] = NULL; } ht->num_elementi = 0;}/* Inserisce o aggiorna la coppia (chiave, valore) */int ht_inserisci(HashTable *ht, const char *chiave, int valore) { size_t idx = hash_stringa(chiave, NUM_BUCKETS); /* 1. Controlla se la chiave esiste già nel bucket idx */ for (HashNodo *curr = ht->buckets[idx]; curr != NULL; curr = curr->next) { if (strcmp(curr->chiave, chiave) == 0) { curr->valore = valore; /* Aggiorna il valore esistente */ return 1; } } /* 2. Altrimenti crea un nuovo nodo e inseriscilo in testa al bucket idx */ HashNodo *nuovo = (HashNodo *)malloc(sizeof(HashNodo)); if (!nuovo) return 0; nuovo->chiave = (char *)malloc(strlen(chiave) + 1); if (!nuovo->chiave) { free(nuovo); return 0; } strcpy(nuovo->chiave, chiave); nuovo->valore = valore; nuovo->next = ht->buckets[idx]; ht->buckets[idx] = nuovo; ht->num_elementi++; return 1;}/* Cerca una chiave: restituisce 1 se trovata (scrivendo in *out_val), 0 se assente */int ht_cerca(const HashTable *ht, const char *chiave, int *out_val) { size_t idx = hash_stringa(chiave, NUM_BUCKETS); for (const HashNodo *curr = ht->buckets[idx]; curr != NULL; curr = curr->next) { if (strcmp(curr->chiave, chiave) == 0) { if (out_val) *out_val = curr->valore; return 1; } } return 0;}
Errori frequenti
Errori da evitare
Confrontare solo gli hash h(k1)==h(k2) invece delle chiavi effettive strcmp(k1, k2) == 0:
Avere lo stesso valore di hash non significa essere la stessa chiave (potrebbe essere una collisione!). Quando si scorre la lista del bucket T[h(k)], bisogna sempre confrontare la chiave memorizzata nel nodo con la chiave cercata tramite strcmp (o == per gli interi).
Lasciare che il fattore di carico α si avvicini a 1 nell’Indirizzamento Aperto:
Nel probing lineare, una tabella vicina alla saturazione o piena di marcatori può richiedere molti tentativi. Una politica può far crescere o ricostruire la tabella oltre una soglia scelta, per esempio 0.75, reinserendo gli elementi con la nuova funzione di indice.
Nel Rehashing, copiare i vecchi bucket con memcpy senza ricalcolare la funzione di hash:
Poiché la dimensione della tabella cambia da m a m′, l’indice kmodm′ di ogni chiave cambia! Bisogna ricalcolare l’hash di ogni singolo elemento.
Esercizi di prova
Esercizio 1. Fattore di carico α nei due modelli (Base)
In una tabella di hash di dimensione m=20 vengono inserite n=30 chiavi distinte.
Quanto vale il fattore di carico α?
È possibile memorizzare queste 30 chiavi usando l’Indirizzamento Aperto senza ridimensionare la tabella? E usando il Concatenamento? Qual è la lunghezza media delle liste nel Concatenamento?
Soluzione
Il fattore di carico vale α=mn=2030=1.5.
Con l’Indirizzamento Aperto è impossibile senza fare rehashing, perché ogni slot dell’array può ospitare al massimo 1 chiave (quindi α non può mai superare 1, ovvero n≤20).
Con il Concatenamento è invece perfettamente possibile: tutte le 30 chiavi vengono inserite nelle 20 liste collegate, e la lunghezza media di ciascuna lista è esattamente α=1.5 nodi.
Esercizio 2. Simulazione di Scansione Lineare vs Scansione Quadratica (Base)
Data una tabella di hash con m=11 a indirizzamento aperto inizialmente vuota e funzione base h(k)=kmod11, mostra la posizione finale in cui vengono inserite le chiavi 22, 1, 13, 11, 24, 33:
Con Scansione Lineareh(k,j)=(h(k)+j)mod11;
Con Scansione Quadraticah(k,j)=(h(k)+j2)mod11.
Soluzione
Calcoliamo prima h(k)=kmod11: h(22)=0,h(1)=1,h(13)=2,h(11)=0,h(24)=2,h(33)=0.
Esercizio 3. Cancellazione logica con DELETED nel Linear Probing (Intermedio)
Nella tabella lineare ottenuta al punto 1 dell’Esercizio 2 ([22, 1, 13, 11, 24, 33, ...]), eseguiamo delete(13) (marcando T[2] = DELETED), poi search(24) e infine insert(35). Mostra cosa accade in ciascuna operazione.
Soluzione
delete(13): h(13)=2, troviamo 13 in T[2] e lo sostituiamo con il tombstoneT[2] = DELETED.
search(24): h(24)=2. Guardiamo T[2]: troviamo DELETED (non EMPTY!), quindi non ci fermiamo: proseguiamo a T[3] (contiene 11=24) e poi a T[4] dove troviamo 24!
insert(35): h(35)=35mod11=2. Guardiamo T[2]: contiene DELETED. Poiché 35 non è presente più avanti nella catena, riutilizziamo lo slot T[2] scrivendo T[2] = 35!
Esercizio 4. Cancellazione di una chiave da una Tabella di Hash con Concatenamento (Intermedio)
Scrivi per la HashTable dell’Esempio Guidato 2 la funzione int ht_rimuovi(HashTable *ht, const char *chiave) che rimuove il nodo corrispondente a chiave liberando sia la stringa sia il nodo, e restituisce 1 (o 0 se assente).
Data una tabella con m=7, h1(k)=kmod7 e seconda funzione di passo h2(k)=1+(kmod5), determina la sequenza di indici ispezionati da h(k,j)=(h1(k)+j⋅h2(k))mod7 per la chiave k=17 al variare di j=0,1,2,3. Perché è fondamentale che h2(k) non possa mai restituire 0?
Soluzione
Per k=17:
h1(17)=17mod7=3
h2(17)=1+(17mod5)=1+2=3
Sequenza di scansione (3+j⋅3)mod7:
j=0: (3+0)mod7=3
j=1: (3+3)mod7=6
j=2: (3+6)mod7=9mod7=2
j=3: (3+9)mod7=12mod7=5
Se h2(k) valesse 0, per ogni j≥0 avremmo h(k,j)=(h1(k)+j⋅0)modm=h1(k): l’algoritmo resterebbe bloccato all’infinito sulla stessa cella iniziale senza mai avanzare!
Esercizio 6. Confronto tra Tabelle di Hash e Alberi Binari di Ricerca Bilanciati (Avanzato)
Se le Tabelle di Hash effettuano ricerca, inserimento e cancellazione in tempo medio Θ(1) mentre gli Alberi Binari di Ricerca (BST) bilanciati richiedono Θ(logn), in quali situazioni pratiche conviene comunque preferire un BST rispetto a una Tabella di Hash?
Soluzione
I BST bilanciati sono preferibili alle Tabelle di Hash in tre scenari fondamentali:
Operazioni basate sull’ordine delle chiavi: Una Tabella di Hash mescola le chiavi in modo pseudo-casuale! Stampare tutte le chiavi in ordine crescente, trovare il minimo/massimo o cercare tutte le chiavi comprese in un intervallo [k1,k2] (Range Query) è immediato in un BST (tramite visita In-Order), mentre in una Hash Table richiede di scandire l’intera tabella Θ(m+n) e poi ordinarla in Θ(nlogn)!
Garanzia sul Caso Peggiore (Real-Time Systems): Un BST bilanciato (AVL, Red-Black Tree) garantisce O(logn)anche nel caso peggiore assoluto, mentre una Hash Table soggetta a collisioni malevole (Hash-Flooding DoS) può degradare a Θ(n) per singola operazione.
Assenza di una buona funzione di hash: Per usare un BST basta saper confrontare due chiavi con <.
Provenienza del materiale
Dispensa ufficiale del corso: C1PROG1U6L5_Tabelle_di_Hash.pdf (Unità 6, Lezione 5 — Tabelle di Hash).
Marco Anisetti, Algoritmi e strutture dati dinamiche, C1PROG1_Appunti_di_fine_unità_6.pdf, cap. 5.