Hash table

Da Wikipedia, l'enciclopedia libera.

Una hash table è una struttura dati che viene usata per l'implementazione di strutture dati astratte associative come Map o Set. Può usare qualsiasi tipo di dato come indice e tutte le operazioni si possono fare in tempo circa costante (O(1)). L'hash table è molto utilizzata nei metodi di ricerca nominati Hashing. L'hashing è un'estensione della ricerca indicizzata da chiavi che gestisce problemi di ricerca nei quai le chiavi di ricerca non presentano queste proprietà. Una ricerca basata su hashing è completamente diversa da una basata su confronti: invece che spostarci nella struttura data in funzione dell'esito dei confronti tra chiavi, cerchiamo 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. 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 DBMS.

[modifica] Funzionamento e Implementazione

Il primo passo per realizzare algoritmi di ricerca tramite hashing è quello di determinare la funzione di hash: il dato da indicizzare viene trasformato da un'apposita funzione di hash in un intero compreso tra 0 ed n-1 che viene utilizzato come indice in un array di lunghezza n.Idealmente, chiavi diverse dovrebbero essere trasformate in indirizzi differenti, ma poiché non esiste la funzione di hash perfetta, è possibile che due o più chiavi diverse siano convertite nello stesso indirizzo. Il caso in cui due dati diversi hanno lo stesso valore di hash viene chiamato collisione e può essere gestito in vari modi. La scelta di una buona funzione di hash è indispensabile per ridurre al minimo le collisioni e garantire prestazioni sempre ottimali.Il risultato migliore si ha con funzioni pseudo-casuali che distribuiscono i dati in input in modo uniforme. Molto spesso però, una buona funzione di hash non può bastare, infatti le prestazioni di una hash table sono fortemente legate anche al cosiddetto fattore di carico (load factor) calcolato come Celle libere/Elementi presenti e che ci dice quanta probabilità ha un nuovo elemento di collidere con uno già presente nella tabella. Questa probabilità, in realtà, è più alta di quanto si possa pensare, come ci dimostra il paradosso del compleanno. È bene dunque mantenere il load factor il più basso possibile (di solito un valore di 0.75 è quello ottimale) per ridurre al minimo il numero di collisioni.Questo può essere fatto, ad esempio, ridimensionando l'array ogni volta che si supera il load factor desiderato.

[modifica] Gestione delle collisioni

Di seguito vengono riportati i metodi più diffusi per la gestione delle collisioni.

Scansione lineare: Quando viene incontrata una collisione non si fa altro che utilizzare l'indice successivo a quello che collide, sino a che non si trova una casella libera.
Scansione quadratica: Quando viene incontrata una collisione non si fa altro che utilizzare l'indice che collide elevato al quadrato con normalizzazione rispetto alla grandezza della tabella dell'indice ottenuto, sino a che non si trova una casella libera.
Hashing doppio: se facendo l'hash di una chiave si incontra una collisione, allora si somma all'indice ottenuto il risultato di una nuova funzione hash (generalmente diversa dalla prima e che ha come parametro l'indice ottenuto precedentemente), e si tenta l'inserimento nel nuovo indice cosi' ottenuto, riapplicando la seconda funzione sino a che non si trova una casella libera.
Concatenazione: per ogni cella della tabella di hash si fa corrispondere invece di un elemento, una Lista (solitamente una lista concatenata). In questo modo un elemento che collide viene aggiunto alla lista corrispondente all'indice ottenuto.

[modifica] Hashing Statico

Nell'hashing statico si utilizza il concetto di bucket, che è l'insieme di pagine contenenti le etichette dei record di dati. Se una pagina bucket primaria è piena viene creata una pagina di overflow. Per cercare l'etichetta corrispondente alla chiave k (M = numero di bucket) si utilizza la seguente formula di hash h(k) = bucket a cui appartiene l'etichetta. La funzione di hash h agisce sul campo della chiave di ricerca del record r e deve distribuire i valori su 0,...,M-1 (M bucket).

Esempio di funzione di hash h(chiave) = (a * chiave + b) mod M (dove a e b sono costanti) Le prestazioni della ricerca dipendono molto dalla funzione h.

Le pagine di bucket primarie, nell'hashing statico, sono allocate consecutivamente. Questo può portare ad avere il problema di lunghe catene di overflow che degradano le prestazioni dato che non abbiamo pagine contigue.

[modifica] Hashing Estendibile

Sostanzialmente è un miglioramento dell'hashing statico, perché oltre ad inserire bucket di overflow permette di raddoppiare il numero di bucket e di riorganizzare le etichette. L'unico problema sta nella riorganizzazione delle etichette, dato che questa operazione è costata in termini di tempo. Esistono due soluzioni. La prima (hashing estendibile) gestisce una directory di puntatori ai bucket primari, la seconda (hashing lineare) permette di risolvere il problema senza l'utilizzo delle directory ma con una famiglia di funzioni hash. Nell'hashing estendibile si parla di profondità di directory e si intende il numero minimo di bit che permette di rappresentare il numero di elementi contenuti nella directory.

[modifica] Hashing Lineare

L'hashing lineare, come accenato nel paragrafo precendente, permette di risolvere il problema delle lunghe catene di overflow senza l'utilizzo delle directory. L'idea di base è quella di utilizzara una famiglia di funzioni hash h0,h1,... hn dove hi ha un range che è la metà di quello di hi+1. Questo vuol dire che il range di h1 è 2^1 N Esempio Se N = 32 allora il numero minino di bit per la rappresentazione del numero è 5. Quindi h0 = h mod 2^0 N cioè h0 = h mod 32 La prossima funzione h2 avrà range 5 + 1 e potrà rapprensetare i bucket da 0 a 61. La funzione di hash sarà come segue h1 = h mod 2 ^ 1 * 32