|
|
La realizzazione di un dizionario con tabelle hash si basa sul concetto di ricavare direttamente dal valore della chiave la posizione della chiave stessa. Oltre ad una buona funzione hash H(k) che mi restituirà il valore della posizione della chiave nel dizionario, occorre un metodo di scansione che permetta di posizionare e reperire le chiavi che hanno trovato la propria posizione occupata ( le collisioni inevitabili). I metodi di scansione si distinguono in esterni e interni, a seconda che le chiavi siano memorizzate all’esterno o all’interno del vettore D contenente il dizionario.
Metodi esterni: liste di trabocco
Metodi interni: scansione: lineare, quadratica, pseudocasuale, hashing doppio
In generale i metodi esterni sono più efficienti di quelli interni.
Scansione esterna, liste di trabocco
La lista di trabocco è un metodo di scansione interno. L’ idea è quella di associare ad ogni posizione H(k) del dizionario una lista V[H(k)], detta appunto di trabocco. Le liste di trabocco hanno un duplice vantaggio, ovvero nessun limite alla capacità del dizionario ed evitare completamente degli agglomerati di chiavi.
Scansione interna
Scansione interna significa, in caso di collisione, scandire le posizioni libere in D per trovarne una libera per la chiave k Supponiamo che sia Fi la funzione che permette di trovare, con l’i-esima applicazione, l’i-esima posizione occupata partendo da H(k). In sostanza i sta ad indicare il numero di volte che si verifica una collisione, per uno stesso indirizzo del vettore D, ottenuto dalla funzione hash.
Scansione lineare:Fi = ( H(k) + h i ) mod m, dove h è primo con m, ed indica la distanza tra due successive posizioni esaminate nella scansione. Se h=1 si ottiene la scansione a passo unitario. La divisione in modulo rende la scansione circolare;
Scansione quadratica: Fi = ( H(k) + h i + i(i -1)/2 ) mod m, con m primo;
Scansione pseudocasuale: Fi = ( H(k) + ri ) mod m, con ri generato in modo pseudocasuale tra 0 e m-1;
Scansione hashing doppio: Fi = ( H(k) + i F(k) ) mod m, con F(k) altra funzione hash diversa da H(k).
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.