Che cos'è un hashtable?
Nell'informatica, una tabella hash è una struttura di dati per la memorizzazione di dati costituita da un elenco di valori, chiamati chiavi, che vengono accoppiati con un corrispondente elenco di valori, chiamato matrice. Ad esempio, un nome commerciale potrebbe essere associato al suo indirizzo. In genere, ogni valore nella matrice ha un numero di posizione indicato come hash. La funzione hash è generalmente un insieme di istruzioni o un algoritmo che associa ciascun valore chiave a un hash, ad esempio collegando il nome dell'azienda al suo indirizzo, il suo numero di telefono e la sua categoria aziendale. Lo scopo della funzione hash è assegnare ogni tasto a un valore univoco corrispondente nell'array; questo è comunemente indicato come hashing. Le funzioni hash devono essere formattate correttamente affinché una tabella hash funzioni correttamente.
Le prestazioni di una tabella hash su un set di dati dipendono dall'efficienza della sua funzione hash. Una buona funzione hash fornisce in genere una ricerca uniforme dei tasti e una distribuzione uniforme dei mapping nell'array corrispondente. Una collisione hash si verifica quando due chiavi vengono assegnate allo stesso valore corrispondente. Quando si verifica una collisione hash, la funzione hash viene di solito eseguita nuovamente fino a quando non viene trovato un valore corrispondente univoco; questo di solito comporta tempi di hashing più lunghi. Sebbene il numero di chiavi in una tabella hash sia di solito fisso, a volte potrebbero esserci chiavi duplicate. Anche così, una tabella hash ben progettata ha funzioni hash efficaci che associano ogni chiave a un valore corrispondente univoco nell'array.
A volte, funzioni di hash inefficienti in una tabella di hash possono anche produrre un cluster di mappature. Se una funzione hash crea un cluster di mapping per chiavi esistenti, ciò può aumentare il tempo necessario per la ricerca dei valori corrispondenti. Questo può rallentare l'hash delle chiavi future poiché la maggior parte delle funzioni di hash generalmente cerca la prossima posizione disponibile nell'array. Se è già stato assegnato un grande cluster di valori, in genere occorrerebbe molto più tempo per 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 hash già esistenti in relazione alla dimensione complessiva dell'array corrispondente in una tabella hash. Di solito viene definito dividendo il numero di chiavi già assegnate per la dimensione dell'array corrispondente. All'aumentare del fattore di carico, una buona funzione di hash manterrà normalmente un numero costante di collisioni e cluster fino a un certo punto. Spesso questa soglia può essere utilizzata per determinare l'efficienza di una funzione hash con un determinato numero di tasti e quando può essere necessaria una nuova funzione hash.
Molti ricercatori di informatica hanno cercato di produrre la funzione hash perfetta, una che non produce collisioni o cluster dato un fattore di carico crescente. In teoria, la chiave per produrre una hashtable perfetta è produrre una funzione hash perfetta. In generale, i ricercatori ritengono che una perfetta funzione di hash dovrebbe avere prestazioni costanti - il numero di collisioni e cluster - con un fattore di carico crescente. Negli scenari peggiori, una funzione hash perfetta consentirebbe comunque un hash costante senza raggiungere una soglia.