In informatica, una tabella hash è una struttura dati per l’archiviazione di dati che consiste in un elenco di valori, chiamati chiavi, che vengono accoppiati con un elenco di valori corrispondente, chiamato array. Ad esempio, il nome di un’attività potrebbe essere associato al suo indirizzo. In genere, ogni valore nell’array ha un numero di posizione denominato hash. La funzione hash è generalmente un insieme di istruzioni o un algoritmo che associa ogni valore chiave a un hash, ad esempio collegando il nome dell’attività al suo indirizzo, numero di telefono e categoria di attività. Lo scopo della funzione hash è assegnare ogni chiave a un valore corrispondente univoco 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 insieme di dati dipendono dall’efficienza della sua funzione hash. Una buona funzione di hash fornisce in genere una ricerca uniforme delle chiavi e una distribuzione uniforme delle mappature nell’array corrispondente. Una collisione di hash si verifica quando due chiavi sono assegnate allo stesso valore corrispondente. Quando si verifica una collisione di hash, la funzione di hash viene solitamente eseguita di nuovo finché non viene trovato un valore corrispondente univoco; questo generalmente si traduce in tempi di hashing più lunghi. Sebbene il numero di chiavi in una tabella hash sia generalmente fisso, a volte potrebbero esserci chiavi duplicate. Anche così, una tabella hash ben progettata ha funzioni hash efficaci che mappano ogni chiave a un valore corrispondente univoco nell’array.
A volte, le funzioni hash inefficienti in una tabella hash possono anche produrre un cluster di mappature. Se una funzione hash crea un cluster di mappature per le chiavi esistenti, questo può aumentare il tempo necessario per cercare i valori corrispondenti. Questo può rallentare l’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 gruppo di valori, in genere sarebbe necessario molto più tempo per cercare un valore non assegnato per una nuova chiave.
Il fattore di carico è un altro concetto legato 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 è 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 normalmente manterrà ancora 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 chiavi e quando potrebbe essere necessaria una nuova funzione hash.
Molti ricercatori di informatica si sono sforzati di produrre la funzione di hash perfetta, una che non produce collisioni o cluster dato un fattore di carico crescente. In teoria, la chiave per produrre una tabella hash perfetta è produrre una funzione hash perfetta. In generale, i ricercatori ritengono che una funzione di hash perfetta dovrebbe avere prestazioni costanti – il numero di collisioni e cluster – con un fattore di carico crescente. Negli scenari peggiori, una funzione di hash perfetta consentirebbe comunque l’hashing costante senza raggiungere una soglia.