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 →, Mappe e dizionariADT mappa (chiavi distinte) con get, put, remove, keySet/values/entrySet; famiglia mappa/mappa ordinata/dizionario (multimappa); applicazioni; implementazioni semplici ma poco efficienti (lista, array indicizzato dalle chiavi); dizionario realizzato con una mappa di liste.Mappe e dizionari →) l'entry $(k, v)$ va nel bucket $A[h(k)]$, in coda alla lista. Il resto della divisione $a \bmod N$ è il resto della divisione intera (come in $39\bmod7=4$: Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →; per i numeri interi Aritmetica binariaSomma e sottrazione in binario, overflow per senza segno (riporto) e per complemento a 2 (segni), flag del processore, moltiplicazione per somme e scorrimenti, algoritmo di Booth, divisione, shift logici e aritmetici.Aritmetica binaria →): si trova $q=\lfloor a/N\rfloor$ e si calcola $a-qN$. 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$. Lunghezze dei bucket $0,\dots,10$: $1,2,0,0,0,3,0,0,2,0,1$, somma $9=n$. Confronti per ritrovare ciascuna chiave (posizione nella lista): $13{:}1$, $94{:}1$, $39{:}2$, $44{:}1$, $88{:}2$, $11{:}3$, $12{:}1$, $23{:}2$, $20{:}1$, in media $14/9\approx1{,}56$ confronti per una ricerca con successo.

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$. Passaggi: $10=7\cdot1+3$, $22=7\cdot3+1$, $31=7\cdot4+3$, $4=7\cdot0+4$, $15=7\cdot2+1$, $28=7\cdot4+0$, $17=7\cdot2+3$. Con $7$ chiavi in $7$ bucket è quasi certo che ci siano collisioni: la probabilità che tutte finiscano in bucket diversi (hashing uniforme) è $\frac{7!}{7^7}=\frac{5040}{823543}\approx0{,}006$ (Calcolo combinatorio per la probabilitàNegli spazi uniformi bisogna contare: principio di moltiplicazione, disposizioni con ripetizione n^k, disposizioni semplici n!/(n−k)!, permutazioni n!, combinazioni (n su k); estrazioni con e senza reinserimento e distribuzione ipergeometrica.Calcolo combinatorio per la probabilità →).

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

Il valore medio $\lambda$ per la lunghezza di un bucket è un Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso →: ogni chiave cade in un dato bucket con probabilità $1/N$, quindi le $n$ chiavi producono in media $n/N$ chiavi per bucket. Qui le lunghezze effettive sono $1,2,0,3,1,0,0$ (somma $7$), con media $1$.

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