Please enable JavaScript.
Coggle requires JavaScript to display documents.
Tecnica Hash memoria secondaria - Coggle Diagram
Tecnica Hash
memoria secondaria
pro e contro
pro
le prestazioni legate alla ricerca casuale sono migliori di quelle della ricerca sugli alberi
quando ordinamenti e ricerche di rango non sono frequenti,
la organizzazione hash è molto conveniente
contro
costo per ordinare le chiavi
le ricerche di rango sono quasi impossibili
staticità
bisogna cercare metodi per permettere alla struttura di crescere senza prefissare dimensione massima
Hash Statico
uso hash per determinare pagina in cui va a finire il record con la chiave cercata
fino a che la pagina non è piena,
non si pone il problema dei sinomini
quando la pagina è piena:
overflow
catena di pagine di overflow
...
complessità
caso pessimo O(N/B)
se le chiavi vengono distribuite in maniera uniforme
1/(1,25)
Hash Dinamico
funzione trasforma chiavi in un numero intero codificato in valori binari
prima viene allocata una sola pagina p e tutte le chiavi vengono inserite in p
quando p è piena, viene allocata una seconda pagina q e le chiavi in p vengono ridistribuite fra p e q usando la funzione
se la prima cifra è 0 la chiave va in p,
se la prima cifra è 1 va in q
ogni volta che si riempie una pagina la si divide valutando il bit successivo
ricorda un Trie
albero con elementi neutri
Hash Estendibile
(metodo con directory)
funzione trasforma chiavi in valori tra 0 e m-1
directory: array di 2^d puntatori a pagine
ogni chiave k è assegnata alla pagina riferita al puntatore che si trova nella locazione del vettore corrispondente al valore dei d bit più significativi di h(k)
d: Global depth
più piccolo valore per cui ogni pagina abbia al massimo B elementi
si aumenta quando la condizione non è più soddisfatta
c: local depth
se due o più locazioni hanno complessivamente meno di B chiavi, possono far riferimento alla stessa pagina
c viene scelto come il valore (0<=c<=d) più piccolo possibile tale che gli elementi raggruppati entrino in una sola pagina
la forma della tabella non dipende dall'ordine in cui inserisco le chiavi
In overflow, modifico solo la pagina che ha causato l'overflow
Cancellazione
in maniera simile all'inserimento
conviene fondere due blocchi quando la soma è inferiore a B in maniera considerevole
se inizio a fare tanti cancellazioni,
potrei anche dimezzare d
Problemi
Se ci sono + di B elementi con la stessa chiave
Oppure più di B sinonimi rispetto alla funzione h
Costi
n° atteso pagine richieste per memorizzare N elementi è asintoticamente pari a n/ln2
n° atteso componenti directory e/ln2 N^1/B N/B
la directory è un array di link
se entra in RAM T(N,M,B)=1
se è troppo grande posso aggiungere un livello
T(N,M,B)=2
Metodi Senza
Directory
Hash Virtuale
funzione h va d N a {0,...,m-1}
inizialmente le chiavi vengono inserite nelle d pagine usando la funzione h0(k)=h(k)mod d
d usualmente numero primo molto piccolo
overflow -> re hash delle chiavi con h1(k)= h(k) mod 2d
si raddoppiano le pagine
si usa h1 solo per le chiavi che con h0sarebbero andate a creare overflow
Problemi
rehash una sola pagina
FATTORE DI CARICAMENTO
il rehash potrebbe portare
tutti gli el di una pagina sempre
in una pagina unica
Costi
Bitmap 1
fattore di caricamento che passa dal 70 al 35% ad ogni raddoppio
Hash lineare
quando si deve fare il raddoppio, invece di applicare h alla pagina da dividere, si applica alla pagina 0
aggiungo all archivio solo la pagina d
successivamente la pagina 1,2 , ecc
quando tutte le pagine sono state divise, si incrementa di 1 il valore di d e si riporta p=0
le chiavi che provocano le divisioni devono comunque essere inserite: è necessario prevedere delle pagine di overflow
una distribuzione uniforme delle chiavi porta ad un accumulo di chiavi in overflow per le ultime pagine dell'archivio coinvolte in un ciclo