Tabelle di Hash

Come l’hash riduce il costo della ricerca

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 ; con gli array ordinati e gli alberi binari di ricerca bilanciati si scende a . È possibile abbattere questa barriera e arrivare a un tempo medio costante (indipendente dal numero di elementi)?

Sì: le Tabelle di Hash (Hash Tables) raggiungono una complessità nel caso medio di 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 (ad es. le matricole da 0 a 999), basterebbe allocare un array T[1000] e salvare l’elemento con chiave direttamente nella cella T[k] in tempo (Tavola a Indirizzamento Diretto).

Tuttavia, nella realtà l’universo delle chiavi possibili è 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 di chiavi effettivamente memorizzate in un dato momento è molto piccolo (). Allocare un array di celle sarebbe impossibile!

L’idea dell’Hashing

Invece di usare la chiave direttamente come indice, allochiamo un array (Tabella di Hash) T[0 .. m-1] di dimensione proporzionale a , e usiamo una funzione matematica chiamata Funzione di Hash:

che trasforma in tempo qualsiasi chiave in un indice valido 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 di elementi memorizzati e il numero di slot della tabella:

Poiché , per il Principio dei Cassetti (Pigeonhole Principle) è matematicamente inevitabile che esistano chiavi distinte che vengono mappate nello stesso indice . Questo evento si chiama Collisione (Collision).

Una buona tabella di hash deve quindi combinare due ingredienti:

  1. Una ottima Funzione di Hash che distribuisca le chiavi nel modo più uniforme possibile tra i bucket (Ipotesi di Hashing Uniforme Semplice);
  2. Una strategia deterministica di risoluzione delle collisioni.

Progettazione delle Funzioni di Hash

Una funzione di hash deve essere deterministica (la stessa chiave deve dare sempre lo stesso indice ), veloce da calcolare in e uniforme (deve dipendere da tutti i bit/caratteri della chiave).

1. Metodo della Divisione (per chiavi intere)

  • Come scegliere ?
    • Evitare le potenze di 2 (): perché estrae solo gli ultimi bit meno significativi di , ignorando completamente tutti gli altri bit!
    • Scelta ottima: scegliere per un numero primo non troppo vicino a una potenza di 2 (ad es. , ).

2. Metodo della Moltiplicazione

Si sceglie una costante reale (Knuth suggerisce la sezione aurea coniugata ), si prende la parte frazionaria di e la si moltiplica per :

3. Funzioni di Hash per Stringhe (Polinomiale / djb2)

Se la chiave è una stringa , sommare semplicemente i codici ASCII () è 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. o , 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 .

flowchart LR
    subgraph Tab["Tabella T[0..4]"]
        direction TB
        T0["T[0]"]
        T1["T[1]"]
        T2["T[2]"]
        T3["T[3]"]
        T4["T[4]"]
    end
    T0 --> N0["NULL"]
    T1 --> N1A["k=11 | ●"] --> N1B["k=6 | NULL"]
    T2 --> N2A["k=22 | NULL"]
    T3 --> N3["NULL"]
    T4 --> N4A["k=14 | ●"] --> N4B["k=9 | ●"] --> N4C["k=4 | NULL"]
  • Inserimento (insert): Si calcola , si verifica se è già nella lista T[i] (aggiornandone il valore) e altrimenti si inserisce il nuovo nodo in testa alla lista T[i] in tempo .
  • Ricerca (search) e Cancellazione (delete): Si calcola e si cerca/rimuove il nodo nella sola lista T[i].
  • Lunghezza media delle liste e Complessità:
    Con elementi distribuiti uniformemente su liste, la lunghezza media di ciascuna lista è esattamente pari al fattore di carico ! Pertanto la ricerca costa nel caso medio (che è se manteniamo ), mentre nel caso peggiore (tutte le chiavi collidono nello stesso bucket!) degenera a .

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 , ovvero ).

Quando vogliamo inserire una chiave e scopriamo che la cella principale è già occupata, ispezioniamo (probing) una sequenza deterministica di celle alternative nella tabella:

finché non troviamo una cella libera! Esistono tre schemi classici di scansione (probing):

  1. Scansione Lineare (Linear Probing):

    Se la cella è occupata, prova la cella successiva , poi , ecc. (ripartendo da dopo ).

    • 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.
  2. Scansione Quadratica (Quadratic Probing):

    Fa salti quadratici () evitando i blocchi contigui dell’addensamento primario.

  3. Doppio Hashing (Double Hashing):

    Usa una seconda funzione di hash (coprima con ) per determinare il passo del salto: così due chiavi che collidono in 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 e abbiano lo stesso hash : viene inserito in T[3] e scivola per linear probing in T[4]. Se poi cancellassimo mettendo T[3] = EMPTY, una successiva ricerca di partirebbe da T[3], vedrebbe EMPTY e si fermerebbe subito concludendo erroneamente che 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 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 con funzione di hash . Inseriamo nell’ordine le chiavi: 10, 24, 31, 17, 25 sia con Concatenamento sia con Indirizzamento Aperto a Scansione Lineare.

  1. Calcolo degli indici iniziali :

    • (Collisione in 3!)
    • (Collisione in 3!)
    • (Collisione in 3!)
  2. 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.
  3. Con Indirizzamento Aperto (Linear Probing ):

    • Inserisci 10 (): T[3] è vuota T[3] = 10.
    • Inserisci 24 (): T[3] occupata () prova : T[4] è vuota T[4] = 24.
    • Inserisci 31 (): T[3] occupata, T[4] occupata prova : T[5] è vuota T[5] = 31.
    • Inserisci 17 (): T[3], T[4], T[5] occupate prova : T[6] è vuota T[6] = 17.
    • Inserisci 25 (): 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

  1. Confrontare solo gli hash 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).
  2. Lasciare che il fattore di carico si avvicini a 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 , reinserendo gli elementi con la nuova funzione di indice.
  3. Nel Rehashing, copiare i vecchi bucket con memcpy senza ricalcolare la funzione di hash:
    Poiché la dimensione della tabella cambia da a , l’indice 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 vengono inserite chiavi distinte.

  1. Quanto vale il fattore di carico ?
  2. È possibile memorizzare queste chiavi usando l’Indirizzamento Aperto senza ridimensionare la tabella? E usando il Concatenamento? Qual è la lunghezza media delle liste nel Concatenamento?

Esercizio 2. Simulazione di Scansione Lineare vs Scansione Quadratica (Base)

Data una tabella di hash con a indirizzamento aperto inizialmente vuota e funzione base , mostra la posizione finale in cui vengono inserite le chiavi 22, 1, 13, 11, 24, 33:

  1. Con Scansione Lineare ;
  2. Con Scansione Quadratica .

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.

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).

Esercizio 5. Doppio Hashing (Avanzato)

Data una tabella con , e seconda funzione di passo , determina la sequenza di indici ispezionati da per la chiave al variare di . Perché è fondamentale che non possa mai restituire ?

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 mentre gli Alberi Binari di Ricerca (BST) bilanciati richiedono , in quali situazioni pratiche conviene comunque preferire un BST rispetto a una Tabella di Hash?


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.