Hash table: differenze tra le versioni

Versione delle 16:51, 20 giu 2017

Versione delle 16:58, 20 giu 2017

Riga 3:

| image=HASHTB08.svg

| caption=Una piccola rubrica telefonica come esempio di hash table.

|data=Tabella Hash|optimal=Spesso|space=O(n)}}

| space=Dipende dalle implementazioni

| optimal=Spesso

}}

Riga 14 ⟶ 12:

Esistono vari tipi di algoritmi di hashing. Per quanto affermato, in una tabella di hashing ben dimensionata il costo medio di ricerca di ogni elemento è indipendente dal numero di elementi. L'hashing è un problema classico dell'informatica; molti algoritmi sono stati proposti, studiati a fondo e impiegati in pratica. Due metodi molto diffusi sono l'hashing statico e l'hashing estendibile e lineare, metodi utilizzati anche dai programmi [[DBMS]].

[[File:HASHTB08.svg|thumb|upright=1.6|Una piccola rubrica telefonica come esempio di hash table.]]

==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: