Esercizio 19tabelle hash con separate chaining

---

Richiami

Con il separate chaining (vedi Tabelle hashTabella hash per implementare una mappa: funzione hash = hash code + compression function, bucket array, separate chaining; hash code per numeri e stringhe (polynomial, cyclic shift), division e MAD; load factor, complessità al caso pessimo Theta(n) e medio O(1+lambda), rehashing; esempio svolto con inserimenti e collisioni.Tabelle hash →) l'entry $(k, v)$ va nel bucket $A[h(k)]$, in coda alla lista. Si assume che in ogni lista le chiavi stiano nell'ordine di inserimento (se l'implementazione inserisce in testa, ogni lista risulta invertita: lo si dichiara).

Parte A

Si calcola $h(k)$ per ciascuna chiave:

(ad esempio $41 = 3 \cdot 11 + 8$, $269 = 24 \cdot 11 + 5$.) Tabella finale:

Collisioni nei bucket $1$, $5$ e $8$. Con $n = 9$ ed $N = 11$ il load factor è $\lambda = 9/11 \approx 0{,}82$.

Parte B

Indici: $10 \bmod 7 = 3$; $22 \bmod 7 = 1$; $31 \bmod 7 = 3$; $4 \bmod 7 = 4$; $15 \bmod 7 = 1$; $28 \bmod 7 = 0$; $17 \bmod 7 = 3$.

(a) Contenuto finale (ordine di inserimento in ogni lista):

Se invece ogni nuovo elemento fosse inserito in testa, le liste risulterebbero $15 \to 22$ nel bucket $1$ e $17 \to 31 \to 10$ nel bucket $3$.

(b) Ricerca di $17$: $h(17) = 3$; si scandisce la lista del bucket $3$ e si confrontano nell'ordine le chiavi $10$, $31$, $17$ (la terza trova la chiave). Con l'inserimento in testa si confronterebbe solo $17$. Le chiavi negli altri bucket non vengono toccate.

(c) Complessità. Detto $\lambda = n/N$ il load factor:

• caso medio: $\Theta(1 + \lambda)$ sotto l'ipotesi di hashing uniforme: costo costante per calcolare $h(k)$ e la scansione di un bucket di lunghezza media $\lambda$. Se la tabella cresce in modo da mantenere $\lambda = O(1)$ si ha $\Theta(1)$;
• caso pessimo: $\Theta(n)$: tutte le $n$ chiavi possono finire nello stesso bucket e la chiave cercata può essere in fondo alla lista o assente.

(d) Load factor: $\lambda = n/N = 7/7 = 1$.

(Entrambe le tabelle sono state verificate con un programma.)

Errori comuni

• Applicare $h$ senza ridurre modulo $N$ (si ottengono indici fuori dalla tabella) o sbagliare il resto (controllare con $3k + 5 - 11q$).
• Confrontare nella ricerca anche chiavi di altri bucket: si guarda solo il bucket $h(k)$.
• Dire che la ricerca è $O(1)$ al caso pessimo: lo è in media.
• Definire il load factor come $N/n$ (rovesciato) o come lunghezza massima del bucket: è il rapporto entry/bucket, cioè la lunghezza media.