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 chiave corrisponde a el. diverso dell’array

Può portare a spreco di memoria

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

20

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

20

N-1

No. chiavi

Hashing 7

Tabella hash

Dato l’insieme base di un dizionario:

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

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

nella tabella

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

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 intero ottenuto in una base scelta

Esempio: base 2, posizioni meno significative a destra

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

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 17

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 18

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 19

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 20

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 dipende anche dal numero di

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

Hashing 21

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 22

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>

}

Implementazione inefficienteSe elemento assente si esamina tutta la tabella

Hashing 23

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

<elimina elemento con chiave k>}

Implementazione inefficienteStessi motivi del caso precedente

Hashing 24

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 25

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

Hashing 26

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 27

Scansione quadratica h(k, i) = (h’(k)+c1i+c2i2) mod |T|, dove

h’(k) è una funzione di hashing, c1 e c2 sono 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 28

Hashing doppio h(k, i) = (h1(k)+ih2(k)) mod |T|, dove

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

dipende dalla chiave L’hashing doppio riduce i fenomeni di

agglomerazione

Hashing 29

Implementazione Java Tabella rappresentata con array Chiavi di tipo Comparable

Convertite in String Funzione hash applicata a oggetti

String i = 0: h(S, 0) = h(S)

S una stringa i > 0: h(S, i) = h(S) + cost * i

cost = 3

Hashing 30

Implementazione Java/cont.

Due array per rappresentare la tabella: Comparable table[] - entry della tabella Boolean isActive[] - per la gestione

isActive[i] = true se table[i] != null oppure table[i] == null, ma table[i] ha precedentemente contenuto un elemento

Problema: efficienza I metodi di ricerca e cancellazione visti

precedentemente possono essere poco efficienti Es.: se elemento assente viene scandita l’intera tabella

Hashing 31

Esempio: ricerca Scansione lineare

h(k, i) = k mod 11 + 3*i Ricerca chiave 27

Posizione (5) occupata da elemento di chiave 16

Come facciamo a sapere che possiamo interrompere la ricerca?

Necessario riconoscere le posizioni che sono state occupate da elementi poi rimossi

33-2-

1516

-

-

27

-

-

Hashing 32

Classe HashTablepublic class HashTable implements Dictionary_adt {

private static final int DEFAULT_TABLE_SIZE = 23; /** The array of elements. */protected Comparable [ ] table; // The array of elementsprotected boolean [] isActive;protected int currentSize; // The number of occupied cellsprotected boolean isRehashable; //true if table can be expandedprotected int k =3; //Coefficient for LinearProbing

/* Seguono costruttori */

Hashing 33

Classe HashTable/2/* Costruttore principale */public HashTable(int size, boolean rehash) {/* Alloca due array table[] e isActive[] di simensionesize. Se rehash == true -> la tabella puo’ essereespansa se e’ piena per piu’ della meta’. Inizializza la tabella: table[i] = null e isActive[i] = false per ogni i */}/* Altri costruttori */

/* Seguono i metodi */

Hashing 34

Classe HashTable/3/* La nostra funzione 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; /* | hashVal | < tableSize */if( hashVal < 0 ) /* si puo’ avere overflow -> hashVal < 0 */

hashVal += tableSize; /* Cosi’ hashVal diventa > 0 */

return hashVal;}/* Altri metodi */

Hashing 35

Classe HashTable/4/* Inserimento */public Object insert(Comparable key ) {int collisionNum = 0; /* No. collisioni */int initialPos = hash( key.toString(),table.length );int currentPos=initialPos;int insertPos= -1; /* Se alla fine vale -1 -> tabella piena

(caso di tabella non espandibile) */

/* Continua … */

Hashing 36

Classe HashTable/5while(collisionNum<table.length-1) {

if (table[currentPos] == null) { /* trovata posizione libera */if (insertPos == -1)

insertPos = currentPos;if (!isActive[currentPos])

break; /* se posizione non attiva -> elemento non presente,

puoi uscire dal ciclo while */} /* End if */else if (table[ currentPos ].compareTo( key )==0) { //table[currentPos]!= null

System.out.println("Element "+ key +" is alredy in the hash table.");

return key;} /* End else */currentPos = initialPos + k * ++collisionNum;

currentPos = currentPos % table.length; // Implement the mod} /* End while */

Hashing 37

Classe HashTable/6 if (insertPos!= -1) { /* E’ stata trovata una posizione libera */

table[ insertPos ] = key;isActive[ insertPos] = true;++currentSize;System.out.println("Insertion of "+key+": in position " +currentPos);if((isRehashable)&&(currentSize > table.length/2)) {

System.out.println("Rehash!");rehash();

} /* End if */return key;} /* End if */else { /* Non e’ stata trovata una posizione libera */

System.out.println("Insertion impossible: hash table full");return null;

} /* End else */} /* End inserimento */

Hashing 38

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

/* Variabili hanno stesso significato che in insert() *//* Continua */

Hashing 39

Classe HashTable/8while ( ( ((table[currentPos] == null)&& isActive[currentPos] )||( (table[currentPos] != null) && (table[currentPos].compareTo(key)!=0))) &&(collisionNum < table.length-1)) {

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

currentPos = currentPos % table.length; // Implement the mod} /* End while *//* Esce da ciclo while se elemento trovato o tutta la tabella esaminatasenza trovare elemento con chiave cercata *//* Continua */

Hashing 40

Classe HashTable/9/* Continua dalla slide precedente */if ((table[currentPos]==null)||table[currentPos].compareTo(key) !=0) {

System.out.println("Element "+ key +" isn't in the hash table.");

return null;} /* End if */else{

System.out.println("Element "+ key +" is in the hash table.");table[currentPos]=null;return key;

} /* End else */} /* End remove() *//* Altri metodi e fine della classe HashTable */

Hashing 41

Classe HashTable/cont. Metodo find() implementa la ricerca

Approccio identico ai casi precedenti Ricerca, inserimento e cancellazione piu’

efficienti Vengono controllati soltanto gli elementi non

nulli o con corrispondente campo isActive a true

Gli elementi con campo isActive a true sono quelli che hanno contenuto un elemento in seguito rimosso

Hashing 42

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 43

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 44

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 45

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

}