Tabelle hash

La tabella hash è un'implementazione efficiente della mappa (vedi 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 →) con tempo medio costante. Ha tre componenti:

1. 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]$;
2. un bucket array $A$ di capacità $N$: $A[i]$ contiene le entry $\langle k, v \rangle$ con $h(k) = i$;
3. 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)$.

Cosa si chiede a una buona funzione hash

1. $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);
2. $h$ deve essere veloce da calcolare.

Hash code

• Numeri: byte, short, char, int $\to$ int per cast; float $\to$ Float.floatToIntBits(k); long $\to$ (int)((k >> 32) + (int)k) (somma dei 32 bit alti e bassi: un semplice cast a int perderebbe metà dei bit); double $\to$ cast a int di Double.doubleToLongBits(k) oppure, come per long, somma delle due metà.
• Stringhe $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.

Compression function

• 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$.

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.

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

Caso pessimo. 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.

Rehashing

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

1. si crea un nuovo bucket array di capacità $N' \ge 2N$ (se serve, si cerca un primo $\ge 2N$);
2. si sceglie una nuova funzione hash;
3. si reinseriscono tutte le entry.

La condizione $N' \ge 2N$ ammortizza il costo del rehashing sugli inserimenti che lo hanno preceduto. 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$:

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.

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.