Hash Tables
Indirizzamento diretto
Tabelle Hash
Risoluzioni di collisioni
Indirizzamento aperto
Indirizzamento diretto
U
(Insieme di tutte
le chiavi)
T[0,…,8]
2
8
7
---
0
---
1
---
2
0
3
---
1
3
K
5
(chiavi
effettive) 6
dati
aggiuntivi
key
3
4
5
5
6
6
---
7
---
8
L’indirizzamento diretto viene utilizzato quando
l’insieme delle chiavi U è piccolo.
Indirizzamento diretto
•L’indirizzamento diretto viene rappresentato,
generalmente, da un array, dove ogni casella corrisponde
ad una chiave (key) dell’insieme U.
•Ogni casella dell’array deve corrispondere ad un elemento
distinto e unico dell’insieme delle chiavi U.
•La casella T[key] punta all’elemento con la chiave key e
le sue informazioni aggiuntive.
•Se T[key]=NIL, allora non esiste nessun elemento da
mappare con chiave key.
•Se |U| non è grande, l’array non raggiunge grosse
dimensioni, utilizzando efficacemente l’indirizzamento
diretto.
Indirizzamento diretto
Operazioni:
DIRECT-ADDRESS-SEARCH(T,key)
1.
return T[key]
DIRECT-ADDRESS-INSERT(T,key)
1.
T[key] ← key
DIRECT-ADDRESS-DELETE(T,key)
1.
T[key] ← NIL
Queste tre operazioni richiedono tempo O(1).
Hash Tables
•L’indirizzamento diretto diventa difficoltoso quando U
risulta essere molto grande.
•Inoltre, se |K| << |U|, ci sarebbe un notevole spreco di
spazio di memoria.
Esempio:
Prendiamo un dizionario della lingua italiana di circa
130.000 parole con lunghezza massima di 15 lettere. Se U
corrisponde all’insieme di tutte le stringhe di lettere L={a, b,
c,…, z} di lunghezza massima di 15, sia ha:
15
| U |  L 
i 1
i
L
151
1
L 1
| K | 130.000
 71.528.434.512.099.266.416
Parole presenti nel dizionario
se |L|=21
Hash Tables
T[0, 1, …, m-1]
---
U
(Insieme di tutte
le chiavi)
----h(key0)= h(key1)
---
key
K
(chiavi
effettive)
0
h(key2)
key
1 key
h(key3)
key
2
3
-----
Viene definita una funzione hash che calcola la casella da
associare a ciascuna chiave (keyi).
h: U → {0, 1, 2, …, m-1}
Si dice, che h(keyi) è il valore hash della chiave (keyi).
Hash Tables
• Tramite le Hash Tables, la quantità di memoria
necessaria può essere ridotta a Θ(|K|), mantenendo un
costo della ricerca di O(1) nel caso medio.
• C’è la possibile presenza di collisioni, ossia quando
due chiavi distinte hanno lo stesso valore hash.
keyi≠keyj e h(keyi)=h(keyj)
• Se la funzione hash distribuisse in modo uniforme le
chiavi nelle differenti celle, la probabilità di collisioni
sarebbe minima.
• Essendo |U|>m (con m la dimensione di T), evitare del
tutto le collisioni è impossibile.
Gestire le collisioni
• Una possibile soluzione è quella di inserire tutti gli
elementi con lo stesso valore hash in una lista
concatenata.
T[0, 1, …, m-1]
U
(Insieme di tutte
le chiavi)
------key0
---
key
K
(chiavi
effettive)
key1
0
key2
-
key
1 key
key3
-
key
3
2
-----
-
Gestire le collisioni
Operazioni:
CHAINED-HASH-SEARCH(T,key)
1.
ricerca un elemento con chiave ‘key’ nella lista T[h(key)]
CHAINED-HASH-INSERT(T,x)
1.
inserisci l’elemento x all’inizio della lista T[h(key)]
CHAINED-HASH-DELETE(T,x)
1.
elimina l’elemento x nella lista T[h(key)]
•La cella T[h(key)] contiene un puntatore all’inizio della
lista concatenata in cui vengono inseriti tutti i valori con lo
stesso valore hash.
•Se nessun elemento è stato ancora inserito, T[h(key)]
contiene NIL.
Gestire le collisioni
• L’inserimento richiede un tempo O(1).
• La ricerca richiede un tempo proporzionale alla lunghezza
della lista nel caso peggiore.
• Per quanto riguarda la rimozione, può essere compiuta in
tempo O(1) quando si usa una lista bidirezionale (doubly
linked list).
• Se la lista concatenata è unidirezionale, per poter
eseguire la rimozione di un elemento bisogna fare una
ricerca per conoscere l’elemento che precede x. Il tempo
quindi è proporzionale alla lunghezza della lista nel caso
peggiore.
Analisi di hashing con liste
concatenate
• Nel caso peggiore tutti gli elementi hanno lo stesso
valore di hash e quindi tutto viene gestito come se fosse
una lista concatenata.
• Nella nostra analisi si fa l’assunzione di uniformità
semplice della funzione hash. Questo vuol dire che la
funzione hash distribuisce bene l’insieme delle chiavi da
memorizzare sulle m celle.
• Si assume anche che il calcolo della funzione hash
h(key) è costante,O(1).
• Si assume, inoltre, che l’accesso alle celle si fatto in
tempo costante, O(1).
• Si definisce il fattore di carico α per T come n/m, cioè
il numero medio di elementi in ogni lista quando ne sono
stati inseriti n in totale.
Analisi di hashing con liste
concatenate
Sotto queste ipotesi, in una tabella hash che
risolve le collisioni per concatenazione una ricerca
senza successo richiede un tempo medio di
Θ(1+ α).
a.
b.
c.
Le chiavi vengono equamente distribuite per tutte le m
celle. Dunque, la lunghezza media delle liste equivale
a α.
Per cui il numero medio di elementi da esaminare in
una ricerca senza successo è pari a α.
A questo si aggiunge il tempo di calcolo di h(key),
ottenendo un tempo medio di Θ(1+ α).
Analisi di hashing con liste
concatenate
Sotto queste ipotesi, in una tabella hash che
risolve le collisioni per concatenazione una ricerca
con successo richiede un tempo medio di
Θ(1+ α).
a. Le chiavi vengono equamente distribuite per tutte le m
celle.
b. L’analisi è più complessa, in quanto dipende in quale
punto della lista mediamente si trova l’elemento x da
trovare.
c. Per eseguire questo calcolo più agilmente si suppone
che gli elementi vengono inseriti alla fine della lista.
Questo non cambia il risultato.
Analisi di hashing con liste
concatenate
d. Sotto questa ipotesi, quando l’elemento i-esimo è
inserito, esso viene messo in una lista lunga in media
(i-1)/m.
e. Per trovare l’elemento i-esimo, bisogna calcolare
h(keyi) ed esaminare mediamente (i-1)/m elementi.
f. Dunque il tempo medio complessivo è:
1 n
1 n
i 1
1 n
T (n)   Tempo(i )   (1 
) 1 
(i  1) 

n i 1
n i 1
m
nm i 1
1 n(n  1)
 1
 1
 1 
 (1   )
nm
2
2 2m
Analisi di hashing con liste
concatenate
Il significato di questa analisi?
•Se gli elementi all’interno della tabella hash sono n e
risultano proporzionali a m, si ha n=O(m) e, quindi,
α = O(m)/m = O(1).
•Quindi, la ricerca media richiede in media tempo
costante.
•Essendo la ricerca l’operazione più costosa, si ottiene un
tempo medio per tutte le operazioni pari a O(1).
Requisiti per una buona funzione
hash
L’assunzione di uniformità semplice della funzione hash
equivale a supporre che ogni chiave ha uguale probabilità
di essere collocata in una qualsiasi cella.
Più formalmente, supponiamo che ogni chiave key è
pescata indipendentemente dalle altre da U con probabilità
P(key). Allora si ha:
 P(key) 
key:h ( key )  j
1
m
Raramente, si è a conoscenza della distribuzione P.
Per questo motivo si utilizzano in pratica delle euristiche
che possono produrre una buona funzione hash.
Il metodo della divisione
Nel metodo della divisone si utilizza il resto di key diviso m:
h(key) = key mod m
La scelta di m deve essere fatto in maniera opportuna,
che dipende, in genere, dalla tipologia di chiavi (numeri
decimali, i byte di caratteri ASCII,…).
Una buona scelta è quella di scegliere un numero primo
non vicino a una potenza di 2.
Per esempio, se n= 2000 e le chiavi sono equamente
probabili, il numero primo 701, che è vicino a 2000/3, può
essere una buona scelta. Si ha quindi:
h(key) = key mod 701
Il metodo della moltiplicazione
Richiede due passi:
1. Si moltiplica K per una costante A, 0 < A < 1, e si
estrae la parte non intera.
2. Si moltiplica il risultato per m e si prende la parte
intera.
In breve:
h(key)  m((key  A)mod1) 
La scelta di m non è più critica. Quindi, si può sceglie un
valore che renda la moltiplicazione efficiente.
Anche se la funzione hash è buona per ogni valore di A, ci
sono alcune scelte migliori. Per esempio:
A≈(√5 – 1)/2=0.6180339887…
Indirizzamento aperto
• Nell’indirizzamento aperto ogni cella della tabella
contiene o un elemento dell’insieme U o NIL.
• Quando si ricerca un elemento, si esaminano
sistematicamente le posizioni della tabella finché o si
trova l’elemento desiderato o è chiaro che non è
presente nella tabella.
• Non ci sono puntatori e liste concatenate, tutto è
memorizzato nella tabella.
• Quindi, la tabella hash può riempirsi finché nessun altro
elemento può essere inserito.
• Il fattore di carico α ≤ 1.
Scansione nell’indirizzamento
aperto
Quando si ricerca o si inserisce un elemento, si esaminano
in sequenza le posizioni della tabella finché o si trova
l’elemento desiderato o si trova NIL.
La sequenza <s0, s1 , s2 , …, sm-1,> è una permutazione
degli indici <0, 1, 2, …, m-1> della tabella e dipende dalla
chiave key scelta.
Quindi la funzione hash è del tipo:
h: U x {0,1, 2, …, m-1} → {0,1, 2, …, m-1}
E la sequenza di scansione è:
<h(key,0), h(key,1), …, h(key,m-1)>
Dunque, si ha un problema di quante posizioni della tabella
in media si vengono visitate.
Inserimento nell’indirizzamento
aperto
HASH-INSERT(T,key)
1.
i←0
2.
repeat j ← h(key,i)
3.
if T[j] = NIL
4.
then T[j] ← key
5.
return j
6.
else i ← i+1
7.
until i = m
8.
error “overflow sulla tabella hash”
La ricerca della posizione termina quando si trova una
posizione vuota.
Ricerca nell’indirizzamento aperto
HASH-SEARCH(T,key)
1.
i←0
2.
repeat j ← h(key,i)
3.
if T[j] = key
4.
then return j
5.
else i ← i+1
6.
until T[j] = NIL o i = m
7.
return NIL
La ricerca della chiave termina quando si trova la chiave o
una posizione vuota, poiché key sarebbe stata inserita
proprio li.
Ipotesi di uniformità della funzione
hash
• Nell’ipotesi di uniformità della funzione hash si
considera equamente probabile una qualunque delle m!
permutazioni delle posizioni data la chiave key.
• Questa ipotesi generalizza quella di uniformità semplice,
in quanto viene restituita dalla funzione hash non un solo
valore di {0, 1, 2, …, m-1}, ma un’intera sequenza.
• Per questo motivo, risulta difficile generare una buona
funzione hash.
• Ci sono alcune approssimazioni:
la scansione lineare, quella quadratica e il doppio hash.
Scansione lineare
Data una funzione hash h’: U → {0, 1, …, m-1}, il metodo di
scansione lineare usa la funzione hash:
h(key,i) = (h’(key) + i) mod m
•La scansione lineare è facile da realizzare.
•Presenta un problema conosciuto come fenomeno di
agglomerazione primaria.
•Le posizioni occupate si accumulano in lunghi tratti,
aumentando il tempio medio di ricerca.
Scansione quadratica
Data una funzione hash h’: U → {0, 1, …, m-1}, il metodo di
scansione quadratica usa la funzione hash
h(key,i) = (h’(key) + c1 i + c2 i2) mod m
•Le scansioni successive dipendono in modo quadratico
dal numero i di accessi.
•Questo metodo funziona meglio della scansione lineare,
ma i valori c1, c2 e m devono essere scelti in modo che la
sequenza scansioni l’intera tabella.
•Come per la scansione lineare, l’accesso iniziale
determina l’intera sequenza, quindi sono usate solo m
distinte sequenze di scansione. Per questo si dice che c’è
un problema di agglomerazione secondaria.
Hashing doppio
Il metodo di hashing doppio usa una funzione hash del tipo:
h(key,i) = (h1(key) + i h2(key)) mod m
•Diversamente dalla scansione lineare o quadratica, la
sequenza di scansione dipende dalla posizione iniziale e
dalla distanza determinata dalla seconda funzione di hash.
Per esempio, si può usare:
h1 = key mod m
h2 = 1+ (key mod m’)
•Questo permette di usare Θ(m2) sequenze di scansione,
avvicinandosi all’assunzione di uniformità della funzione di
hash.
Analisi dell’indirizzamento aperto
Diamo solo i risultati:
• Data una tabella hash a indirizzamento aperto con
fattore di carico α=n/m <1, il numero medio di accessi di
una ricerca senza successo è al più 1/(1-α),
assumendo l’uniformità della funzione hash.
• Data una tabella hash a indirizzamento aperto con
fattore di carico α=n/m <1, il numero medio di accessi di
una ricerca con successo è al più 1/α ln(1/(1-α)),
assumendo l’uniformità della funzione hash e che ogni
chiave sia ricercata nella tabella in modo equamente
probabile.