Hash table: differenze tra le versioni

Versione delle 00:32, 11 mar 2011

Versione delle 15:43, 14 mar 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]].

Può usare qualsiasi tipo di dato come indice e tutte le operazioni si possono fare in tempo circa costante T(n) = ([[notazione O grande|O]](1)).

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