Primo approccio (semplice): Indirizzamento Direttouv/IASD/hash.pdfIn una tabella di login di un...

Primo approccio (semplice): Indirizzamento Diretto

Assumiamo che:• l’universo delle chiavi sia U = {0, 1, . . . , u− 1}

• per ogni coppia di elementi x e y valga key[x] 6= key[y]

• Ogni elemento x verrá memorizzato nella locazione T [key[x]] di unarray, T [0 . . . u− 1] che inizialmente ha T [i] = NULL, ∀i

Gli algoritmi:

SEARCH(T, k)

return (T [k])

INSERT(T, x)

T [key[x]] = x

DELETE(T, x)

T [key[x]] = NULL

Complessitá: Θ(1)

Universita degli Studi di Salerno – Corso di Introduzione agli Algoritmi e Strutture Dati – Prof. Ugo Vaccaro – Anno Acc. 2014/15 – p. 1/34

Problemi con l’approccio appena descritto:

• Se l’universo delle possibili chiavi U = {0, . . . , u− 1} é molto grande,potremmo non avere memoria sufficiente per memorizzare l’arrayT [0 . . . u− 1].

• In piú, anche se avessimo memoria sufficiente, molta risulterebbeessere sprecata se l’insieme S degli elementi che andremmoeffettivamente a memorizzare fosse piccolo.

Esempi :In una tabella di login di un computer con 100 utenti, dove le usernamesono di lunghezza 10 e consistono di caratteri minuscoli, vale che|U | = 2610, mentre |S| = 102 (e quindi |S| ≪ |U |).

In una tavola dei simboli usata durante la compilazione di un programmacon 1000 variabili di lunghezza fino a 32 caratteri ASCII, avremmo|U | ≈ 9432, mentre |S| = 103


Introduzione allo Hashing

Per introdurre lo Hashing, rivediamo il metodo di indirizzamento diretto, incui ogni elemento di chiave k viene memorizzato nella locazione T [k]

U(universo delle chiavi)

T0

1

2

3

4

5

6

7

8

9

S(chiavi usate)

23

69

0

5

1

78

4


Introduzione allo Hashing: indirizzamento indiretto

Idea: fissare la dimensione della tabella T ad m = O(|S|)(≪ |U |). Inquesto caso, peró, l’elemento x ∈ S con chiave key[x] = k non puó esserememorizzato in T [k] (in quanto k potrebbe essere > delle dimensioni dellatabella). Useremo allora una funzione h : k ∈ U → h(k) ∈ {0, . . . ,m −1} (funzione di hash), e memorizzeremo l’elelemento x in nella locazioneT [h(key[x])]


T0

m− 1

S(chiavi usate)

k1k2

k3

k4

h(k1)

h(k2)

h(k3)

h(k4)


Esempio: |U | = 100, |S| = 10, h : k ∈ U → h(k) = k (mod 10)


T0

1

2

3

4

5

6

7

8

9

S(chiavi usate)

4213

369 76

• Usando la funzione di hash h : k ∈ U → h(k) = k (mod 10) abbiamoridotto la memoria necessaria da 100 (= |U |) locazioni a 10 locazioni, maadesso si possono verificare collisioni , ovvero si possono presentare duechiavi k1 6= k2 per cui h(k1) = h(k2)


Ricapitolando

• Se U rappresenta l’universo di tutte le possibili chiavi, ed S l’insiemedelle chiavi effettivamente usate, con |S| ≪ |U |, possiamo usare unafunzione di hash h : k ∈ U → h(k) ∈ {0, . . . ,m− 1}, ( h calcolabile intempo O(1)), per memorizzare le chiavi in una tabella T con solo m

locazioni di memoria (tipicamente m≪ |U |).

Problema : Possono occorrere delle collisioni se si presentano duechiavi k1 6= k2 per cui h(k1) = h(k2)

• Un tale problema (l’occorrenza di collisioni) é inevitabile se |S| > m,pertanto occorre prevedere delle tecniche efficienti per risolvere i conflittigenerati dalle collisioni occorse.


Metodi per risoluzione delle collisioni

Vi sono due metodi per la risoluzione di collisioni:

Concatenazione : Si mantiene una lista linkata (esterna alla tabellaT ) composta da tutti gli elementi che la funzione di hash indirizza allastessa locazione dell’array T (una lista per ogni locazione ). Questometodo é molto semplice da gestire. Usa allocazione dinamica dellamemoria.

Indirizzamento Aperto : Si memorizzano tutte le chiavi nella tabellaT . Quando accade una collisione, si usa di nuovo la funzione di hashper trovare una nuova locazione libera per memorizzare l’elementonella tabella T . Facile da implementare e non usa allocazionedinamica della memoria. Crea peró altri problemi, che vedremo inseguito ...


Risoluzione di collisioni mediante Concatenazione

Idea di base : memorizzare in un unica lista linkata tutti gli elementi che lafunzione di hash assegna alla stessa locazione di memoria t della tabellaT . La locazione t punterá alla testa di una tale lista.


T0

m− 1

S(chiavi usate) k1

k2

k3

k4

k1

k2

k3

k4

k5

k5

k6

k6


Risoluzione di collisioni mediante Concatenazione

Algoritmi:

CHAINED-HASH-SEARCH(T, k)

cerca l’elemento con chiave k in T [h(k)]

Complessitá: O(lunghezza della lista)

CHAINED-HASH-INSERT(T, x)

inserisci x nella lista T [h(key[x])]

Complessitá: O(1)

CHAINED-HASH-DELETE(T, x)

cancella x dalla lista T [h(key[x])]

Complessitá: O(1) se la lista é doppiamente linkata, altrimenti occorretrovare il predecessore di x per eseguire la cancellazione.


Esempio di hash con concatenazione

m = 9, h(k) = k (mod 9), S = {5, 10, 19, 33, 20, 15, 12, 17, 28}

0

1

2

3

4

5

6

7

8

T

28

20

12

5

15

17

33

19 10


Analisi di Hashing con concatenazione

Il caso peggiore per la ricerca di un elemento in una tabella hash conconcatenazione occorre quando tutte le chiavi di S sono state indirizzatedalla funzione h nella stessa locazione di T . In tal caso, il temporichiesto da SEARCH(T, k) é Θ(n), dove n = |S|.

Il caso medio dipende da come sono state “ben” (ovvero uniformemente)distribuite le n chiavi tra le m locazioni di T .

Data una tabella di taglia m, ed n elementi da memorizzarvi, definiamo ilfattore di carico come α = n/m. La nostra analisi sará in termini di α.

Ai fini dell’analisi, faremo la cosiddetta assunzione di hashing semplice eduniforme, il che significa che ogni elemento di S ha la stessa probabilitá(= 1/m) di essere indirizzato dalla funzione h in una qualunque locazionedi T , indipendentemente dagli altri elementi.


Analisi di Hashing con concatenazione: Ricerca senza successo

In una tabella hash in cui le collisioni sono risolte mediante concate-nazione, la ricerca di un elemento non presente nella tabella (ricerca senzasuccesso) prende tempo Θ(1+α), in media, sotto l’ipotesi di hashing sem-plice ed uniforme

Prova:• La assunzione di hashing semplice ed uniforme implica che ogni chiaveha eguale probabilitá di essere indirizzata ad ognuna delle m locazionidella tabella.• Il tempo medio per la ricerca senza successo della chiave k é pertantopari al tempo medio per scorrere una qualsiasi delle m liste.• Il tempo medio per scorrere una qualsiasi delle m liste é pari al numeromedio di elementi in essa, che é n/m = α.• Quindi, il tempo medio per la ricerca senza successo della chiave k éΘ(1 + α) (includendo il tempo per il calcolo di h(k)).


Analisi di Hashing con concatenazione: Ricerca con successo

In una tabella hash in cui le collisioni sono risolte mediante concate-nazione, la ricerca di un elemento presente nella tabella (ricerca con suc-cesso) prende tempo Θ(1+α), in media, sotto l’ipotesi di hashing sempliceed uniforme

Conseguenze : Se il fattore di carico α = n/m é O(1) (costante), allora iltempo di ricerca medio in una tabella hash, sotto l’ipotesi di hashingsemplice ed uniforme, é O(1)!

Un analogo risultato vale anche per i tempi di inserzione e dicancellazione in una tabella hash.


Osservazioni

• Nelle situazioni pratiche in cui vengono eseguite solo le operazioni diSEARCH(T, k), INSERT(T, x), e DELETE(T, x), il metodo basato sulletabelle hash é talmente veloce che, generalmente, esso é il metodoprevalentemente impiegato.

• In generale, l’hashing non viene usato nelle situazioni in cui i datidevono essere memorizzati su memorie secondarie, oppure nellesituazioni in cui é importante anche l’ordine relativo degli elementimemorizzati nella struttura dati (ad esempio, se SEARCH(T, k) restituisceil valore NIL, vorremmo poter sapere in ogni caso chi é l’elemento con lachiave piú prossima a k). In tali situazioni si preferiscono strutture datibasate su alberi di ricerca.


Sulle funzioni hash

Uno dei problemi piú importanti é come scegliere la funzione di hash.

Una buona funzione di hash dovrebbe poter soddisfare l’assunzione dihash semplice ed uniforme. In altre parole, sotto l’assunzione che lechiavi vengano estratte da U in maniera indipendente tra di loro ed inaccordo ad una distribuzione di probabilitá P , occorre che

∑

k h(k)=j

P (k) =1

mj = 0, . . . ,m− 1

dove P (k) é la probabilitá di estrarre la chiave k e m la taglia della tabellahash usata.

Sfortunatamente, P non é in generale nota...

In pratica, vengono usate delle euristiche per scegliere funzioni hash chefunzionino “bene”. Assumeremo da ora in poi che l’universo delle chiavi Usia l’insieme dei numeri naturali, (o che le chiavi possano esserecodificate in tal modo).


Esempi di scelta di funzioni hash

Metodo della divisione: h(k) = k (mod m)

Esempio: Se m = 52 e k = 35 allora h(k) = 27.

Regole di “buon senso”:

• In generale, vorremmo che la funzione h “disperda” le chiavi k nellamaniera piú uniforme possibile all’interno della tabella T .

• Spesso le sono simili o hanno valori piú o meno uguali. Non vogliamoche queste regolaritá vengano preservate dalla funzione di hash h.Quindi, in generale, h(k) e h(k + ǫ) devono differire di “molto” tra di loro,anche se ǫ é piccolo.

• Evitare quindi potenze di 2 per valori di m. Altrimenti non tutti i bit di kverranno usati da h (ad es., se m = 2p allora h(k) dipende solo dai p bitsmeno significativi di k, e quindi chiavi che avessero tali p bits ugualiverrebbero indirizzate alla stessa locazione di memoria).



• Per le stesse ragioni enunciate prima, occorre evitare per i valori di m lepotenze di 10, se usiamo numeri decimali per i valori chiave

• Se m = 2p − 1 e k é una stringa di caratteri interpretata in base 2p,allora chiavi che sono permutazione delle stesse cifre verrebberoindirizzate alla stessa locazione di memoria (ad es., se m = 15, le chiavi51 e 15, interpretate in base 24, colliderebbero sotto la funzione hash k

(mod m)). Quindi, evitare anche questi valori di m.

• Buoni valori di m sono numeri primi non troppo vicini a potenze di 2. Ades., se n = 2000, una buona scelta é h(k) = k (mod 491) (491 é unnumero primo e 512 é una potenza di 2).



Metodo della moltiplicazione: Dati 0 < A < 1, h(k) = ⌊m(kA (mod 1))⌋

• La scelta di m non é critica per questo metodo. Si puó quindi sceglierem potenza di 2, il che rende la funzione facile da calcolare.

• Un buon valore di A é considerato essere A = 0.61803...


C’é un problema...

Osservazione: Qualunque sia la scelta della funzione di hash, un“avversario” potrebbe sempre scegliere un insieme di chiavi cheverrebbero memorizzate nella stessa locazione della tabella T . Ciórenderebbe il metodo basato sull’hash completamente inefficiente, inquanto avremmo una unica lista lunga quanti sono gli elementimemorizzati.

Se potessimo scegliere “casualmente” una funzione di hash da uninsieme di funzioni opportunamente progettato, indipendentemente dallechiavi da memorizzare, potremmo ottenere buone performances,qualunque siano le chiavi che in seguito si presenteranno per esserememorizzate (perché l’ “avversario” non potrebbe conoscere a priori lafunzione di hash scelta a caso da noi, un pó come si procedeva nellascelta del pivot nel QuickSort...) .


Hash Universale

Definizione: Sia U l’universo delle chiavi e sia H una collezione finita difunzioni di hash, dove ciascuna funzione h ∈ H, h : U → {0, . . . ,m− 1},mappa le chiavi di U in {0, . . . ,m− 1}. L’insieme H é detto universale se∀x, y ∈ U (x 6= y), vale che

|{h ∈ H : h(x) = h(y)}| =|H|

m

• In altri termini, la probabilitá di avere una collisione per due valori dellechiavi x e y, data una funzione di hash scelta a caso nell’insieme H, é paria 1/m.

• Se scegliessemo la funzione di hash in un insieme universale H, allora ilproblema dell’avversario descritto nella slide precedente scomparirebbe.


Costruzione di insiemi universali di funzioni di hash

• Scegli la taglia m della tabella come un numero primo

• Decomponi la chiake k in r + 1 bytes, in modo tale che k = k0k1 . . . kr,ed inoltre il valore di ogni ki é strettamente inferiore a m.

• Sia a = a0a1 . . . ar una sequenza di numero scelti a caso, doveai ∈ {0, . . . ,m− 1}. Ci sono mr+1 possibili tali sequenze a.

• Definiamo una funzione di hash ha come ha =∑r

i=0 aiki (mod m), el’insieme H = ∪a{ha}

Teorema : L’insieme H é un insieme universale di funzioni di hash.


Risoluzione di conflitti mediante Indirizzamento Aperto

Indirizzamento Aperto: Tutti gli elementi sono memorizzati direttamentenella tabella hash (non vi sono puntatori ad elementi esterni, comenell’hash per concatenazione). Pertanto, in ogni locazione della tabella ovi é un elemento, oppure vi é NULL (denotante locazione vuota).

La tabella hash é quindi statica (la memoria assegnata agli elementi noncresce al loro numero). Pertanto, il fattore di carico α = n/m ≤ 1.

La questione delicata é come trovare una locazione in cui inserire nuovielementi (nell’hashing per concatenazione si creava semplicemente unanuova locazione di memoria e dalla tabella hash c’era un puntatore a talenuova locazione, che a sua volta puntava ad un (eventuale) vecchioelemento giá inserito).

Nella tecnica dell’inidirizzamento aperto, per trovare una locazione per unnuovo elemento da inserire, si esaminerá la tabella hash stessa, in unqualche modo sistematico, fin quando non si troverá una locazione libera.


Piú precisamente...

La funzione di hash é ora definita come

h : U × {0, 1, . . . ,m− 1} → {0, 1, . . . ,m− 1}

Per ogni valore chiave k, si calcolano uno dopo l’altro i valorih(k, 0), h(k, 1), . . . , fin quando non si trova un valore h(k, i) della tabellanon ancora occupato da un elemento, e la chiave k viene memorizzata intale locazione libera.

HASH-INSERT(T, k)

i = 0

repeat j = h(k, i)

if T [j] = NULL

then T [j] = k

return j

i = i+ 1

until i = m

error “hash table overflow” % (La tabella é piena)

k

U

h(k, 0)

h(k, 1)

h(k, 2)

h(k, j)

x

y

z

T


Ricerca in una tabella hash con indirizzamento aperto

Nella ricerca di una chiave k, si procede come se si volesse inserire k,usando la funzione hash per testare le locazioni in cui potrebbe esserestata inserita precedentemente k, fin quando o la si trova o si termina laricerca senza successo (restituendo il valore NIL).

HASH-SEARCH(T, k)

i = 0

repeat j = h(k, i)

if T [j] = k

then return j

else i = i+ 1

until T [j] = NULL oppure i = m

return NULL

k

h(k, 0)

h(k, 1)

h(k, 2)

h(k, i)

x

y

z

T

kj

return j


Ricerca in una tabella hash con indirizzamento aperto

Nella ricerca di una chiave k, si procede come se si volesse inserire k,usando la funzione hash per testare le locazioni in cui potrebbe esserestata inserita precedentemente k, fin quando o la si trova o si termina laricerca senza successo (restituendo il valore NIL).

HASH-SEARCH(T, k)

i← 0

repeat j = h(k, i)

if T [j] = k

then return j

else i = i+ 1

until T [j] = NULL oppure i = m

return NIL

k

h(k, 0)

h(k, 1)

h(k, 2)

h(k, i)

x

y

z

T

j

return NIL


Cancellazione in una tabella hash con indirizzamento aperto

Non possiamo semplicemente cancellare un elemento in una tabella T sostituendo la suapresenza con un NIL, ció potrebbe disturbare successive ricerche. Supponiamo infatti divoler cercare la chiave k, che si trova nella locazione j = h(k, i).

k

h(k, 0)

h(k, 1)

h(k, 2)

h(k, i)

x

y

z

T

kj

In un tempo successivo, la chiave memorizzata nella locazione h(k, 2) (che al tempodell’inserimento di k era occupata, perció k era stata inserita in h(k, i)) é stata cancellata.

k

h(k, 0)

h(k, 1)

h(k, 2)

h(k, i)

x

y

T

kj

Quando poi andiamo a cercare k, nella sequenza delle h(k, 0), h(k, 1), . . . , troviamo NIL inh(k, 2) e concluderemmo che k non c’é nella tabella, commettendo un errore!


Come rimediare al problema?

• Potremmo inserire dei puntatori, ma la tecnica dell’indirizzamentoaperto vuole proprio fare a meno dei puntatori...

• Potremmo effettuare le cancellazioni non inserendo NIL al postodell’elemento cancellato, ma bensí inserendo uno speciale simbolo DEL.

• In questo modo, la funzione HASH-SEARCH(T, k) continuerebbe adesaminare la tabella T ogni qualvolta incontra o una locazione occupatada una chiave diversa da k, oppure se incontra una locazione con ilsimbolo DEL, fin quando o non trova k (e restituisce l’indice di talelocazione), oppure trova un NIL (e correttamente segnala la nonpresenza di k nella tabella)

• Ció risolve il problema, ma fa degradare le performances della tabella, inquanto le sue locazioni sarebbero ora occupate sia da elementi che davecchie cancellazioni. In generale, quando si richiede di effettuare ancheoperazioni di cancellazioni, si preferisce usare la tecnica dellaconcatenazione vista prima.


Come calcolare in pratica i valori h(k, 0), h(k, 1), . . .?

Ci sono tre tecniche che vengono generalmente usate per calcolare lesequenze di valori h(k, 0), h(k, 1), . . . usate nell’hashing medianteindirizzamento aperto:

1. Probing lineare

2. Probing quadratico

3. Doppio hashing

Queste tecniche garantiscono che la sequenza dei valorih(k, 0), h(k, 1), . . . , h(k,m− 1) sia una permutazione degli interi0, 1, . . . ,m− 1. Ció é necessario, affinché tutte le locazioni della tabella T

vengano prima o poi prese in considerazione nella fase di inserzione o rdiricerca di un elemento.


Probing Lineare

Data una funzione h′ : U → {0, 1, . . . ,m− 1}, il probing lineare usa lafunzione di hash h(k, i) = (h′(k) + i) (mod m) per i = 0, 1, . . . ,m− 1.

Quindi, data la chiave k, la prima locazione della tabella T che viemeconsiderata é T [h′(k)], poi viene considerata T [h′(k) + 1], poi vieneconsiderata T [h′(k) + 2], e cosí via..., fin quando non viene trovata unalocazione libera per inserire la chiave k


Esempio: Indirizzamento aperto e probing lineare

Assumiamo di avere una tabella di 16 elementi, e vogliamo mem-orizzarvi le chiavi k ∈ U , k = 1, 2, 17, 35, 3, 10, 27, 28, utiliz-zando la funzione hash h(k, i) = (h′(k) + i) mod 16, doveh′(k) = k mod 16, i = 0, 1, . . . , e risolvendo le collisioni me-diante la tecnica dell’indirizzamento aperto.

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

h(1, 0) = (h′(1) + 0) (mod 16) = 1 (mod 16) = 1

1

h(2, 0) = (h′(2) + 0) (mod 16) = 2 (mod 16) = 2

2

h(17, 0) = (h′(17) + 0) (mod 16) = 1 (mod 16) = 1, collisione!


h(17, 2) = (h′(17) + 2) (mod 16) = 3 (mod 16) = 3

17


h(35, 1) = (h′(35) + 1) (mod 16) = 4 (mod 16) = 4

35



h(3, 2) = (h′(3) + 2) (mod 16) = 5 (mod 16) = 5

3

h(10, 0) = (h′(10) + 0) (mod 16) = 10 (mod 16) = 10

10


Vantaggi e svantaggi del probing lineare

• É facile da implementare

• Tuttavia, due chiavi k, k′ che collidono per i = 0, ovvero per cuih(k, 0) = h(k′, 0) tenderanno a collidere anche per successivi valori di i,allungando i tempi di ricerca della locazione libera in cui memorizzarli.


Probing quadratico

Il probing quadratico usa funzioni hash della forma

h(k, i) = (h′(k) + c1i+ c2i2) (mod m)

dove h′ é una funzione di hash ausiliaria, c1, c2 6= 0 sono costantiausiliarie, e i = 0, 1, . . . ,m− 1, m é la taglia della tabella hash.

Quindi, data la chiave k, la prima locazione della tabella T che viemeconsiderata é T [h′(k)], poi viene considerata T [h′(k) + c1 + c2], poi vieneconsiderata T [h′(k) + 2c1 + 4c2], poi viene considerataT [h′(k) + 3c1 + 9c2], e cosí via..., fin quando non viene trovata unalocazione libera per inserire la chiave k.


Doppio hashing

Il metodo del doppio hashing viene considerato uno dei migliori metodidi hash disponibili, in quanto le permutazioni generate dah(k, 0), h(k, 1), . . . , h(k,m− 1) “somigliano” maggiormente allepermutazioni “casuali”, che distribuiscono unformemente le chiavi nellatabella hash. Tale metodo usa una funzione di hash della forma

h(k, i) = (h1(k) + i · h2(k)) (mod m)

dove h1 e h2 sono due funzioni di hash ausiliarie.Quindi, la prima locazione in cui si tenta di inserire la chiave k é T [h1(k)],poi si tenta di inserire in T [h1(k) + h2(k)], poi in T [h1(k) + 2 · h2(k)], e cosívia ..., fin quando o non si trova una locazione libera, oppure non sirealizza che la tabella T é completamente piena, nel qual caso si ritornaun messaggio di errore.

Nota : Affinché si possano esaminare tutte le locazioni della tabella T ,occorre che h2(k) debba essere relativamente primo con m.


Esercizio:

Usando il metodo del doppio hashing, memorizzare le chiavi 10, 18, 34in una tabella hash di taglia m = 8, usando le funzioni

h1(k) = k (mod 8), h2(k) = 1 + (k (mod 6))


Primo approccio (semplice): Indirizzamento Direttouv/IASD/hash.pdfIn una tabella di login di un...

Documents

Transcript of Primo approccio (semplice): Indirizzamento Direttouv/IASD/hash.pdfIn una tabella di login di un...