Hash table: differenze tra le versioni

Versione delle 11:05, 2 feb 2020

Versione delle 17:34, 11 lug 2020

Riga 8:

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

LE'hash table è molto utilizzata nei metodi di ricerca nominati Hashing. L''hashing'' èovvero 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]].