Trasformazione di chiavi: hashingdeligu/didattica/aa04/algo/docs/HashingSlide.pdf · Ugo de'...

Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 15

Dizionari

Realizzazioni con trasformazione di chiavi (hashing)


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.


… e in Informatica

I dizionari sono realizzazioni di un ADT che specializza tanto le

Collezioni (insiemi) che le Mappe (memorie associative)


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.


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


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


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.


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).


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.


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


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:


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


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


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


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


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


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.



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



T

M

Empty

M

Deleted

M

Vettori di booleani


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


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


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


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.


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.


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.


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

Trasformazione di chiavi: hashingdeligu/didattica/aa04/algo/docs/HashingSlide.pdf · Ugo de'...

Documents

Transcript of Trasformazione di chiavi: hashingdeligu/didattica/aa04/algo/docs/HashingSlide.pdf · Ugo de'...