Hashing

Hashing 2

argomenti Hashing

Tabelle hash Funzioni hash e metodi per generarle Inserimento e risoluzione delle

collisioni Eliminazione

Funzioni hash per file Hashing estendibile Hashing lineare

Hashing 3

Richiamo sul concetto di dizionario Insieme di coppie del tipo

<elemento, chiave> Le chiavi appartengono a un

insieme totalmente ordinato Operazioni:

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

Hashing 4

Tabelle hash Adatte per realizzare dizionari Generalizzazione del concetto di array Importanti nell’accesso a dati su

memoria secondaria Gli accessi avvengono a memoria secondaria Costo degli accessi predominante

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

Problemi?

Hashing 5

Indirizzamento diretto

Ogni possibile chiave corrisponde a el. diverso dell’array

Può portare a spreco di memoria

Es.: 10000 studenti e matr.= No. decimale a 5 cifre

10

N-1

No. chiavi

Hashing 6

Obiettivi

N ~ No. Chiavi effettivamente usate

Tempo di ricerca O(1)

D.: possibile? Nota: No. Chiavi possibili può essere >> N

10

N-1

No. chiavi

Hashing 7

Tabella hash

Dato l’insieme base di un dizionario:

<T, h> T è una tabella con N celle h: K {0,...,N-1}

K insieme delle possibili chiavi {0,...,N-1} insieme delle posizioni

nella tabella, dette pseudochiavi

Hashing 8

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

Hashing 9

Requisiti di una funzione hash

Uniformità semplice: Pr[h(k)=j] ~ 1/|K| La probabilità è calcolata rispetto alla

distribuzione delle chiavi Intuitivamente, si desidera che gli

elementi si distribuiscano nell’array in modo uniforme

Difficile costruire funzioni che soddisfino la proprietà

D.: perché?

Hashing 10

Requisiti di una funzione hash/2

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

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

• Non è nota la distribuzione delle chiavi

• Può aversi agglomerazione degli elementi

In pratica: si cerca di avere indipendenza dai dati

01234

01234

Hashing 11

Paradosso del compleanno scelti 23 individui a caso, la probabilità

che due di essi abbiano lo stesso compleanno è > ½ (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

Hashing 12

Interpretazione delle chiavi

Tra gli elementi di K è definito un ordinamento totale ma:

Le chiavi non sono necessariamente numeri naturali Es.: stringhe Soluzione: associare a ciascuna chiave

un intero Modalità dipendono da insieme delle

chiavi e applicazione

Hashing 13

Esempio: stringhe Possibile metodo: associare a ciascun

carattere il valore ASCII e alla stringa il numero intero ottenuto in una base scelta

Esempio: base 2, posizioni meno significative a destra

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

Ascii(‘p’)=112

Ascii(‘t’)=116

Hashing 14

Derivazione di funzioni hash

Molti metodi Divisione Ripiegamento Mid-square Estrazione ...........

Obiettivo: distribuzione possibilmente uniforme

Differenze: Complessità Fenomeni di agglomerazione

Hashing 15

Divisione h(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 collidono

No 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)

Hashing 16

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

Hashing 17

Estrazione Si usa soltanto una parte della chiave

per calcolare l’indirizzo Esempio: 6 cifre centrali del numero

di carta di credito

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

Hashing 18

Risoluzione delle collisioni I metodi si distinguono per la

collocazione degli elementi che danno luogo alla collisione

Concatenazione: alla i-esima posizione della tabella è associata la lista degli elementi tali che h(k)=i

Indirizzamento aperto: tutti gli elementi sono contenuti nella tabella

Hashing 19

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

01234

k1 k4

k5

k2 k2 k7

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

Hashing 20

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

Hashing 21

Indirizzamento aperto Tutti gli elementi sono memorizzati nella

tabella Le collisioni vanno risolte all’interno della

tabella Se la posizione calcolata è già occupata occorre

cercarne una libera I diversi metodi ad indirizzamento diretto si

distinguono per il metodo di scansione adottato La funzione hash può dipendere anche dal numero

di tentativi effettuati Indirizzo=h(k, i) per l’i-esimo tentativo

Hashing 22

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. i>else <overflow>

}

Hashing 23

Ricerca search (k) {/* T denota la tabella */i=0;while ((k!=key(T[h(k, i)])) && (i<|T|))

i++;if (i < |T|)

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

}

Hashing 24

Cancellazione delete (k) {/* T denota la tabella */search(k);if (<trovato>)

<elimina elemento con chiave k>}

Hashing 25

Scansione La funzione h(k, i) deve essere tale che

tutte le posizioni della tabella siano esaminate

Sono possibili diverse forme per la funzione h(k,i) Scansione lineare Scansione quadratica Hashing doppio

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

Hashing 26

Scansione lineare h(k, i) = (h’(k)+i) mod |T|, dove h’(k) è una

funzione di hashing Si scandiscono tutte le posizioni nella

sequenza T[h’(k)], T[h’(k)]+1, .... T[|T|], 0, 1, ...., T[h’(k)]-1

Possibilità di agglomerazione primaria: gli elementi si agglomerano per lunghi tratti agglomerazione primaria = due sequenze di

scansione che hanno una collisione rimangono collidenti

Hashing 27

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

012

100

{2, 103, 104, 105,....}Caso estremo, ma il problemaesiste

Hashing 28

Scansione quadratica h(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)/2 Possibilità 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 29

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 chiave L’hashing doppio riduce i fenomeni di

agglomerazione secondaria esente da quelli di agglomerazione

primaria

Hashing 30

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 fissa

Gli indirizzi sono associati ai bucket La funzione hash restituisce in questo

caso un puntatore al bucket

Hashing 31

Hashing estendibile/2 h(k) restituisce

una stringa binaria b

I bit più significativi di b sono usati per determinare l’indirizzo del bucket

00

01

10

11

2 2

1

Lungh. locale 2

Indice

Lungh. globaleBucket 00

Bucket 01

Bucket 1

File

h(k)=11001

Hashing 32

Esempio

00

01

10

11

2

2

1

2

Indice

Bucket 00

Bucket 01

Bucket 1

File

0

1

1

1

1

Indice

Bucket 0

Bucket 1

File

10010

01100011000000101100

h(k)=00101

Dim. Bucket = 410010

011000110001100

0000100101

Hashing 33

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++;

}