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

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

ordinato Operazioni:

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

Indirizzamento diretto: si associa ad ogni valoredella chiave un indice di un array – ricerca in tempoO(1)

Problemi?

Hashing 4

Indirizzamento diretto

Ogni chiavecorrisponde a el.diverso dell’array

Può portare aspreco di memoria

Es.: 10000 studentie matr.= No.decimale a 5 cifre

20

|N|-1

No. chiavi

Hashing 5

Obiettivi

N ~ No. Chiavieffettivamente usate

Tempo di ricerca O(1) D.: possibile? Nota: No. Chiavi

possibili può essere>> |T|

20

|T|-1

No. chiavi

Hashing 6

Tabella hash

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

K insieme delle possibili chiavi {0,...,|T|-1} insieme delle posizioni nella

tabella

Hashing 7

asd_library.hash.HashTablepublic class HashTable implements Dictionary_adt{public HashTable() {

this(DEFAULT_TABLE_SIZE);

}

public HashTable(int size) { allocateTable(size); makeEmpty(); isRehashable = false; }

Hashing 8

Funzioni hash perfette ecollisioni

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

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

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

Hashing 9

Requisiti di una funzione hash

Uniformità semplice: Pr[h(k)=j] ~ 1/|T| 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 funzionehash/2

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

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

• Non è nota ladistribuzionedelle chiavi

• Può aversiagglomerazionedegli elementi

In pratica: si cerca di avere indipendenza dai dati

01234

01234

Hashing 11

Interpretazione delle chiavi Tra gli elementi di K è definito un

ordinamento totale ma: Le chiavi non sono necessariamente

numeri naturali (o persino numeri) Es.: stringhe Soluzione: associare a ciascuna chiave un

intero Modalità dipendono da insieme delle chiavi e

applicazione

Hashing 12

Esempio: stringhe Possibile metodo: associare a ciascun carattere

il valore ASCII e alla stringa il numero interoottenuto in una base scelta

Esempio: base 2, posizioni meno significative adestra

Stringa = “p t” chiave = 112*21+116*20=240

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

Hashing 13

Derivazione di funzioni hash Molti metodi

Divisione Ripiegamento Mid-square Estrazione ...........

Obiettivo: distribuzione possibilmente uniforme Differenze:

Complessità Fenomeni di agglomerazione

Hashing 14

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 ip bit meno significativi uguali collidono

No potenze di 10 se le chiavi sono numeri decimali(motivo simile)

In generale, la funzione dovrebbe dipendere da tuttele cifre della chiave (comunque rappresentata)

Scelta buona in pratica: numero primo non troppovicino a una potenza di 2 (esempio: h(k)=k mod 701per |K|=2048 valori possibili)

Hashing 15

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 16

Estrazione

Si usa soltanto una parte della chiave percalcolare l’indirizzo

Esempio: 6 cifre centrali del numero dicarta di credito

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

Hashing 17

HashTable.hash() public static int hash( String key, int tableSize ){ int hashVal = 0;

for( int i = 0; i < key.length( ); i++ ) hashVal = 37 * hashVal + key.charAt( i );

hashVal %= tableSize; if( hashVal < 0 ) hashVal += tableSize;

return hashVal; }

Hashing 18

Risoluzione delle collisioni

I metodi si distinguono per la collocazionedegli elementi che danno luogo allacollisione

Concatenazione: alla i-esima posizionedella tabella è associata la lista deglielementi tali che h(k)=i

Indirizzamento aperto: tutti gli elementisono 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 listaassociata alla posizione h(k) – costo O(1)

search(k): ricerca lineare nella listaassociata alla posizione h(k) – costoO(lungh. lista associata a h(k))

delete(k): ricerca nella lista associata ah(k), quindi cancellazione – costoO(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 occorrecercarne una libera

I diversi metodi ad indirizzamento diretto sidistinguono per il metodo di scansione adottato

La funzione hash dipende anche dal numero ditentativi effettuati

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

Hashing 22

Inserimentoinsert (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

HashTable.insert()public Object insert(Comparable key ){ int collisionNum = 0; int initialPos = hash( key.toString(),table.length ); int currentPos=initialPos;

while((collisionNum<=table.length)&& table[ currentPos ] !=null &&

!table[ currentPos ].equals( key ) ){

currentPos = initialPos + k * ++collisionNum; //Compute ith probe

currentPos = currentPos % table.length; // Implementthe mod

} if (collisionNum > table.length){ System.out.println("Insertion impossible: hash table full"); return null; }

Hashing 24

HashTable.insert()else if (table[ currentPos ].equals( key ) ){ System.out.println("Element "+ key +" is alredy in

the hash table."); return key; }else{ table[ currentPos ] = key; ++currentSize; System.out.println("Insertion: ok!"); return key; }

}

Hashing 25

Ricercasearch (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 26

Cancellazionedelete (k) {/* T denota la tabella */

search(k);if (<trovato>)

<elimina elemento con chiave k>}

Hashing 27

HashTable.remove() public Comparable remove(Comparable key ){ int collisionNum = 0; int initialPos = hash( key.toString(),table.length ); int currentPos=initialPos;

while( !table[ currentPos ].equals( key )&&(collisionNum<=table.length)){

currentPos = initialPos + k *++collisionNum; // Compute ith probe

currentPos = currentPos % table.length; //Implement the mod

}

Hashing 28

HashTable.remove()if (!table[ currentPos ].equals( key )){ System.out.println("Element "+ key +" isn't in the

hash table."); return null; }else{ System.out.println("Element "+ key +" is removed

from the hash table."); table[currentPos]=null; return key; } }

Hashing 29

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à ecomportamento rispetto a fenomeni diagglomerazione

Hashing 30

Scansione lineare

h(k, i) = (h’(k)+i) mod |T|, dove h’(k) èuna funzione di hashing

Si scandiscono tutte le posizioni nellasequenza T[h’(k)], T[h’(k)]+1, .... T[|T|],0, 1, ...., T[h’(k)]-1

Possibilità di agglomerazione primaria: glielementi si agglomerano per lunghi tratti

Hashing 31

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

Prob[cella succ. gruppo]= dim(gruppo + 1)/|T|

Prob[cella isolata]= 1/|T|

Hashing 32

Scansione quadratica

h(k, i) = (h’(k)+c1i+c2i2) mod |T|, doveh’(k) è una funzione di hashing, c1 e c2sono costanti

Es.: h(k, i) = h’(k)+i2, h(k, i+1) = h’(k)-i2,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 33

Hashing doppio

h(k, i) = (h1(k)+ih2(k)) mod |T|, doveh1(k) e h2(k) sono funzioni di hashing

Es.: h(k, i) = h’(k)+i2, h(k, i+1) = h’(k)-i2,i=1,..., (|T|-1)/2

Anche la modalità di scansione dipendedalla chiave

L’hashing doppio riduce i fenomeni diagglomerazione

Hashing 34

Universal Hashing/1 Nel caso peggiore possono essere scelte n

chiavi tali che h(k1)= h(k2)= …. h(kn). Inquesto caso il tempo di retrieval è O(n)

Qualsiasi funzione hashing deterministicapuo’ incontrare questo caso peggiore.

Nell’Universal Hashing si definisce unafamiglia di funzioni hash. Una delle funzioni èselezionata a priori, in modo indipendentedalle chiavi degli elementi.

Hashing 35

Universal Hashing/2 H e’ una famiglia di funzioni hash H e’ universale se per ogni coppia x,y:

#h∈H:h(x)=h(y)=|H|/|T|

La probabilità di collisione tra due chiavi è simile aduna scelta casuale di h(x):

||/1][ TcE xy =

Hashing 36

Universal Hashing/3 Come costruire una famiglia universale H di funzioni

hash?m=|T| primox = <x0, x1 , .., xr > r+1 bytesa = <a0, a1 , .., ar > r+1 elementi random in {0,…,m-1}

ha =

H contiene mr+1 funzioni

!=

r

i

imx

0

imoda U

a

ahH =

Hashing 37

Universal Hashing/4Thm:H è una famiglia universale di

funzioni hashFissati <a1 , .., ar > esiste un solo valore a0

Percio’ ogni coppia di x e y collide esattamente per unmr valori della sequenza a

Poiche’ vi sono mr+1 valori possibili per la sequenza a,la collisione avviene con probabilita’ 1/m

!=

""="r

i

iimyxyxa

0

i000 ))(mod(a)(