Hash table: differenze tra le versioni

Versione delle 06:39, 1 giu 2019

Versione delle 15:48, 9 lug 2019

Riga 14:

== Descrizione ==

=== Funzionamento e implementazione ===

Il primo passo per realizzare algoritmi di ricerca tramite hashing è quello di determinare la ''funzione di hash'': il dato da indicizzare viene trasformato da un'apposita [[funzione di [[hash]] in un intero compreso tra <math>0</math> ed <math>m-1</math> che viene utilizzato come indice in un [[array]] di lunghezza m. Supponendo che <math>U</math> sia l'universo delle chiavi e <math>T[0 ... m-1]</math> una tabella hash, una funzione hash h, stabilisce una corrispondenza tra <math>U</math> e le posizioni nella tabella hash, quindi:

<math>h:U \rightarrow \{0,1,...,m-1\}</math>

Idealmente, chiavi diverse dovrebbero essere trasformate in indirizzi differenti, ma poiché non esiste la funzione di [[hash]] ''perfetta'', ovvero totalmente [[iniettiva]], è possibile che due o più chiavi diverse siano convertite nello stesso indirizzo.

Il caso in cui la funzione hash applicata a due chiavi diverse genera un medesimo indirizzo viene chiamato '''collisione''' e può essere gestito in vari modi. La scelta di una buona funzione di hash è indispensabile per ridurre al minimo le collisioni e garantire prestazioni sempre ottimali. Il risultato migliore si ha con funzioni pseudo-casuali che distribuiscono i dati in input in modo uniforme.

Riga 59:

== Hashing statico ==

Nell'hashing statico si utilizza il concetto di bucket, che è l'insieme di pagine contenenti le etichette dei record di dati.

Se una pagina bucket primaria è piena, viene creata una pagina di overflow. Per cercare l'etichetta corrispondente alla chiave <math>k</math> (<math>M =</math> numero di bucket) si utilizza la seguente formula di [[hash]]

<math>h(k) = \mbox{bucket}</math> a cui appartiene l'etichetta.

La funzione di hash <math>h</math> agisce sul campo della chiave di ricerca del record <math>r</math> e deve distribuire i valori su <math>0,...,M-1</math> (<math>M</math> bucket). Le prestazioni della ricerca dipendono molto dalla funzione <math>h</math>.