Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Dizionari
Realizzazioni con trasformazione di chiavi (hashing)
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Dizionari nella vita …
Dizionario. Opera di consultazione in cui è raccolto il lessico di una o più lingue. Le singole voci sono costituite da un lemma e da una glossa che fornisce le informazioni sul significato e sugli usi del lemma. Nel D. i lemmi sono presentati in ordine alfabetico.
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
… e in Informatica
I dizionari sono realizzazioni di un ADT che specializza tanto le
Collezioni (insiemi) che le Mappe (memorie associative)
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Dizionari in Javajava.util Class Dictionarylava.lang.Objects |
+--java.util.DictionaryDirect Known Subclasses:
Hashtablepublic abstract class Dictionaryextends ObjectThe Dictionary class is the abstract parent of any class, such as Hashtable, which maps keys to values. Every key and every value is an object. In any one Dictionary object, every key is associated with at mostone value. Given a Dictionary and a key, the associated element can be looked up. Any non-null object can be used as a key and as a value.
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Mappe
Tipi: Key, Value, MapOperatori:
NewMap: void → MapSet: Map, Key, Value → MapGet: Map, Key → Value × bool
Map = {M: Key → Value: Dom(M) è finito}Set(M, k, v) = M′ M′(k) = v,
M′(k′) = M(k′), se k′ ≠ kGet(M, k) = (v, b) se M(k) = v allora b = true
se k ∉ Dom(M) allora b = false
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
L’ADT dei dizionari
Tipi: Key, Dict
Operatori:
NewDictionary: void → Dict
Search: Key, Dict → bool
Insert: Key, Dict → Dict
Delete: Key, Dict → Dict
Semantica: come Set, con Key al posto di Element
Modello semplificato:
identifichiamo elementi (valori) e
chiavi
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Tabelle ad accesso diretto
Idea: sfruttare la chiave come indice su una tabella T ad accesso diretto (vettore):
k0
k3
k4
K
M
T0
1
2
3
4
|K| − 1
Idea: sfruttare la chiave come indice su una tabella T ad accesso diretto (vettore):
Spreco di memoria se |K| è molto grande.
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Accesso con trasformazione della chiave
TKk1
k2
k3
k4
h(k3)
h(k4)
h(k1)
h(k2)
M
0
1
2
3
4
h
funzione hash
m − 1se |K| > m, h non può essere iniettiva:
Collisione: se i ≠ j e h(ki) = h(kj).
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Hashing uniforme
• P(k) è la probabilità che k sia una chiave da inserire in T
• m la dimensione di T
h è uno hashing uniforme se
∑−∈
=)(1
1)(jhk m
kP per j = 0, … , m − 1
Questo è un ideale se vogliamo che ogni chiave abbia la stessa probabilità
di essere associato ad una qualsiasi delle m posizioni in T.
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Quando le chiavi sono stringhe
W E B E R N010111 000101 000010 000101 010010 001110
23 5 2 5 18 14
Nell’esempio un carattere è codificato con 6 bit: base 26 = 64:
012345 641464186456426456423)Webern"key(" ⋅+⋅+⋅+⋅+⋅+⋅=
∑−
=−− =
1
00121 )"key("
q
i
iiqq bcaaaa L
Base = 2dim. codice
Codice del carattere ai
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Metodo della divisione
suffisso stesso lo hanno e quando ))(key())(key( allora 2 Se
21
21
ssshshm p ==
caratteri stessi gli hanno e quando ))(key())(key(
)1mod()1mod()( allora 1 Se
2121
1
0
1
0
ssshsh
bcbbckhbmq
ii
q
i
ii
=
−
=−
=−= ∑∑
−
=
−
=
Propongo:h(k) = k mod m
Questa funzione è la migliore probabilisticamente, ma la
scelta di m è critica:
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Metodo della divisione
Propongo:h(k) = k mod m
Questa funzione è la migliore probabilisticamente, ma la
scelta di m è critica:
Se b = 64 ed n = 256 una buona scelta è m = 383:
1. 383 non è potenza di 2 (quindi neppure di 64)
2. α = n/m = 256/383 ≈ 0.6 < 0.8
Un buon fattore di carico
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Metodo della moltiplicazione
k A − k A è la parte decimale di k A, che è ≥ 0 e < 1, la si moltiplica per m e se ne prende la parte intera: tutti i valori in 0..m – 1 sono possibili.
h(k) = m(k A − k A)
dove 0 < A < 1.
61803399.01 ≈= −φA
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Metodo della moltiplicazione
h(k) = m(k A − k A)
dove 0 < A < 1.Vantaggi:
1. La scelta di m non è più critica
2. Le permutazioni non danno collisione
3. Stringhe uguali tranne l’ultimo carattere danno valori molto distanti
4. Si può calcolare facilmente usando l’aritmetica con virgola fissa
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Gestione della collisione
Le collisioni, che comunque sono inevitabili per ragioni di cardinalità, sono gestite seguendo due approcci:
1. tecnica di concatenazione separata (liste di trabocco)
2. tecnica di indirizzamento aperto (sondaggi)
Comunque si tratta di imbucare le cose
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Conacatenazione separata
La tabella T è un vettore di puntatori a liste: la chiave k viene inserita nella lista puntata da T[h(k)].
T
funzione hash
h
h(k3)
h(k4)
h(k1)
h(k2)
M
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Indirizzamento aperto
Idea: utilizzare soltanto la tabella per contenere gli elementi;estendere la funzione di hash in modo da produrre sequenze
di valori, datte sondaggi
Idea: utilizzare soltanto la tabella per contenere gli elementi;estendere la funzione di hash in modo da produrre sequenze
di valori, datte sondaggi
h: K × {0, 1, …, ∞} → {0, 1, … , m − 1}
< h(k, 0), h(k, 1), h(k, 2), … >
In caso di collisione si controllano in sequenza gli indici del sondaggio finché non si raggiunge una locazione libera in T.
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Indirizzamento aperto
T
k′h(k, 0) = h′ (k)
h(k, 1) = h′ (k) + 1 mod m
k h(k, 2) = h′ (k) + 2 mod m
Mmai usata
occupatausata ma libera
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Indirizzamento aperto
T
M
Empty
M
Deleted
M
Vettori di booleani
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Inserimento
Insert (k, T)i ← 0, inserito ← falsewhile i < dim(T) and not inserito do // ci sono al più m valori distinti in un sondaggio su T [0.. m – 1]
j ← h(k, i);if not Empty[j] and not Deleted[j] and T[j] = k then
inserito ← trueelse if Empty[j] or Deleted[j] then
T [j] ← k, Empty[j] ← false, Deleted[j] ← false, inserito ← true
else i ← i + 1
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
CancellazioneDelete (k, T)
i ← 0, stop ← false
while i < dim(T) and not stop do
// ci sono al più m valori distinti in un sondaggio su T [0.. m – 1]
j ← h(k, i);
if Empty[j] then stop ← true
else if not Deleted[j] and T[j] = k then
Deleted[j] ← true, stop ← true
else i ← i + 1
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
RicercaSearch (k, T)
i ← 0, stop ← false, trovato ← false
while i < dim(T) and not trovato and not stop do
// ci sono al più m valori distinti in un sondaggio su T [0.. m – 1]
j ← h(k, i);
if Empty[j] then stop ← true
else if not Deleted[j] and T[j] = k then
trovato ← true
else i ← i + 1
return trovato
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Sondaggio lineare
h(k, i) = (h′(k) + i) mod m
dove h′ è una funzione hash ordinaria
Problemi:
• clustering primario: le entrate tendono ad addensarsi in gruppi contigui (clusters) : se T [j] è consecutiva ad un cluster idi chiavi allora la probabilità che una nuova chiave sia inseritain T [j] è (i+1)/m anzicché 1/m
• clustering secondario: il sondaggio è determinato da h′(k); dato che questi sono m, vi sono solo m sondaggi distinti.
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Sondaggio quadratico
h(k, i) = (h′(k) + c1i + c2i2) mod m
dove c1 e c2 sono costanti intere positive
Problemi:
• clustering primario: si comporta meglio del caso lineare perché valori consecutivi non sono adiacenti
• clustering secondario: il sondaggio è ancora determinato da h′(k), quindi il problema di avere solo m sondaggi persiste.
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Sondaggio per doppio hashing
h(k, i) = (h1′(k) + i h2′(k)) mod m
dove h1′ e h2′ sono funzioni hash ditinte
Problemi:
• clustering secondario: il sondaggio è determinato dalla coppia (h1′(k) , h2′(k) ); di tali coppie ve ne sono m2, per cui il clustering secondario non scompare ma è alleviato.
Il comportamento del doppio hashing è sufficientemente simile a quello ideale dello hashing uniforme.
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15
Analisi nel caso medio
Scansione α I(α) S(α)
αα−−1
2/12
2
)1(21)1(
αα−
+−Lineare 10 <≤α
Quadratica,Doppio hash α−1
1 )1ln(1 αα
−−10 <≤α
α+1 2/1 α+Liste di trabocco α≤0
n = num. chiavi, m = dim. tabella, α = n/m
S(α) = ricerca con successo, I(α) = ricerca con insuccesso
Top Related