Hashing
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
2
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
3
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
4
Indirizzamento diretto



0
2
Ogni chiave
corrisponde a
el. diverso
dell’array
Può portare a
spreco di
memoria
Es.: 10000
studenti e
matr.= No.
decimale a 5
cifre
No. chiavi
N-1
Hashing
5
Obiettivi




0
2
N ~ No. Chiavi
effettivamente
usate
Tempo di ricerca
O(1)
D.: possibile?
Nota: No. Chiavi
possibili può
essere >> N
No. chiavi
N-1
Hashing
6
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
7
Funzioni hash perfette e
collisioni

Funzione hash perfetta:




In generale N < |K| (spesso N << |K|)


k1!=k2  h(k1) != h(k2)
Richiede N >= |K|
Raramente ragionevole in pratica
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
8
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
9
Requisiti di una funzione
hash/2

Esempio: sia |T|=5 e h(k)=k mod 5
{1, 7, 10, 14}
• Non è nota la
distribuzione
delle chiavi
• Può aversi
agglomerazione
degli elementi
{1, 6, 11, 16}
0
1
2
3
4
0
1
2
3
4
In pratica: si cerca di avere indipendenza dai dati
Hashing
10
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
11
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
12
Derivazione di funzioni hash

Molti metodi







Divisione
Ripiegamento
Mid-square
Estrazione
...........
Obiettivo: distribuzione possibilmente uniforme
Differenze:


Complessità
Fenomeni di agglomerazione
Hashing
13
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
14
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
15
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
16
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
17
Concatenazione
h(k1)= h(k4)=0
h(k5)= h(k7)=h(k2)=4


0
1
2
3
4



k1
k4
k7
k5
Es.: h(k)=k mod 5
k1=0, k4=10
k5=9, k7=14, k2=4
Hashing
k2
k2
18
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
19
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
20
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
21
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,Implementazione
i)]>
inefficiente
Se elemento assente si esamina
else <elemento assente>
tutta la tabella
}
Hashing
22
Cancellazione
delete (k) {
/* T denota la tabella */
search(k);
if (<trovato>)
<elimina elemento con chiave k>
}
Implementazione inefficiente
Stessi motivi del caso precedente
Hashing
23
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
24
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
25
Agglomerazione primaria

h(k, i) = (h’(k)+i) mod 101, h’(k)=k mod 101
{2, 103, 104, 105,....}
Caso estremo, ma il problema
esiste
0
1
2
100
Hashing
26
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
27
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
28
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
29
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
30
Esempio: ricerca

Scansione lineare


Ricerca chiave 27



h(k, i) = k mod 11 + 3*i
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
Hashing
33
2
15
16
27
31
Classe HashTable
public class HashTable implements Dictionary_adt {
private static final int DEFAULT_TABLE_SIZE = 23;
/** The array of elements. */
protected Comparable [ ] table; // The array of elements
protected boolean [] isActive;
protected int currentSize;
// The number of occupied cells
protected boolean isRehashable; //true if table can be expanded
protected int k =3;
//Coefficient for LinearProbing
/* Seguono costruttori */
Hashing
32
Classe HashTable/2
/* Costruttore principale */
public HashTable(int size, boolean rehash) {
/* Alloca due array table[] e isActive[] di simensione
size. Se rehash == true -> la tabella puo’ essere
espansa 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
33
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
34
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
35
Classe HashTable/5
while(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
36
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
37
Classe HashTable/7
public 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
38
Classe HashTable/8
while ( ( ((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 esaminata
senza trovare elemento con chiave cercata */
/* Continua */
Hashing
39
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
40
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
41
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
42
Hashing estendibile/2


h(k) restituisce
una stringa
binaria b
I bit più
significativi di b
sono usati per
determinare
l’indirizzo del
bucket
File
Lungh. locale
2
Bucket 00
Lungh. globale
h(k)=11001
2
2
Bucket 01
00
01
10
1
Bucket 1
11
Indice
Hashing
43
Esempio
File
File
2
1
01100
01100
00001
01100
h(k)=00101
1
Bucket 0
00
1
01
1
01100
01100
01100
Bucket 01
10010
Bucket 1
2
10
10010
Bucket 00
2
0
Indice
00001
00101
Bucket 1
11
Indice
Dim. Bucket = 4
Hashing
1
44
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
45