Tabelle hash

In questa pagina 8

Definizione (tabella hash). La tabella hash è un'implementazione efficiente della mappa (vedi Mappe e dizionari) con tempo medio costante. Ha tre componenti:

una funzione hash $h : U \to [0, N-1]$ ( $U$ universo delle chiavi), composta da hash code $k \mapsto \mathbb{Z}$ e compression function $\mathbb{Z} \to [0, N-1]$ ;

un bucket array $A$ di capacità $N$ : $A[i]$ contiene le entry $\langle k, v \rangle$ con $h(k) = i$ ;

un metodo di gestione delle collisioni: $\langle k_1, v_1 \rangle, \langle k_2, v_2 \rangle$ con $k_1 \ne k_2$ e $h(k_1) = h(k_2)$ .

Esempio. Con $N=11$ e $h(k)=(3k+5)\bmod11$ la chiave $12$ va nel bucket $41\bmod11=8$ : $3\cdot12+5=41$ e $41=3\cdot11+8$ , quindi il resto è $8$ .

L'idea: invece di usare la chiave come indice di un array enorme (Mappe e dizionari), la si trasforma in un indice piccolo. Visto che $|U| \gg N$ , la funzione $h$ non può essere iniettiva (principio dei cassetti: più chiavi di quante siano le celle), quindi le collisioni sono inevitabili e vanno gestite. Sono anche più frequenti di quanto si pensi, come nel paradosso del compleanno (Calcolo combinatorio per la probabilità): con soli $5$ chiavi in $N=11$ bucket, la probabilità che nessuna collida è $\frac{11\cdot10\cdot9\cdot8\cdot7}{11^5}=\frac{55440}{161051}\approx0{,}34$ , cioè c'è una collisione con probabilità $\approx 0{,}66$ .

Cosa si chiede a una buona funzione hash

$h$ deve imitare il più possibile un processo casuale (uniform hashing): per ogni $k \ne k'$ e ogni $i, j$ vale $\Pr[h(k) = i] = 1/N$ e $\Pr[h(k) = i \mid h(k') = j] = 1/N$ (le chiavi finiscono in indici statisticamente indipendenti: è la nozione di Indipendenza di eventi, e il condizionamento è quello di Probabilità condizionata; in pratica ogni chiave è assegnata a un bucket scelto a caso con probabilità uniforme $1/N$ );
$h$ deve essere veloce da calcolare.

Hash code

Numeri: byte, short, char, int $\to$ $\to$ int per cast; float $\to$ $\to$ Float.floatToIntBits(k); long $\to$ $\to$ (int)((k >> 32) + (int)k) (somma dei 32 bit alti e bassi: un semplice cast a int perderebbe metà dei bit); double $\to$ $\to$ cast a int di Double.doubleToLongBits(k) oppure, come per long, somma delle due metà.
Definizione (hash code per stringhe)
- Stringhe $S = s_0 s_1 \dots s_{k-1}$ $S = s_{0} s_{1} \dots s_{k - 1}$ :
  - somma dei caratteri $\sum s_i$ : non è buona: stop, spot, tops hanno lo stesso hash code (le permutazioni collidono);
  - polinomiale: $\sum_{i=0}^{k-1} s_i \, a^{k-1-i}$ (con la regola di Horner); per parole inglesi vanno bene $a = 31, 33, 37, 39, 41$ ( $a = 31$ nella classe String di Java);
  - cyclic shift: si somma ogni carattere dopo uno shift ciclico di $5$ posizioni della somma parziale: h <- s0; for i <- 1 to k-1: h <- (h << 5) | (h >> 27); h <- h + s_i.

Perché la somma dei caratteri è debole: l'addizione è commutativa, quindi qualsiasi permutazione delle stesse lettere dà lo stesso hash code (stop, spot, tops hanno gli stessi caratteri, il cui codice numerico dipende dalla codifica scelta: Codifiche binarie e informazione non numerica). Il polinomio usa invece potenze diverse di $a$ per le diverse posizioni, quindi lo scambio di due lettere cambia il risultato. La regola di Horner calcola il polinomio con $k-1$ moltiplicazioni e addizioni, senza elevare a potenza: h <- s0; for i <- 1 to k-1: h <- h*a + s_i. Per "abc" con $a=31$ : $h=97$ ; $97\cdot31+98=3105$ ; $3105\cdot31+99=96354$ ; lo stesso valore di $97\cdot31^2+98\cdot31+99$ . Il costo è $\Theta(k)$ per una stringa di $k$ caratteri, quindi " $h(k)$ costa $O(1)$ " vale se la chiave ha lunghezza limitata. Gli operatori di shift <<, >> sono quelli sui bit (Aritmetica binaria, Sistemi di numerazione posizionali).

Esempio. Con $a=31$ , "ab" ha hash code polinomiale $97\cdot31+98=3105$ e "ba" ha $98\cdot31+97=3135$ , mentre con la somma dei caratteri entrambe valgono $195$ .

Compression function

Definizione (compression function: divisione e MAD)

Metodo della divisione: $i \mapsto i \bmod N$ . Se $N$ non è primo le correlazioni tra gli hash code tendono a conservarsi; ad esempio con $N = 2^p$ conta solo gli ultimi $p$ bit e con $N = 10^p$ solo le ultime $p$ cifre decimali. In pratica si sceglie $N$ primo e lontano da potenze di $2$ .

MAD (multiply-add-divide): $i \mapsto [(a i + b) \bmod p] \bmod N$ con $p > N$ primo e $a, b \in [0, p-1]$ scelti a caso, $a > 0$ .

Perché $N$ potenza di $2$ è una cattiva scelta. Scrivere un numero in binario (Sistemi di numerazione posizionali): $i \bmod 2^p$ sono esattamente gli ultimi $p$ bit di $i$ , quindi tutti i codici che hanno gli stessi ultimi $p$ bit collidono. Con $N=8$ i codici $8, 16, 24$ vanno tutti nel bucket $0$ ; con $N=11$ vanno nei bucket $8, 5, 2$ . Lo stesso accade con $N=10^p$ e le ultime $p$ cifre decimali. Un $N$ primo non ha divisori in comune con la maggior parte degli schemi regolari dei dati, e li "mescola".

Esempio. Con $N=11$ l'hash code $137$ dà $137\bmod11=5$ ; con MAD ( $a=3$ , $b=5$ , $p=13$ ) l'hash code $7$ dà $[(3\cdot7+5)\bmod13]\bmod11=0$ .

Separate chaining

Definizione (load factor e separate chaining). Ogni bucket è una mappa più piccola, realizzata con una lista. Il load factor è $\lambda = n/N$ ( $n$ entry, $N$ bucket): la lunghezza media di un bucket.

Esempio. Con $n=9$ entry e $N=11$ bucket: $\lambda=9/11\approx0{,}82$ . Perché $\lambda$ è la lunghezza media: con $n$ entry distribuite sui $N$ bucket in modo uniforme, il numero di entry nel bucket $i$ ha Valore atteso $n\cdot\frac1N=\lambda$ (ogni entry cade nel bucket $i$ con probabilità $1/N$ , e il valore atteso di una somma è la somma dei valori attesi).

get(k):    se esiste (k, x) in A[h(k)] restituisci x, altrimenti null
put(k, v): se esiste (k, x) in A[h(k)] sostituisci x con v e restituisci x
           altrimenti inserisci (k, v) in coda ad A[h(k)], n <- n + 1, restituisci null
remove(k): se esiste (k, x) in A[h(k)] toglila, n <- n - 1, restituisci x; altrimenti null

Si assume che il calcolo di $h(k)$ costi $O(1)$ .

Proprietà (costo di una tabella hash: caso pessimo e medio). Per una tabella con $n$ entry get, put, remove costano $\Theta(n)$ , dominate dalla ricerca della chiave nel bucket: $O(n)$ banale; $\Omega(n)$ con tutte le entry nello stesso bucket e chiave cercata assente.

Caso medio. Sotto l'ipotesi di uniform hashing la complessità media è $O(1 + \lambda)$ , nel senso: ricerca senza successo, media su tutti i valori di $h(k)$ equiprobabili; ricerca con successo, media su tutte le chiavi presenti equiprobabili inserite una dopo l'altra senza cancellazioni. In pratica si impone $\lambda < 0{,}9$ . Il load factor è il compromesso tra spazio e velocità: $\lambda$ piccolo = tempo basso e spazio elevato; $\lambda$ grande = tempo elevato e spazio ridotto. La qualità di $h$ determina quanto ci si avvicina all'ipotesi ideale.

Esempio. Con $\lambda\approx0{,}82$ una ricerca senza successo costa in media circa $1+\lambda\approx1{,}8$ confronti, mentre nel caso pessimo, con tutte le entry in un bucket, costa $n$ .

Da dove viene $1+\lambda$ . Ricerca senza successo di $k$ : si calcola $h(k)$ (costo costante, il " $1$ ") e si confronta $k$ con tutte le entry del bucket $h(k)$ , in media $\lambda$ : totale $1+\lambda$ . Ricerca con successo: la chiave cercata è stata inserita come $j$ -esima; quando è stata inserita nel suo bucket c'erano in media $\frac{j-1}{N}$ altre entry davanti a lei (inserimento in coda), quindi ci vogliono in media $1+\frac{j-1}{N}$ confronti. Facendo la media sulle $j=1,\dots,n$ chiavi equiprobabili: $\frac1n\sum_{j=1}^{n}\Big(1+\frac{j-1}{N}\Big)=1+\frac{n-1}{2N}<1+\frac{\lambda}{2}$ (si usa la somma dei primi interi, Sommatorie). Il grafico mostra che finché $\lambda$ resta costante (per esempio sotto la soglia $0{,}75$ ) il costo medio è una costante piccola, indipendente da $n$ .

Grafico interattivo: Confronti medi per una ricerca in una tabella hash con separate chaining in funzione del load factor: senza successo 1 + λ, con successo circa 1 + λ/2; a λ = 0,75 (soglia di rehashing) sono 1,75 e 1,375

Rehashing

Definizione (rehashing). Quando $\lambda$ supera una soglia (ad esempio $\lambda > 0{,}75$ ):

si crea un nuovo bucket array di capacità $N' \ge 2N$ (se serve, si cerca un primo $\ge 2N$ );

si sceglie una nuova funzione hash;

si reinseriscono tutte le entry.

Esempio. Con $N=11$ e soglia $0{,}75$ il nono inserimento ( $9/11>0{,}75$ ) causa il rehashing verso $N'\ge22$ , per esempio il primo $23$ .

La condizione $N' \ge 2N$ ammortizza il costo del rehashing sugli inserimenti che lo hanno preceduto: è lo stesso argomento dell'array estendibile che raddoppia (Liste, pile e code). Dopo il rehashing con $N'=23$ e $n=9$ si ha $\lambda=9/23\approx0{,}39$ , e si può arrivare a $n=17$ entry senza nuovo rehashing ( $17/23\approx0{,}74$ ), mentre con $n=18$ si supera la soglia ( $18/23\approx0{,}78$ ): servono $9$ inserimenti prima del prossimo rehashing, quindi il costo $\Theta(n)$ del trasferimento è diviso su molti inserimenti. Il trasferimento di $n$ entry costa $\Theta(n)$ perché le chiavi sono già distinte e non occorre cercarle prima di inserirle.

Esempio svolto

$N = 11$ , $h(k) = (3k + 5) \bmod 11$ , separate chaining, chiavi inserite nell'ordine $12, 44, 13, 88, 23, 94, 11, 39, 20$ :

$k$	12	44	13	88	23	94	11	39	20
$3k + 5$	41	137	44	269	74	287	38	122	65
$h(k)$	8	5	0	5	8	1	5	1	10

Contenuto finale (bucket vuoti omessi): $A[0] = (13)$ ; $A[1] = (94, 39)$ ; $A[5] = (44, 88, 11)$ ; $A[8] = (12, 23)$ ; $A[10] = (20)$ . Le collisioni sono nei bucket 1, 5 e 8. Load factor $\lambda = 9/11 \approx 0{,}82$ . La ricerca di $11$ confronta $44$ , $88$ , $11$ : tre confronti. Passaggi per $k=94$ : $3\cdot94+5=287$ e $287=26\cdot11+1$ , quindi il resto è $1$ e $94$ va in $A[1]$ ; per $k=39$ : $3\cdot39+5=122=11\cdot11+1$ , anche in $A[1]$ , dietro a $94$ (inserimento in coda). Lunghezze dei bucket: $1,2,3,2,1$ (somma $9$ , uguale a $n$ ); gli altri $6$ bucket sono vuoti.

Pro e contro

Pro: implementazione facile; ottime prestazioni al caso medio; non richiede un universo ordinato. Contro: complessità elevata al caso pessimo; esito dipendente dalla bontà della funzione hash; spreco di spazio per mantenere $\lambda$ basso.

Errori comuni

Dire che get è $O(1)$ al caso pessimo: lo è in media, con $\lambda$ costante.
Scegliere $N$ potenza di $2$ o di $10$ con la divisione.
Dimenticare che dopo il rehashing la funzione hash cambia: ogni entry va reinserita, non copiata nella stessa posizione.
Usare la somma dei caratteri come hash code di stringhe: gli anagrammi collidono.

Versione ripasso

Definizione: implementazione della mappa (vedi Mappe e dizionari) con tempo medio costante. Tre componenti: funzione hash $h: U\to[0,N-1]$ (hash code $k\mapsto\mathbb{Z}$ seguito da una compression function); bucket array $A$ di capacità $N$ , con $A[i]$ che contiene le entry con $h(k)=i$ ; gestione delle collisioni ( $k_1\ne k_2$ con $h(k_1)=h(k_2)$ ).
Esempio: con $N=11$ e $h(k)=(3k+5)\bmod11$ la chiave $12$ dà $41=3\cdot11+8$ , quindi bucket $8$ .
Collisioni inevitabili: $|U|\gg N$ , quindi $h$ non è iniettiva (principio dei cassetti). Con $5$ chiavi in $11$ bucket, la probabilità che nessuna collida è $\frac{11\cdot10\cdot9\cdot8\cdot7}{11^5}\approx0{,}34$ (vedi Calcolo combinatorio per la probabilità).
Buona funzione hash: (1) uniform hashing, cioè $\Pr[h(k)=i]=1/N$ e indipendenza tra chiavi diverse (vedi Indipendenza di eventi); (2) velocità di calcolo.
Hash code per i numeri: int così com'è; long sommando le due metà a $32$ bit (un cast diretto perderebbe metà dei bit); float e double tramite la rappresentazione in bit.
Hash code per stringhe:
- la somma dei caratteri è cattiva: stop, spot, tops collidono;
- polinomiale $\sum_i s_i\,a^{k-1-i}$ con $a=31$ , calcolato con Horner (h <- h*a + s_i): per "abc" si ottiene $96354$ ;
- cyclic shift di $5$ bit sulla somma parziale, poi somma del carattere successivo.
- Esempio: "ab" dà $97\cdot31+98=3105$ , "ba" dà $3135$ ; con la somma entrambe valgono $195$ .
Compression, divisione: $i\bmod N$ con $N$ primo e lontano da potenze di $2$ : con $N=8$ i codici $8, 16, 24$ finiscono tutti nel bucket $0$ . Esempio: con $N=11$ , $137\bmod11=5$ .
Compression, MAD: $[(ai+b)\bmod p]\bmod N$ , con $p>N$ primo, $a,b\in[0,p-1]$ scelti a caso e $a>0$ . Esempio: $a=3$ , $b=5$ , $p=13$ , $N=11$ con hash code $7$ dà bucket $0$ .
Separate chaining: ogni bucket è una lista. Load factor $\lambda=n/N$ , cioè la lunghezza media di un bucket; con $n=9$ e $N=11$ è $\lambda\approx0{,}82$ . get, put e remove scorrono la lista del bucket $A[h(k)]$ ; put aggiunge in coda.
Costo: caso pessimo $\Theta(n)$ $Θ (n)$ , con tutte le entry nello stesso bucket. Caso medio sotto uniform hashing $O(1+\lambda)$ $O (1 + λ)$ ; in pratica si tiene $\lambda<0{,}9$ $λ < 0, 9$ .
- Ricerca senza successo: in media $1+\lambda$ confronti.
- Ricerca con successo: in media $1+\frac{n-1}{2N}<1+\frac{\lambda}{2}$ , mediando sulle $n$ chiavi inserite in coda.
Rehashing: se $\lambda$ supera una soglia (ad esempio $0{,}75$ ) si crea un array di capacità $N'\ge 2N$ (dopo $N=11$ , ad esempio $23$ ), si sceglie una nuova $h$ e si reinseriscono tutte le entry: $\Theta(n)$ , ammortizzato sugli inserimenti precedenti.
Esempio svolto: $N=11$ , $h=(3k+5)\bmod11$ , chiavi $12,44,13,88,23,94,11,39,20$ danno bucket $8,5,0,5,8,1,5,1,10$ . Contenuto: $A[0]=(13)$ , $A[1]=(94,39)$ , $A[5]=(44,88,11)$ , $A[8]=(12,23)$ , $A[10]=(20)$ ; la ricerca di $11$ fa $3$ confronti.
Pro/contro: semplice e veloce in media, non richiede un universo ordinato; caso pessimo lineare, dipende dalla qualità di $h$ , spreco di spazio per tenere $\lambda$ basso.
Errori tipici: dire che get è $O(1)$ nel caso pessimo; scegliere $N$ potenza di $2$ o di $10$ ; copiare le entry invece di reinserirle dopo il rehashing; usare la somma dei caratteri come hash di una stringa.