Hashing - Dipartimento di Ingegneria informatica ...damore/asd/trasparenze/2002-03/hashing.pdf ·...

Hashing

giu 03 ASD - Hashing 2

argomentiHashing

Tabelle hashFunzioni hash e metodi per generarleInserimento e risoluzione delle collisioni Eliminazione

Funzioni hash per fileHashing estendibileHashing lineare


Richiamo sul concetto di dizionario

Insieme di coppie del tipo <elemento, chiave>Le chiavi appartengono a un insieme totalmente ordinatoOperazioni:

insert(el, key)delete(key) search(key)


Tabelle hash Adatte per realizzare dizionariGeneralizzazione del concetto di arrayImportanti nell’accesso a dati su memoria secondaria

Gli accessi avvengono a memoria secondariaCosto degli accessi predominante

Indirizzamento diretto: si associa ad ogni valore della chiave un indice di un array –ricerca in tempo O(1)Problemi?


Indirizzamento diretto

10

N-1

Ogni possibile chiave corrisponde ael. diversodell’array

Può portare a spreco di memoria

Es.: 10000 studenti ematr.= No. decimale a 5 cifre

No. chiavi


Obiettivi

10

N-1

N ~ No. Chiavi effettivamente usate

Tempo di ricerca O(1)

D.: possibile?

Nota: No. Chiavi possibili può essere >> N

No. chiavi


Tabella hash

Dato l’insieme base di un dizionario:<T, h>T è una tabella con N celleh: K {0,...,N-1}

K insieme delle possibili chiavi{0,...,N-1} insieme delle posizioni nella tabella, dette pseudochiavi


Funzioni hash perfette e collisioni

Funzione hash perfetta: k1!=k2 h(k1) != h(k2) Richiede N >= |K|Raramente ragionevole in pratica

In generale N < |K| (spesso N << |K|)Conseguenza: k1!=k2 ma h(k1) == h(k2) è possibile

Collisione (più frequenti del previsto - cfr. paradosso del compleanno)

Es.: proporre una funzione hash perfetta nel caso in cui le chiavi siano stringhe di lunghezza 3 sull’alfabeto {a, b, c}


Requisiti di una funzione hash

Uniformità semplice: Pr[h(k)=j] ~ 1/|K|La probabilità è calcolata rispetto alla distribuzione delle chiaviIntuitivamente, si desidera che gli elementi si distribuiscano nell’array in modo uniformeDifficile costruire funzioni che soddisfino la proprietàD.: perché?


Requisiti di una funzionehash/2

Esempio: sia |T|=5 e h(k)=k mod 5

{1, 7, 10, 14} {1, 6, 11, 16}

• Non è nota la distribuzione delle chiavi

• Può aversi agglomerazione degli elementi

In pratica: si cerca di avere indipendenza dai dati

01234

01234


Paradosso del compleannoscelti 23 individui a caso, la probabilità che due di essi abbiano lo stesso compleanno è > ½ (circa 50.7%)

dimostrare!in termini di hashing, anche ipotizzando di avere le pseudochiavi a distribuzione uniforme, dopo 22 inserimenti in una tabella di 365 celle, ogni ulteriore inserimento avrà probabilità superiore a ½ di generare una collisione


Interpretazione delle chiaviTra gli elementi di K è definito un ordinamento totale ma:Le chiavi non sono necessariamente numeri naturali

Es.: stringheSoluzione: associare a ciascuna chiave un interoModalità dipendono da insieme delle chiavi e applicazione


Esempio: stringhePossibile metodo: associare a ciascun carattere il valore ASCII e alla stringa il numero intero ottenuto in una base sceltaEsempio: base 2, posizioni meno significative a destra

Stringa = “pt” pseudochiave = 112*21+116*20=340

Ascii(‘p’)=112 Ascii(‘t’)=116


Derivazione di funzioni hashMolti metodi

DivisioneRipiegamentoMid-squareEstrazione...........

Obiettivo: distribuzione possibilmente uniformeDifferenze:

ComplessitàFenomeni di agglomerazione


Divisioneh(k)=k mod |T| - Bassa complessitàAttenzione ai fenomeni di agglomerazione

No potenze di 2: se m=2p allora tutte le chiavi con i p bit meno significativi uguali collidonoNo potenze di 10 se le chiavi sono numeri decimali (motivo simile)In generale, la funzione dovrebbe dipendere da tutte le cifre della chiave (comunque rappresentata)Scelta buona in pratica: numero primo non troppo vicino a una potenza di 2 (esempio: h(k)=k mod 701 per |K|=2048 valori possibili)


Ripiegamento

Chiave k suddivisa in parti k1,k2,....,kn

h(k)=f(k1,k2,....,kn)Esempio: la chiave è un No. di carta di credito. Possibile funzione hash:

1. 4772 6453 7348 {477, 264, 537, 348}2. f(477,264,537,348) = (477+264+537+348)mod 701 = 224


Estrazione

Si usa soltanto una parte della chiave per calcolare l’indirizzoEsempio: 6 cifre centrali del numero di carta di credito

4772 6453 7348 264537Il numero ottenuto può essere ulteriormente manipolatoL’indirizzo può dipendere da una porzione della chiave


Risoluzione delle collisioni

I metodi si distinguono per la collocazione degli elementi che danno luogo alla collisioneConcatenazione: alla i-esima posizione della tabella è associata la lista degli elementi tali che h(k)=iIndirizzamento aperto: tutti gli elementi sono contenuti nella tabella


Concatenazioneh(k1)= h(k4)=0h(k5)= h(k7)=h(k2)=4

k1 k401234

k2k2k5 k7

Es.: h(k)=k mod 5k1=0, k4=10k5=9, k7=14, k2=4


Concatenazione/2

insert(el, k): inserimento in testa alla lista associata alla posizione h(k) – costo O(1)search(k): ricerca lineare nella lista associata alla posizione h(k) – costo O(lungh. lista associata a h(k))delete(k): ricerca nella lista associata a h(k), quindi cancellazione – costo O(lungh. lista associata a h(k))


Indirizzamento apertoTutti gli elementi sono memorizzati nella tabellaLe collisioni vanno risolte all’interno della tabella

Se la posizione calcolata è già occupata occorre cercarne una liberaI diversi metodi ad indirizzamento diretto si distinguono per il metodo di scansione adottato La funzione hash può dipendere anche dal numero di tentativi effettuatiIndirizzo=h(k, i) per l’i-esimo tentativo


Inserimento insert (el, k) {

/* T denota la tabella */

i=0;

while (h(k, i) <occupata> && (i<|T|))

i++;

if (i < |T|)

<inserisci el in pos. h(k, i)>

else <overflow>

}


Ricerca search (k) {


i=0;

while ((k!=key(T[h(k, i)])) && (i<|T|))

i++;

if (i < |T|)

<restituisci T[h(k, i)]>

else <elemento assente>

}


Cancellazione delete (k) {


search(k);

if (<trovato>)

<elimina elemento con chiave k>

}


ScansioneLa funzione h(k, i) deve essere tale che tutte le posizioni della tabella siano esaminateSono possibili diverse forme per la funzione h(k,i)

Scansione lineareScansione quadraticaHashing doppio

Si differenziano per complessità e comportamento rispetto a fenomeni di agglomerazione


Scansione lineareh(k, i) = (h’(k)+i) mod |T|, dove h’(k) è una funzione di hashingSi scandiscono tutte le posizioni nella sequenza T[h’(k)], T[h’(k)]+1, .... T[|T|], 0, 1, ...., T[h’(k)]-1Possibilità di agglomerazione primaria: gli elementi si agglomerano per lunghi tratti

agglomerazione primaria = due sequenze di scansione che hanno una collisione rimangono collidenti


Agglomerazione primariah(k, i) = (h’(k)+i) mod 101, h’(k)=k mod 101

012{2, 103, 104, 105,....}

Caso estremo, ma il problemaesiste

100


Scansione quadraticah(k, i) = (h’(k)+c1i+c2i2) mod |T|, dove h’(k) è una funzione di hashing, c1 e c2 sono costanti

es. indirizzi scanditi: h’(k), h’(k)+1, h’(k)+2,h’(k)+3…

Es.: h(k, i) = h’(k)+i2, h(k, i+1) = h’(k)+(i+1)2, i=1,..., (|T|-1)/2Possibilità di agglomerazione secondaria: se h’(k1)= h’(k2) h’(k1,i)= h’(k2,i) Descrivere h(k, i) quando h’(k)=k mod |5|


Hashing doppio

h(k, i) = (h1(k)+ih2(k)) mod |T|, dove h1(k) e h2(k) sono funzioni di hashing Anche la modalità di scansione dipende dalla chiaveL’hashing doppio riduce i fenomeni di agglomerazione secondaria

esente da quelli di agglomerazione primaria


Hashing estendibile

E’ usato nella gestione di file, la cui dimensione può variare.

Es.: file ad accesso diretto

Il file è organizzato in bucket, ciascuno dei quali ha una dimensione fissaGli indirizzi sono associati ai bucketLa funzione hash restituisce in questo caso un puntatore al bucket


Hashing estendibile/2

00011011

2 2

1

Lungh. locale 2

Lungh. globaleBucket 00

Bucket 01

Bucket 1

File

h(k)=11001

h(k) restituisce una stringa binaria bI bit più significativi di b sono usati per determinare l’indirizzo delbucket Indice


Esempio

22

1

2

Indice

Bucket 00

Bucket 01

Bucket 1

File

10010

011000110001100

0000100101

1

1

1

Indice

Bucket 0

Bucket 1

File

10010

01100011000000101100

h(k)=00101

0000111011

Dim. Bucket = 4


H. estendibile - Inserimento extHashInsert (el, k) {

/* L=lunghezza globale */

str=h(k); /* LS= lunghezza str */

p=indice[pattern[LS-1...LS-L]];

if (<Bucket puntato da p non pieno)

<inserisci el>

else {

<suddividi bucket> /* l=lunghezza locale bucket*/

l++;

<inserisci el>

}

if (l > L)

<Raddoppia indice>

L++;

}

Hashing - Dipartimento di Ingegneria informatica ...damore/asd/trasparenze/2002-03/hashing.pdf ·...

Documents

Transcript of Hashing - Dipartimento di Ingegneria informatica ...damore/asd/trasparenze/2002-03/hashing.pdf ·...