Cos'è un hashtable?

Nell'informatica, un hashtable è una struttura di dati per l'archiviazione di dati che consiste in un elenco di valori, chiamati tasti, che vengono accoppiati con un corrispondente elenco di valori, chiamato array.Ad esempio, un nome commerciale potrebbe essere abbinato al suo indirizzo.In genere, ogni valore nell'array ha un numero di posizione indicato come hash.La funzione hash è generalmente un insieme di istruzioni o un algoritmo che mappa ogni valore chiave per un hash mdash;Collegamento del nome aziendale al suo indirizzo, al suo numero di telefono e alla sua categoria aziendale, ad esempio.Lo scopo della funzione hash è assegnare ciascuna chiave a un valore corrispondente univoco nell'array;Questo è comunemente indicato come hashing.Le funzioni di hash devono essere correttamente formattate per un hashtable per funzionare correttamente.

Le prestazioni di un hashtable da un insieme di dati dipendono dall'efficienza della sua funzione hash.Una buona funzione di hash prevede in genere una ricerca uniforme delle chiavi e una distribuzione uniforme delle mappature nell'array corrispondente.Una collisione hash si verifica quando due chiavi sono assegnate allo stesso valore corrispondente.Quando si verifica una collisione hash, la funzione hash viene generalmente eseguita di nuovo fino a quando non viene trovato un valore corrispondente unico;Ciò si traduce comunemente in tempi di hashing più lunghi.Sebbene il numero di chiavi in un hashtable sia generalmente fisso, a volte potrebbero esserci chiavi duplicate.Anche così, un hashtable ben progettato ha funzioni di hash efficaci che mappano ogni chiave su un valore corrispondente univoco nell'array.

A volte, le funzioni di hash inefficienti in un hashtable possono anche produrre un cluster di mappature.Se una funzione hash crea un cluster di mappature per le chiavi esistenti, ciò può aumentare la quantità di tempo necessaria per cercare i valori corrispondenti.Questo può rallentare lo hashing per le chiavi future poiché la maggior parte delle funzioni hash generalmente cerca la prossima posizione disponibile nell'array.Se è già stato assegnato un grande cluster di valori, in genere richiederebbe molto più tempo a cercare un valore non assegnato per una nuova chiave.

Il fattore di carico è un altro concetto correlato all'efficienza di una funzione hash;Il fattore di carico è la quantità di hashing già esistenti in relazione alla dimensione complessiva dell'array corrispondente in un hashtable.Di solito è definito dividendo il numero di chiavi già assegnate per le dimensioni dell'array corrispondente.All'aumentare del fattore di carico, una buona funzione di hash normalmente manterrà comunque un numero costante di collisioni e cluster fino a un certo punto.Spesso questa soglia può essere utilizzata per determinare quanto sia efficiente una funzione hash con un determinato numero di chiavi e quando potrebbe essere necessaria una nuova funzione di hash.

Molti ricercatori di informatica hanno cercato di produrre la perfetta funzione hash mdash;uno che non produce collisioni o cluster dati un fattore di carico crescente.In teoria, la chiave per produrre un hashtable perfetto è produrre una perfetta funzione di hash.In generale, i ricercatori ritengono che una perfetta funzione di hash dovrebbe avere prestazioni costanti e mdash;il numero di collisioni e cluster mdash;con un fattore di carico crescente.Nel peggiore dei casi, una funzione hash perfetta consentirebbe comunque di hashing costante senza raggiungere una soglia.