Hash table: differenze tra le versioni

Versione delle 09:44, 20 lug 2011

Versione delle 23:52, 22 ago 2011

Riga 1:

In [[informatica]] una '''hash table''', detta anche '''hash map''', 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 chedi 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. 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]].

[[Image:HASHTB08.svg|thumb|362px|right|Una piccola rubrica telefonica come esempio di hash table.]]