Che cosa è un Hashtable?

In informatica, una tabella hash è una struttura dati per memorizzare dati che consiste in un elenco di valori, detti tasti, che vengono accoppiati con una corrispondente elenco di valori, chiamato un array. Ad esempio, un nome commerciale potrebbe ottenere accoppiato con il suo indirizzo. Tipicamente, ogni valore nella matrice ha un numero di posizione indicato come un hash. La funzione di hash è generalmente un insieme di istruzioni o di un algoritmo che associa ogni valore chiave per una hash - che collega il nome di business per l'indirizzo, il numero di telefono e la sua categoria di business, per esempio. Lo scopo della funzione di hash è assegnare ogni tasto ad un corrispondente valore univoco nella matrice; questo è comunemente indicato come hashing. Le funzioni hash devono essere adeguatamente formattati per una tabella hash per funzionare correttamente.

Le prestazioni di una tabella hash su un insieme di dati dipende l'efficienza della sua funzione hash. Una funzione hash buona fornisce tipicamente per una ricerca uniforme delle chiavi e una distribuzione uniforme del mappature nell'array corrispondente. Una collisione hash si verifica quando due tasti vengono assegnati allo stesso valore corrispondente. Quando si verifica una collisione hash, la funzione di hash viene solitamente eseguito di nuovo fino a un valore corrispondente unica si trova; questo comunemente si traduce in tempi più hashing. Anche se il numero di chiavi in ​​una tabella hash è di solito fissato, a volte ci possono essere chiavi duplicate. Anche così, una tabella hash ben progettato ha funzioni hash efficaci che mappano ogni chiave di un corrispondente valore unico nella matrice.

A volte, funzioni hash inefficienti in una tabella hash possono anche produrre un gruppo di mapping. Se una funzione hash crea un cluster di mappature per chiavi esistenti, questo può aumentare la quantità di tempo necessario per ricercare i valori corrispondenti. Questo può rallentare l'hashing per le chiavi future poiché la maggior parte funzioni hash generalmente cercano la successiva posizione disponibile nella matrice. Se un grande cluster di valori è già stato assegnato, che in genere vorrebbe molto più tempo per cercare un valore non assegnato per una nuova chiave.

Il coefficiente di riempimento è un altro concetto legato all'efficienza di una funzione hash; il fattore di carico è la quantità di hashings già esistenti in rapporto alle dimensioni complessive del corrispondente matrice in una tabella hash. Di solito è definito dividendo il numero di tasti già assegnati dalla dimensione della matrice corrispondente. Poiché il fattore di carico aumenta, una buona funzione hash normalmente ancora mantenere un numero costante di collisioni e cluster fino ad un certo punto. Spesso questa soglia può essere utilizzato per determinare come efficace una funzione hash è con un certo numero di chiavi e quando una nuova funzione hash può essere necessaria.

Molti ricercatori di informatica hanno cercato di produrre la funzione di hash perfetta - uno 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 di 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. Nel peggiore dei casi, una funzione di hash perfetta consentirebbe ancora di costante hashing senza raggiungere una soglia.

  • Una tabella hash è una struttura dati per memorizzare dati che consiste in un elenco di valori, detti tasti, che vengono accoppiati con una corrispondente elenco di valori, chiamato un array.