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



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
0
1
No. chiavi
N-1
Hashing
5
Obiettivi




0
1
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 con N celle
 h: K  {0,...,N-1}


K insieme delle possibili chiavi
{0,...,N-1} insieme delle posizioni nella
tabella, dette pseudochiavi
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
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
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
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
11
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
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 = “pt”  pseudochiave = 112*21+116*20=340
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


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
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 può dipendere 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>
}
Hashing
23
Cancellazione
delete (k) {
/* T denota la tabella */
search(k);
if (<trovato>)
<elimina elemento con chiave k>
}
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

agglomerazione primaria = due sequenze di
scansione che hanno una collisione rimangono
collidenti
Hashing
26
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
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. 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
28
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
29
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
30
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
31
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
32
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
33