Algoritmi e programmazione/Le tabelle di hash

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 11. Le tabelle di hash.

[[{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/Le tabelle di hash}}/Tipologie di problemi{{#ifcategory:Traduzioni\|/Le tabelle di hash\|\|/Le tabelle di hash}}\|10. Tipologie di problemi]]	[[{{#ifcategory:Traduzioni\|/Le tabelle di hash\|Algoritmi e programmazione\|/Le tabelle di hash}}\|{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/Le tabelle di hash}}]]	[[{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/Le tabelle di hash}}/L'ADT grafo non orientato{{#ifcategory:Traduzioni\|/Le tabelle di hash\|\|/Le tabelle di hash}}\|12. L'ADT grafo non orientato]]

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

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

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

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

Tabelle di hash per valori numerici[modifica | modifica sorgente]

Metodo moltiplicativo (chiavi <math>k</math> in virgola mobile)[modifica | modifica sorgente]

8 Per una chiave <math>k</math> compresa nell'intervallo <math>\left[ s , t \right]</math>:

<math>h \left( k \right) = \sup{\left( M {k - s \over t-s} \right)}</math>

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

Metodo modulare (chiavi <math>k</math> intere)[modifica | modifica sorgente]

9 Si applica la funzione mod() a una chiave <math>k</math> intera:

<math>h \left( k \right) = k \, \text{mod} \, M</math>

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

Metodo moltiplicativo-modulare (chiavi <math>k</math> intere)[modifica | modifica sorgente]

11 Data una costante <math>A</math> (per esempio: <math>A= \tfrac{\sqrt{5} - 1}{2}</math>):

<math>h \left( k \right) = \inf {\left( k \cdot A \right)} \, \text{mod} \, M</math>

Tabelle di hash per stringhe[modifica | modifica sorgente]

Metodo modulare per stringhe corte[modifica | modifica sorgente]

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

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

Metodo modulare per stringhe lunghe[modifica | modifica sorgente]

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

<math>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</math>

15 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[modifica | modifica sorgente]

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

16 Si ha una collisione se:

<math>k_i \neq k_j \longrightarrow h \left( k_i \right) = h \left( k_j \right)</math>

Linear chaining[modifica | modifica sorgente]

17-22-23 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: <math>T \left( n \right) = O \left( 1 \right)</math>;
ricerca: se <math>N = \left| K \right|</math> = numero delle chiavi, <math>M</math> = 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: <math>\Theta \left( N \right)</math>;
- caso medio: le chiavi sono tutte uniformemente distribuite → la dimensione media delle liste è uguale al fattore di carico <math>\alpha = \tfrac{N}{M}</math>: <math>T \left( n \right) = O \left( 1+ \alpha \right)</math> (un buon valore di <math>\alpha</math> è 0,1);
cancellazione:
- se la lista è doppio-linkata: <math>T \left( n \right) = O \left( 1 \right)</math>;
- altrimenti, il costo è legato alla ricerca dell'elemento.

Open addressing[modifica | modifica sorgente]

24 Ogni cella può contenere al massimo un solo elemento (<math>\alpha \leq 1</math>), 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 <math>M-1</math> celle rimanenti vengono sondate nell'ordine di una delle <math>\left( M - 1 \right) !</math> permutazioni stabilita dalla funzione di hash, in funzione anche del tentativo <math>t</math>: <math>h \left( k,t \right) : U \times \left \{ 0, \cdots , M -1 \right \} \longrightarrow \left \{ 0, \cdots ,M-1 \right \}</math>.

Linear probing[modifica | modifica sorgente]

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

29 Sperimentalmente, tentativi in media di probing per la ricerca:

search miss: <math>\frac{1}{2} \left( 1 + \frac{1}{1 - \alpha} \right)</math>
search hit: <math>\frac{1}{2} \left( 1+ \frac{1}{{\left( 1- \alpha \right)}^2} \right)</math>

Se <math>\alpha \sim 0^+</math> → search miss ~1 → efficiente.

Double hashing[modifica | modifica sorgente]

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

35 Sperimentalmente, tentativi in media di probing per la ricerca:

search miss: <math>{1 \over 1- \alpha}</math>
search hit: <math>{1 \over \alpha} \logTemplate:1 \over 1 - \alpha</math>