Hash table
tipo di struttura dati / Da Wikipedia, l'enciclopedia encyclopedia
Caro Wikiwand AI, Facciamo breve rispondendo semplicemente a queste domande chiave:
Puoi elencare i principali fatti e statistiche su Hash table?
Riassumi questo articolo per un bambino di 10 anni
In informatica una hash table o hash map, in italiano tabella hash o mappa hash, è una struttura dati usata per mettere in corrispondenza una data chiave con un dato valore. Viene usata per l'implementazione di strutture dati astratte associative come le mappe o i set.
Hash table | |
---|---|
Una piccola rubrica telefonica come esempio di hash table. | |
Classe | Struttura dati |
Struttura dati | Tabella Hash |
Caso peggiore spazialmente | O(n) |
Ottimale | Spesso |
È molto utilizzata nei metodi di ricerca nominati 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 di gestione delle basi di dati.