Hash table: differenze tra le versioni

Versione delle 16:58, 20 giu 2017

Versione delle 13:08, 24 giu 2017

Riga 1:

{{Algoritmo

| classclasse = [[Struttura dati]]

| imageimmagine = HASHTB08.svg

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

|datastruttura dati = Tabella Hash|optimalottimale = Spesso|spacespazio = O(n)}}

{{F|programmazione|febbraio 2013}}

In [[informatica]] un''''hash table''', in italiano '''tabella hash''', è una [[struttura dati]] usata per mettere in corrispondenza una data ''chiave'' con un dato ''valore''. Viene usata per l'implementazione di [[Struttura dati#Strutture dati astratte|strutture dati astratte]] associative come Map o [[set (informatica)|Set]].

L'hash table è molto utilizzata nei metodi di ricerca nominati Hashing. L'hashing è un'estensione della ricerca indicizzata da chiavi che gestisce problemi di ricerca nei quali le chiavi di ricerca non presentano queste proprietà. Una ricerca basata su hashing è completamente diversa da una basata su confronti: invece di muoversi nella struttura data in funzione dell'esito dei confronti tra chiavi, si cerca di accedere agli elementi nella tabella in modo diretto tramite operazioni aritmetiche che trasformano le chiavi in indirizzi della tabella.

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]].

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]].

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

Riga 54:

Se facendo l'hash di una chiave si incontra una collisione, allora si somma all'indice ottenuto il risultato di una nuova funzione hash (generalmente diversa dalla prima e che ha come parametro l'indice ottenuto precedentemente), e si tenta l'inserimento nel nuovo indice così ottenuto, riapplicando la seconda funzione sino a che non si trovi una casella libera.

== Hashing statico ==

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

Riga 94:

==Analisi del costo di scansione==

Il numero di passi da effettuare per una scansione completa della tabella è data nel caso medio da:

Riga 117 ⟶ 116:

==Altri progetti==

{{Interprogetto|commons=Category:Hash tables}}