Algoritmi/Le tabelle di hash

tion

La tabella di hash è un tipo di dato astratto che utilizza uno spazio di memoria congruente con il numero di dati, in cui si garantiscono operazioni prossime al costo unitario, ovvero con un tempo medio di accesso in ricerche/cancellazioni/inserzioni di tipo unitario.

• tabelle ad accesso diretto: la chiave è l'indice del vettore → complessità lineare, ma: non sono utilizzabili quando il numero delle chiavi è troppo grande e non si può allocare in memoria;
• strutture ad albero: complessità logaritmica, ma si spera che l'albero non degeneri;
• tabelle di hash: c'è una funzione intermedia detta funzione di hash che manipola la chiave e la trasforma in un indice.

Il numero $\left|K\right|$ delle chiavi contenute in una tabella di hash di dimensione $M$ è molto minore della cardinalità dell'universo delle chiavi: $\left|K\right|\ll \left|U\right|$.

Se ogni chiave nell'universo ha un indirizzo compreso tra 0 e $m-1$, la funzione di hash $h:U\longrightarrow \left\{0,\cdots ,m-1\right\}$ associa alla chiave $k$ l'indice $h\left(k\right)$ della tabella $T$.

La tabella di hash deve garantire una buona distribuzione: se le chiavi sono equiprobabili allora i valori $h\left(k\right)$ devono essere equiprobabili, cioè la distribuzione deve essere semplice uniforme e non si deve polarizzare su determinate chiavi.

Tabelle di hash per valori numerici

Metodo moltiplicativo (chiavi $k$ in virgola mobile)

Per una chiave $k$ compresa nell'intervallo $\left[s,t\right]$:

$h\left(k\right)=\sup {\left(M{k-s \over t-s}\right)}$

1. normalizzazione: si divide $k-s$ (offset tra la chiave $k$ e l'estremo inferiore dell'intervallo) e $t-s$ (ampiezza dell'intervallo) → si ottiene un valore compreso tra 0 e 1;
2. si moltiplica per il numero $M$ per trovare un valore compreso nell'intervallo tra 0 e $m-1$;
3. si prende l'intero superiore, poiché $h\left(k\right)$ è un numero intero.

Metodo modulare (chiavi $k$ intere)

Si applica la funzione mod() a una chiave $k$ intera:

$h\left(k\right)=k\,{\text{mod}}\,M$

Per limitare le collisioni, si prende per $M$ un numero primo. Esempi antitetici di tabelle di hash sono la funzione ${\text{mod}}\,2^{n}$: concentra tutti i numeri in valori 0 e 1 → tantissime collisioni perché si limita ai primi n bit più significativi.

Metodo moltiplicativo-modulare (chiavi $k$ intere)

Data una costante $A$ (per esempio: $A={\tfrac {{\sqrt {5}}-1}{2}}$):

$h\left(k\right)=\inf {\left(k\cdot A\right)}\,{\text{mod}}\,M$

Tabelle di hash per stringhe

Metodo modulare per stringhe corte

Pensando ogni carattere come numero, la stringa è la rappresentazione compatta di un polinomio. Valutando il polinomio in un punto (di solito ${\text{card}}\left(U\right)$), si ottiene il valore numerico intero $k$ → si applica il metodo modulare per chiavi intere.

Le operazioni per valutare il polinomio non sono però efficienti → questo metodo si può usare per stringhe corte.

Metodo modulare per stringhe lunghe

La valutazione del polinomio è effettuata tramite il metodo di Horner, che considera ricorsivamente polinomi di grado 1:

$p_{n}\left(x\right)=\left\{\left[\left(a_{n}x+a_{n-1}\right)x+a_{n-2}\right]x+\cdots +a_{1}\right\}x+a_{0}$

La base x del polinomio può essere un numero primo o un numero pseudocasuale a = (a * b) mod (M - 1) (hash universale). Per calcolare la chiave k, per ogni polinomio di primo grado valutato si deve fare a ogni passo la funzione mod M.

Gestione delle collisioni

È inevitabile il fenomeno della collisione, ovvero quando chiavi diverse corrispondono allo stesso valore di indice; si può ridurre con buone funzioni di hash.

Si ha una collisione se:

$k_{i}\neq k_{j}\longrightarrow h\left(k_{i}\right)=h\left(k_{j}\right)$

Linear chaining

Ogni elemento della tabella contiene un puntatore alla testa di una lista concatenata che contiene tutte le chiavi collidenti.

Operazioni sulla lista

• inserzione: non si hanno esigenze di ordinamento → l'inserzione meno costosa è quella in testa: $T\left(n\right)=O\left(1\right)$;
• ricerca: se $N=\left|K\right|$ = numero delle chiavi, $M$ = dimensione della tabella di hash:
  • caso peggiore: tutte le chiavi si concentrano in una sola lista → operazione lineare nella dimensione della lista, ma: caso poco frequente: $\Theta \left(N\right)$;
  • caso medio: le chiavi sono tutte uniformemente distribuite → la dimensione media delle liste è uguale al fattore di carico $\alpha ={\tfrac {N}{M}}$: $T\left(n\right)=O\left(1+\alpha \right)$ (un buon valore di $\alpha$ è 0,1);
• cancellazione:
  • se la lista è doppio-linkata: $T\left(n\right)=O\left(1\right)$;
  • altrimenti, il costo è legato alla ricerca dell'elemento.

Open addressing

Ogni cella può contenere al massimo un solo elemento ($\alpha \leq 1$), e in caso di collisione il valore da inserire va inserito in un'altra cella, verificando che sia vuota (probing = ricerca di una cella vuota). Le $M-1$ celle rimanenti vengono sondate nell'ordine di una delle $\left(M-1\right)!$ permutazioni stabilita dalla funzione di hash, in funzione anche del tentativo $t$: $h\left(k,t\right):U\times \left\{0,\cdots ,M-1\right\}\longrightarrow \left\{0,\cdots ,M-1\right\}$.

Linear probing

• inserzione: si sonda la cella di indice successivo e si inserisce nella prima casella vuota;
• ricerca: si passa di volta in volta alla cella di indice successivo, ricordando che al termine della tabella si deve passare alla prima cella (mod M a ogni incremento). È una gestione implicita delle liste all'interno di un vettore senza ricorrere al concetto di puntatore;
• cancellazione: bisogna distinguere le celle vuote dalle celle svuotate dalla cancellazione, perché altrimenti la ricerca successiva si fermerebbe alla cella svuotata.

Sperimentalmente, tentativi in media di probing per la ricerca:

• search miss: ${\frac {1}{2}}\left(1+{\frac {1}{1-\alpha }}\right)$
• search hit: ${\frac {1}{2}}\left(1+{\frac {1}{{\left(1-\alpha \right)}^{2}}}\right)$

Se $\alpha \sim 0^{+}$ → search miss ~1 → efficiente.

Double hashing

L'indice della cella successiva in caso di probing con insuccesso viene calcolato da un'altra funzione di hash h₂.

Sperimentalmente, tentativi in media di probing per la ricerca:

• search miss: ${1 \over 1-\alpha }$
• search hit: ${1 \over \alpha }\log {1 \over 1-\alpha }$