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, i)]>
else <elemento assente>
}
Hashing
22
Cancellazione
delete (k) {
/* T denota la tabella */
search(k);
if (<trovato>)
<elimina elemento con chiave k>
}
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
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
29
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
30
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
31
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
32