Tecniche di hashing dinamico e difetti dell'hashing

Il vettore di bit può essere rappresentato in memoria principale con un numero intero. Presa ad

esempio la pagina 420, verifico che B(420) è pari a 1 in RAM e se si accedo al disco. Essendo

operazioni in RAM il loro costo è pari a 0, quindi il costo della ricerca è pari ad 1 accesso solo

sul disco. Il costo dell'inserimento quando non c'è un trabocco costa 2 accessi, uno per trovare la

posizione ed 1 per scrivere la tupla, con trabocco si allocano pagine nuove e si ristribuisce la

pagina quindi faccio 3 accessi al disco.

Legge che regola il funzionamento dei moduli:

K mod M = 0,

K mod 2M = { (K mod M ) + M

Regola

Le funzioni di ricerca ed inserimento devono essere accoppiate altrimenti non funziona

l'hashing virtuale!

Se dovessi invece aumentare non a , ma a M+1 dovrei ridistribuire tutte le pagine e non

2 × M

solo quella dove accade il trabocco, inoltre la ricerca sarebbe peggiore. Il raddoppiare le pagine è

il motivo per cui si chiama hashing virtuale, in quanto il raddoppio non è sostenibile, infatti 20

trabocchi portano ad avere pagine sparsissime e questo non va bene. Una soluzione a ciò è

20

2

l'hashing lineare che ha crescita lineare e non esponenziale.

Tecnica di hashing lineare a crescita lineare

L'idea è di tenere traccia dell'indice della pagina non ancora ridistribuita più a sinistra.

p

Supponiamo di essere nella situazione seguente:

2 / 6

Tecniche di hashing dinamico e difetti dell'hashing

e di voler inserire la tupla 11.

Data la funzione ho che il è pari a 2, ma la pagina 2 è piena quindi si

H (K) = K mod M

0

verifica il primo trabocco. La pagina non è puntata da quindi creo una lista di trabocco dove

p

metto la tupla traboccata, dopodiché aggiorno la funzione di hash a ed

H (K) = K mod 2M

1

aggiungo una pagina. Infine prendo la pagina puntata da la ridistribuisco secondo la nuova

p

funzione di hash ed aumento il valore di . Nel caso in cui la pagina che trabocca è puntata da

p p

aggiungo subito una pagina e ridistribuisco la pagina che trabocca secondo la funzione hash

ed aumento il valore di .

H (K) p

1

Il resto può avere o il valore di prima oppure il valore di prima più M. Cosa succede se la

pagina di reindirizzamento non esiste? Non può succedere, perché ridistribuiamo la pagina più

a sinistra puntata da e questa pagina restituisce l'indirizzo vecchio oppure, quello della

p

pagina appena creata e non può dare altri valori, perché è una proprietà dell'algebra modulare.

Quando si cerca un valore si usa la funzione attuale assieme al valore da confrontare

p + M − 1

con il resto dato dalla funzione di hashing. Supponiamo di cercare la tupla 4, il risultato della

funzione hash è 4 (in quanto 4 mod 6 fa 4), ma la pagina 4 non esiste e questo significa che non è

stata ancora ridistribuita la pagina corrispondente alla pagina 4. Passo quindi alla funzione hash

precedente.

Quando accede un trabocco su una pagina non puntata da , se la pagina puntata da ha una lista

p p

di trabocco allora nella ridistribuzione anch'essa verrà contata.

Perciò le liste di trabocco hanno vita breve, in particolare se avvengono molti trabocchi le liste di

trabocco verranno cancellate dopo poco tempo e se non ci sono molti trabocchi, allora le

prestazioni non calano.

Quando =M, la struttura si resetta quindi M=2M, =0 e si passa a . Ogni

p p H (K) = K mod M

0

M trabocchi raddoppio l'argomento per questo si ha crescita lineare e non esponenziale.

3 / 6

Tecniche di hashing dinamico e difetti dell'hashing

Hashing estendibile

Questa tecnica non usa l'algebra modulare, prende la chiave K ed usa la codifica binaria. Quindi

distribuisce la tuple sulla base della codifica binaria della loro chiave. Per chiave non si intende

la chiave primaria ma la chiave di ricerca. Ogni pagina è associata ad un numero che è pari al

′

p

numero di trabocchi che ne ha determinato l'esistenza,tramite tengono traccia del numero di

p

trabocchi totali.

All'inizio ho una pagina ed un vettore chiamato indice. L'indice dice dove sono le tuple che

hanno la caratteristica della celletta, ossia di avere gli ultimi bit pari a quelli specificati.

x

All'inizio , perciò tutte le tuple finiscono nella prima pagina.

x = 0

Supponendo di avere pagine che con dimensione pari a 2 tuple, dopo aver memorizzato la tupla 1

e 2, quando arriva la tupla 3 avviene un trabocco ed aggiorno . A questo punto spezzo in due la

p

prima pagina per ottenerne 2. Le pagine avranno come valore di , il valore non più 0 ma quello

′

p

precedente aumentato di 1. Infine raddoppio l'indice per distinguere le tuple dove la chiave

termina con bit 0 e dove termina con bit 1.

Dopo tutto questo, ridistribuisco le tuple della pagina che ha traboccato assieme alla tupla che ha

generato il trabocco, secondo l'indice quindi ultimo bit 0 ed ultimo bit 1.

Supponiamo di trovarci nella seguente situazione:

e di voler aggiungere la tupla 5. In questo caso si crea un trabocco, perciò andrò a spezzare a

metà la pagina traboccata aggiornerò il loro e raddoppierò l'indice. In sostanza passerò a questa

′

p 4 / 6

Tecniche di hashing dinamico e difetti dell'hashing

situazione:

Per essere precisi indica il numero di volte che si raddoppia l'area indice.

p

La tecnica in risposta ad ogni trabocco, spezza la pagina traboccata, se raddoppio la pagina

che ha traboccato vuol dire che il numero di pagine complessivo è aumentato di 1. L'area

indice la raddoppio quando .

′

p = p

La tecnica si predispone bene anche per la contrazione delle pagine. L'area indice è facile da

rappresentare inoltre questa tecnica si predispone bene anche a ridurre le pagine. Per

rappresentare efficientemene l'area indice si può usare un albero.

Difetti hashing

Nei database l'hashing non è efficace perché non supporta ricerche basate su chiavi diverse da

quelle usate nel'hashing stesso oppure le ricerche per range in quanto le tuple sono distrubuite

casualmente.

L'hashing è una tecnica di indicizzazione di tipo primario, cioè oltre a tenere traccia di dove si

trovano le tuple anche il dove collocarle, ciò limita il come tenere le pagine ordinate rispetto una

caratteristica che viene chiamata partizionamento orizzontale.

5 / 6