FANDOM


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.

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

6 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 numericiModifica

Metodo moltiplicativo (chiavi k in virgola mobile)Modifica

8 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)Modifica

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

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

10 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)Modifica

11 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 stringheModifica

Metodo modulare per stringhe corteModifica

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

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

Metodo modulare per stringhe lungheModifica

14 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

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 collisioniModifica

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:

k_i \neq k_j \longrightarrow h \left( k_i \right) = h \left( k_j \right)

Linear chainingModifica

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: 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 addressingModifica

24 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 probingModifica

  • 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: \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 hashingModifica

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

35 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}}

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Inoltre su FANDOM

Wiki casuale