hash 1

METODIDI

ACCESSO(HASH)

hash 2

Nelle lezioni precedenti• Avete visto:– le caratteristiche delle principali unità

di memoria permanente– la struttura dei files– il loro ordinamento

In questa lezione• Presenteremo:– le caratteristiche principali dei metodi

hash per l’accesso alle tuple (record)

hash 3

organizzazioni hash• IDEA DI BASE : associare ad un

file di NB blocchi una funzione che trasformi un valore di chiave ki in un numero di blocco bi tra 1 ed NB– una tupla viene memorizzata nel

blocco bi– ad ogni blocco è associato un

indirizzo nel DASD– un blocco puo' contenere 1 o più

tuple

hash 4

organizzazioni hashLa regola con cui ad una chiave k viene associato unnumero di blocco b si chiama funzione hash oalgoritmo di hashing.

tupla : < chiave, informazione>

HASH (chiave) = b

b-1 b b+1

hash 5

organizzazioni hashIl file è ben utilizzato se:• ci sono pochi spazi vuoti, cioè se il fattore di

"packing”(caricamento) è' elevato:Fp = m/M <1, dove:

M = numero massimo di record per blocco, m = numero medio di record per blocco

• l’occupazione effettiva dei blocchi è vicina alla media

Fp basso sta a significare che il file è vuoto,Fp vicino ad 1 da significare che molti blocchisono pieni. Con i blocchi pieni si creano problemi

di OVERFLOW

hash 6

organizzazioni hashQuando un blocco (es. bj) è pieno ed una nuova tupla deve essere inserita poiché FH (f. hash) gli ha assegnato quel blocco (bj) allora si deve creare una lista (catena) di overflow.

File overflow

bj bk bn

FH

bj bk

bj

bk

bk

tupla itupla e

tupla i tupla e

o 1 o 2

hash 7

organizzazioni hashL'OVERFLOW avviene per due motivi:• ci sono più tuple con lo stesso valore di chiave

per cui FH le manda nello stesso blocco• FH non è perfetta ed assegna a due o più

valori di chiave diversi lo stesso blocco del file (collisione)

con lunghe liste di overflow si degrada l'efficienzaFH deve distribuire le tuple il più uniformementepossibile nei blocchi. Osserviamo che:• più piccolo è il blocco rispetto alle tuple più è

alto Fp ma più probabile è l'overflow,• più grande è il blocco rispetto alle tuple più è

basso Fp ma è meno probabile l'overflow.

hash 8

metodi per la funzione Hash1) MID-SQUARE:• La chiave (convertita in numero se

alfanumerica) è moltiplicata per se stessa ed i numeri centrali del quadrato vengono presi e normalizzati per rientrare nel "range" NB del numero di blocchi del file.

• ES: se un record ha una chiave di 6 cifre ed il file ha NB=7000 blocchi, il quadrato ha 12 cifre e si prendono le quattro dalla 5a alla 8a, se il numero è 172148, il quadrato è 029634933904 e le cifre centrali sono 3493.

hash 9

metodi per la funzione Hash• Per evitare che il numero così ottenuto sia

maggiore di 7000, lo si normalizza moltiplicandolo per 7000/10000, cioè il numero del blocco che risulta è 0.7 x 3493 = 2445.

• I due numeri immediatamente precedenti e successivi danno:172146 ⇒ 3224 ⇒ 2397172147 ⇒ 3450 ⇒ 2415172149 ⇒ 3527 ⇒ 2469172150 ⇒ 3562 ⇒ 2493

• Due valori successivi danno lo stesso blocco !

hash 10

metodi per la funzione Hash2) DIVISIONE• La chiave K viene divisa per il numero primo

più vicino ad NB ed il resto viene preso come numero del blocco

Es. 172148 viene diviso per 6997 (numero primo più vicino < NB) ed il resto è 4220

172146 ⇒ 4218172147 ⇒ 4219172149 ⇒ 4221172150 ⇒ 4222

• Il metodo della divisione non è un "randomizzatore", ma assegna valori successivi di K a blocchi successivi.

hash 11

metodi per la funzione Hash3) SHIFTING• Le cifre della chiave K vengono divise in due (o

più) gruppi, vengono spostate in modo da sovrapporsi per un numero di cifre pari al numero di cifre che rappresentano NB blocchi, i frammenti di K vengono sommati ed il risultato viene normalizzato.

8 cifre ⇒ 4 cifre per NB

Es: : 17207329 ⇒ 1720 | 7359 ⇒ 1720 +7359 =9079

hash 12

metodi per la funzione Hash4) FOLDING• I frammenti vengono "ripiegati" (fold) su se stessi e

poi sommati, le cifre in eccesso vengono eliminate• ES.: 17207329 ⇒ 17 | 207 | 329

SHIFTING e FOLDING vengono generalmente adoperatiper chiavi alfa- numeriche molto lunghe

8 cifre ⇒ 3 cifre207 +923 +717 =

1847 ⇒ 847

hash 13

metodi per la funzione Hash• Esempio: sequenza di 22 registrazioni di cui si

evidenzia solo la chiave, da memorizzare in un archivio di 13 blocchi la cui capacità è 2.

• funzione hash: i caratteri della chiave vengono convertiti in numeri prendendo i primi 4 bit della codifica BCD, successivamente se la stringa numerica così ottenuta è più lunga di 5 la si spezza in gruppi di 5 a partire da sinistra e poi si sommano i gruppi, infine si divide il numero per 13 e si prende il resto della divisione.

hash 14

• DATI NUMERO RESTO (mod 13)• 1 LUISA 34921 4• 2 EDVIGE 54602 3• 3 ADELE 14535 2• 4 AGNESE 17557 8• 5 FRANCESCA 74384 12• 6 ROBERTA 96290 13• 7 NOEMI 56549 13 • 8 ELENA 53551 5• 9 LAURA 31491 6 • 10 BEATRICE 26074 10 • 11 DIANA 49151 12• 12 IRENE 99555 2 • 13 PAOLA 71631 2• 14 BERENICE 26890 7• 15 VANESSA 51573 3• 16 SARA 02191 8 • 17 CARLA 31931 10 • 18 OLGA 06371 2• 19 GIORGIA 79788 8• 20 LARA 03191 7• 21 CAROLA 31964 11• 22 GIOVANNA 80202 6

hash 15

indirizzo ARCHIVIO puntatore• 1• 2 ADELE IRENE 14• 3 EDVIGE VANESSA• 4 LUISA• 5 ELENA• 6 LAURA GIOVANNA• 7 BERENICE LARA• 8 AGNESE SARA 15• 9 • 10 BEATRICE CARLA• 11 CAROLA• 12 FRANCESCA DIANA• 13 ROBERTA NOEMI• 14 PAOLA OLGA overflow record• 15 GIORGIA overflow record

Come si può vedere i blocchi 1 e 9 non vengono riempiti, mentre 2 ed 8 vanno inoverflow.

hash 16

COSA VUOL DIRE "METODO MIGLIORE"?• Il metodo migliore è quello che distribuisce il più

uniformemente possibile le tuple, evitando di riempire troppo alcuni blocchi lasciandone vuoti altri. In generale bisogna fare esperimenti e poi eventualmente cambiare funzione Hash e/o il numero di blocchi NB.

• Il metodo Mid-square e quello che più si avvicina ad un generatore di valori random. Il metodo della divisione è in generale il migliore perché "distribuisce" meglio le tuple.

• Per un FILE HASH si devono definire un numero NB di blocchi che costituiscono la " PRIME AREA " e NO per la " OVERFLOW AREA

hash 17

overflow distribuito

FH

N blocchi overflow overflowN blocchi

hash 18

overflow distribuito• 1 blocco di overflow ogni N blocchi. Se non c’è

posto nel primo OB si carica la tupla nel successivo OB

• Questo metodo si attua quando il file system alloca al file molti cilindri di disco, allora per ogni cilindro di T tracce le prime T-1 contengono i blocchi del file e la T-esima contiene l’overflow . Ciò consente di cercare in overflow evitando il più possibile di spostare il pettine di lettura .

• Sinonimi blocco: bucket, paginatupla: record, n-pla

hash 19

prestazioni

hash 20

prestazioni

hash 21

prestazioni• Es.: 10000 tuple di 200 bytes con blocchi di

4096, capacità = 20usando le curve del grafico si ha che:

• caricamento del 100% overflow al 17%,NB= 10000/200= 500, NO = 85, tot.= 585Chash = 1 nel 83% dei casi ≥ 2 nel 17%

• caricamento del 70% overflow al 3%,NB= 10000/14=715, NO= 22, tot. = 737Chash = 1 nel 97% dei casi ≥ 2 nel 3%

hash 22

Metodo open addressing- Non ci sono blocchi di overflow.- I blocchi sono dimensionati con molta area vuota.- Se un blocco va in overflow il record viene messo

nel primo blocco successivo con area disponibile. (NB va in overflow in 1)

X Y Z K

x x

x x

y

yx

x x z

z y

k

4 record per blocco

hash 23

open addressing

• Prime area consecutive spill: il record viene posto nel blocco successivo

• Prime area skip spill: il record viene posto in un blocco a distanza prefissata.

• Non ci sono puntatori.• La ricerca di un record parte dal blocco

indirizzato da FH e poi segue in modo sequenziale fintanto che viene trovata una posizione vuota, se il record fosse stato presente sarebbe infatti stato posto nella prima posizione vuota disponibile.

hash 24

open addressing• Questo metodo poiché si basa sulla ricerca

dei records fintanto che non si trova un "vuoto" non può rendere "vuoti" i recordseliminati.

• I records eliminati vengono marcati come "non attivi" poiché servono alla ricerca dei successivi. I records marcati possono però venire utilizzati per accogliere nuovi recordsattivi. In conclusione ci sono 3 tipi di records: ATTIVI, NON ATTIVI, VUOTI

• Le prestazioni degradano per fattori di caricamento >60%

hash 25

Hash dinamicoLINEAR HASHING(1980)Scopi:• Contenimento dell'area di overflow • Crescita controllata del file• Riorganizzazione automatica

I metodi statici si fermano all’esaurimento dell’overflow , devono essere monitorati e ristrutturati in tempo aumentando NB e facendo il re-hash con un altro divisore o altra FH

hash 26

Linear Hashing, metodo:• ogni volta che un blocco (qualsiasi esso sia) va in

overflow–deposita il record in overflow–effettua un block-split (partizionamento di un

blocco).• non effettua il block-split per il blocco andato in

overflow, effettua automaticamente il block-split per il primo blocco (a partire dall’inizio del file) che non ha ancora subito un block-split! (Bj).

• acquisisce un nuovo blocco successivo all'ultimo nel file e ridistribuisce i records Bj (e del suo overflow) traBj ed il blocco appena acquisito.

hash 27

Linear hashing• Non può fare direttamente il block-split del

blocco andato in overflow (come nel B-tree) poiché dovrebbe in tal caso fare il re-hash del file, in quanto inserire un blocco vuol dire cambiare la numerazione

• i records in overflow vengono recuperati tutte le volte che si realizza un block split , risultati sperimentali riportano un overflowpraticamente nullo per fattori di caricamento del 50% e dell'ordine del 5% per fattori di caricamento del 75%.

hash 28

Linear hashing• ALGORITMO• Chiave del record : key (convertita in

numero)• Hash-range iniziale : M, meglio se primo.• Numero blocchi iniziali: M0← M, M1← M• I blocchi numerati da 0 ad M0-1 .• Funzione Hash H[key]: address ← key

mod(M0)• Split pointer: SP : numero del blocco del

prossimo split

hash 29

Begin {linear hashing}SP ← 0;Per ogni record : indirizzo ← H(key);if indirizzo >M1- 1 then indirizzo ← indirizzo - M0/2; {a}si inserisce il record; if record va in overflow allora

begin M1 ← M1 + 1; si acquisisce il nuovo blocco BM1-1;se M1>M0 allora SP ← 0, M0← 2 × M0;si effettua il re-hash dei record contenuti in

BSP e nell'overflow per BSP e si distribuiscono tra BSP e BM1-1 ;

SP ← SP+1end

end

hash 30

Linear hashing0 1 M0 - 1 M1 - 1

area di overflow

nuovo bloccoSP

ESEMPIO. M0=7 : resti a 77 → 0 , 14 → 0 , 28 → 0 , 21 → 0

0 1 6

hash 31

Linear hashingSupponiamo che avvenga un overflow (in questo caso M1>M0), allora M0 ←14,si fa il re-hash dei record nel blocco 0 con resto a 14: 7 → 7, 14 → 0, 28 → 0, 21 → 7

0 1 6 7

nuovoil test {a} fa in modo che non si alterino gli altri indirizzi:13 → 13 13-7 → 615 → 1 26 → 12 12-7 → 59 → 9 9-7 → 2

Facendo lo split ed il re-hash i valori delle key vengonomodificati, quindi quando raddoppio di nuovo M, il test{a} va fatto solo sui nuovi record e non sui vecchi che sono stati già modificati.

hash 32

extendible hashing• L'extendible hashing è un metodo di hash

dinamico che usa una struttura dati ausiliaria, fu proposto da Fagin (IBM) nel 79.

• Nello schema extendible hashing l'archivio è strutturato in due livelli : un indice e l'area daticomposta da NB blocchi.

• Si suppone che l'indice possa in generale essere contenuto in memoria centrale e che quindi influisca in modo poco rilevante sul tempo di accesso all'archivio.

hash 33

extendible hashing• L'indice è composto di coppie <valore, puntatore >:

• il valore è costituito da d bit, • il puntatore indirizza un blocco nell'area dati,• d è chiamato "profondità dell'indice", • l'indice è costituito da P = 2d puntatori che

puntano agli NB blocchi con P ≥ NB, • i puntatori non sono necessariamente tutti

distinti, ma se vi sono più puntatori allo stesso blocco essi sono 2q con q<d, in questo caso si dice che il blocco ha profondità locale d'=d-q.

• Poiché i valori sono sempre un numero p potenza di 2 non c’è bisogno di memorizzarli.

hash 34

000001010011100101110111

profondità: d= 3

INDICE d = 2

d = 3

d = 1

d = 3

....1

...110

...010

...00

AREA DATI

extendible hashing

hash 35

extendible hashing• La ricerca di un record di chiave K avviene in

due passi:1 K viene trasformata dalla funzione Hash

nella chiave hash H, si estrae da H un suffisso S (prefisso) costituito dai primi d bit a partire da destra (sinistra), con S si cerca nell'indice e si trova il valore corrispondente;

2 si estrae il puntatore, si accede al blocco indirizzato e si cerca il record con chiave K.

hash 36

extendible hashingInserimento di un record di chiave K:• si cerca il blocco dove inserirlo come nel caso

della ricerca, se il blocco è saturo si possono avere due casi:

1 il blocco ha una profondità locale d'<d, allora si acquisisce un nuovo blocco, si aumenta d'di 1, si distribuiscono i vecchi ed il nuovo record tra il vecchio ed il nuovo blocco sulla base della differenziazione creata dal nuovo bit del suffisso(0/1) e si aggiornano i puntatori che puntavano al vecchio blocco.

hash 37

000001010011100101110111

profondità':

INDICE d = 2

d = 3

d = 2

d = 3

...01

...110

...010

...00

...11d = 2

AREA DATI

d= 3

extendible hashing

hash 38

extendible hashing2 il blocco ha profondità d, allora si acquisisce

un nuovo blocco, si aumenta di 1 la profondità d dell'indice, si ridistribuiscono i vecchi ed il nuovo record sulla base della differenziazione creata dal nuovo bit del suffisso(0/1) e si ricostruisce l'indice raddoppiandolo (passa da 2 d-1 a 2d puntatori).

• In seguito a cancellazioni, in caso di svuotamento parziale o totale di blocchi, possono essere fusi due blocchi che si differenziano per l'ultimo bit del suffisso e l'indice può essere contratto.

hash 39

00000001001000110100010101100111

profondità: d= 4

INDICE d = 2

d = 4

d = 2

d = 3

...01

...110

..0010

...00

...11d = 2

AREA DATI

10001001101010111100110111101111 d = 4

..1010

raddoppio

extendible hashing

hash 40

extendible hashing: costruzione

d = 0

vuoto

d = 0S1

S1S2

S1= 00011110S2= 11010001capacità del blocco= 2

passo 0

passo 1

passo 2

hash 41

extendible hashing: costruzione

0d = 1

d = 1 1

S1S3

S2

01

S1S3

S2S4

d = 1

d = 1

S1= 00011110S2= 11010001S3= 00111100S4= 11000011

passo 3

passo 4

hash 42

extendible hashing: costruzioned = 2

0001

S3

S2S4

S1S5

d = 1

d = 2

S3

S2S6

S1S5

S4

d = 2

d = 2

d = 2

d = 2

S5= 11001010

S6= 11001001

passo 5

passo 6

1011

00011011