Una hash table è un dizionario, ovvero una struttura dati dinamica che permette di gestire le tre principali operazioni sui dati: inserzione, cancellazione e ricerca.
Come funziona una hash table
L’obiettivo dell’utilizzo di una hash table è quello di cercare di eseguire le operazioni in tempo Θ(1). L’idea è quella di utilizzare una funzione matematica che associa il valore di un dato ad una corrispondente cella di memoria. Se volessimo ad esempio effettuare la ricerca di un elemento, dando in pasto il dato alla funzione, essa restituirà la posizione della cella dove è memorizzato. Tutto ciò quindi ci eviterebbe di effettuare costose ricerche.
Tuttavia, trovare una funzione hash perfetta per ogni dato da inserire non è assolutamente facile per via delle collisioni.
Le collisioni avvengono quando uno o più dati da inserire generano la stessa posizione in memoria di un altro valore già precedentemente inserito. Questo è uno dei motivi per cui le funzioni hash vanno scelte con cautala.
Una funzione di hashing che non genera collisioni è detta funzione di hashing perfetto, quindi che dato un insieme di chiavi K = {k1, k2,…,km-1} dove m è la dimensione del vettore, per ogni chiave ki, corrisponde al più una cella di memoria. Possiamo allora dire che l’hashing perfetto è una funzione iniettiva.
Dato che spesso le collisioni sono inevitabili, esistono modi di organizzare la memoria per gestirle meglio. Passiamo quindi a vedere in quali modi possiamo realizzare la struttura di una hash table.
Come è fatta una hash table
La struttura di una hash table va scelta a seconda dell’utilizzo che ne vogliamo fare. Ne esistono principalmente due, una è detta di tipo chaining e l’altra è detta di tipo open addressing. La prima viene solitamente utilizzata se c’è la necessità di modificare spesso i dati, quindi facendo numerose cancellazioni. La seconda invece si utilizza nel caso i dati non debbano essere modificati spesso.
Chaining
La hash table di tipo chaining risolve le collisioni creando un vettore di puntatori a lista. Con questa tecnica inseriamo ogni dato nella corrispondente cella, la quale sarà la testa di una lista. Se un dato genera un hash uguale ad un altro già inserito, andremo ad aggiungere un nuovo nodo a tale lista e memorizzeremo il dato al suo interno. Questo nuovo nodo diventerà la nuova testa della lista, mentre quella vecchia diventerà il secondo nodo.
Dalla figura vediamo rappresentato un universo U di chiavi, al suo interno abbiamo il sottoinsieme delle chiavi K utilizzabili con la nostra funzione hash e hash table. Notiamo ad esempio che k1 e k4 sono state inserite nella seconda cella perché i dati generano lo stesso valore di hashing, quindi una collisione.
La lista scelta è di tipo doubly linked per poterla scorrere più efficientemete, ma potremmo utilizzare anche una singly linked se volessimo, ciò però comporterebbe un aumento del costo dell’operazione di eleminazione della chiave dalla tabella.
Operazioni su hash table di tipo chaining
Passiamo adesso ad una dicussione sul costo delle operazioni, considerando di avere una hash table di tipo chaining che utilizza liste doubly linked.
L’operazione di inserimento in una hash table di tipo chaining in ogni caso richiede tempo Θ(1), dato che ogni volta che immettiamo un nuovo dato, andremo semplicemente ad inserire una nuova testa alla lista corrispondente.
L’operazione di ricerca è abbastanza sgradevole al caso pessimo, in quanto potrebbe capitare che tutte i dati da inserire generino lo stesso valore di hashing, e che quindi andranno ad inserirsi tutti in una sola lista. Supponendo di avere n dati, la ricerca al caso pessimo costa quindi Θ(n).
Al caso medio la ricerca costa circa la dimensione media della lista all’interno della tabella, più il costo per il calcolo della funzione di hashing.
Supponendo di avere n elementi e una hash table con un vettore di dimensione m, il costo vale Θ(1+α), dove α = n/m, α è detto fattore di carico, ovvero la dimensione media della lista.
La ricerca viene spesso distinta tra ricerca con successo o senza successo. La ricerca senza successo ha un costo leggermente più elevato, ma che comunque non supera l’ordine di quello della ricerca con successo.
Infine abbiamo l’operazione di eliminazione che costa al caso pessimo Θ(1). Questo perché solitamente si assume di conoscere già la posizione dell’elemento all’interno della lista, quindi basta rimuovere il nodo e collegare il suo predecessore con il suo successore attraverso i puntatori. Se il nodo lo dovessimo anche cercare, dovremmo considerare anche il costo della ricerca.
Open addressing
Con la struttura open addressing facciamo in modo che gli elementi inseriti occupino il vettore stesso, a differenza del chaining dove nel vettore memorizzavamo i puntatori a lista.
Intuitivamente con l’open addressing la cella corrispodente alla chiave k viene calcolata dando in pasto alla funzione hash la chiave k, più l’indice i del vettore. Quello che fa è calcolare il valore della cella finché non ne trova una vuota, partendo dall’indice i=0.
Nota bene, l’algoritmo non parte a scorrere il vettore dall’indice i=0 ma da h(k, i), dove inizialmente i=0 e dove h è la funzione hash. Da lì scorre il vettore ricalcolando la funzione con l’indice i+1.
Guardiamo per esempio come è fatto lo pseudocodice dell’algoritmo di ricerca e notiamo come ad ogni ciclo ricalcola la funzione hash con il nuovo indice:
Hash-Search(T, k):
i = 0
repeat:
j = h(k, i)
if T[j] == k
return j
i = i+1
until T[j] == NIL or i == m
return NILLa hash table per l’open addressing deve avere un fattore di carico α < 1, ovvero che il rapporto tra il numero degli elementi da inserire e la dimensione del vettore deve essere minore di 1. Quindi n/m < 1, ricordiamo che n è il numero di elementi è m la dimensione del vettore.
Funzioni hash per l’open addressing
La funzione hash per l’open addressing deve essere uniforme, ovvero che deve garantire che ogni chiave che vogliamo inserire nella tabella abbia la stessa probabilità di essere inserita in una cella di tutte le altre chiavi da inserire.
Più formalmente:
Dove Q(i) è la probabilità che una chiave finisca nella cella i e m è la grandezza del vettore della tabella.
La funzione hash deve quindi inoltre garantire che restituisca un risultato che rientri nel dominio {0,1,…,m-1}, altrimenti l’elemento non può essere inserito all’interno di una cella essendo un valore che non fa parte del vettore. Quindi:
Trovare una funzione hash adatta per l’open addressing non è assolutamente facile. Ci sono però tre funzioni che vengono solitamente utilizzate di cui una è la migliore.
Queste funzione si chiamano linear probing, quadratic probing e double hashing. Andiamo allora ad esaminarle una ad una e vediamo quale funziona meglio.
Linear probing
La funzione hash per il linear probing è definita nel seguente modo:
h(k, i) = (h'(k) + i) mod m
Questa funzione genera un valore appartenente ad un indice del vettore e poi l’algoritmo inserisce la chiave, se però la cella è occupata lo inizia scorre in maniera lineare, scorrendo le celle una ad una, due a due o tre a tre, ecc, a seconda dal valore di h'(k) finché non ne trova una vuota, quindi genererà una sequenza del tipo
T[h'(k) + 0], T[h'(k) + 1], …, T[h'(k) + m-1]
Il linear probing soffre quando abbiamo un numero considerevole di elementi perché man a mano che inseriamo le chiavi, il tempo di ricerca medio della cella aumenta fin troppo. Questo “handicap” si chiama primary clustering, ovvero agglomerazione primaria.
Infatti supponendo di aver occupato i celle, la probabiltà di inserire la chiave k è più bassa rispetto a quando tutte le celle sono libere, quindi l’algoritmo si dovrà occupare di scorrere il vettore finché non trova quella vuota e man a mano che si riempe la probabilità scende.
La probabilità quindi di una chiave di essere inserita equivale a (i+1)/m,
infatti a i=0 la probabità resta quella prevista, ovvero 1/m, mentre poi all’aumentare di i diminuisce.
Quadratric probing
La funzione hash per il quadratic probing è definita nel seguente modo:
h(k, i) = (h'(k) + c1i + c2i2 ) mod m
dove c1 e c2 sono valori costanti positivi, scelti in modo tale da assicurare di generare permutazioni per ogni cella, quindi comprese in {0, 1, …, m-1}.
Le ispezioni in questo caso non sono lineari come nel linear probing, ma l’offset, cioè la dimensione dello spostamento, dipende dal valore quadratico che assume i ad ogni ciclo.
Il qudratic probing funziona meglio del linear probing, però comunque soffre del secondary clustering, ovvero che quando due chiavi generano la stessa posizione iniziale, cioè h(k1, 0) = h(k2, 0), allora le loro sequenze di ispezione sono ad ogni ciclo identiche. Formalmente:
Double hashing
La funzione hash per il double hashing è definita nel seguente modo:
h(k, i) = ( h1(k) + ih2(k) ) mod m
Questa funzione è una delle migliori e tra le più utilizzate, perché riesce a generare permutazioni in maniera più casuale, garantendo una maggiore diversificazione nelle sequenze di probing.
h1 e h2 sono due funzioni scelte che prendono in input la chiave k.
Facciamo un esempio di inserimento nella tabella riprendentdo quello fatto nel libro CLRS (cap. 11, figura 11.5). Supponiamo di voler inserire la chiave k=14 in una tabella occupata già dalle chiavi di valore 79, 69, 98, 72, 50. La dimensione della tabella è m=13, la funzione h1(k) = k mod 13, mentre h2(k) = 1 + (k mod 11). Vediamo gli inserimenti.
h(14, 0) = ( (14 mod 13) + 0*(1 + (14 mod 11) ) mod 13 = 1
la cella 1 è occupata dal 79, andiamo avanti.
h(14, 1) = ( (14 mod 13) + 1*(1 + (14 mod 11) ) mod 13 = 5
la cella 5 è occupata dal 98, andiamo avanti.
h(14, 2) = ( (14 mod 13) + 2*(1 + (14 mod 11) ) mod 13 = 9
la cella 9 è vuota, inseriamo la chiave 14.
Complessità dell’open addressing
Una hash table open addressing, in caso di ricerca senza successo, la complessità viene calcolata considerando l’intersezione di tutte le probabilità di raggiungere ogni cella, non semplicemente la visita di ogni cella. Con una dimostrazione basata appunto sulla probabilità si conclude che la complessità è di 1/(1-α) (dim: CLRS 11.6).
Con la ricerca con successo è simile ma bisogna considerare inoltre che non è detto che si arrivi a visitare tutte le celle e si conclude allora che la complessità equivale a (1/α) ln( 1/(1-α) ) (dim: CLRS 11.8).
L’inserimento è simile alla ricerca, perché l’algoritmo dovrà cercare la cella e poi inserire la chiave. La complessità è allora asintoticamente equivalente alla ricerca: 1/(1-α).
L’eliminazione è di nuovo simile alla ricerca. Ricordiamo che per eliminare un elemento dall’open addressing non bisogna assegnare alla cella corrispondente il valore vuoto (NIL), perché altrimenti potrebbe interrompere le procedure di ricerca. Per questo è obbligatorio utilizzare un flag del tipo T[h(k, i)].deleted = true, per dire che tale elemento non occupa più la cella e quindi può essere rimpiazzato da un altro elemento.
Pseudocodici algoritmi open addressing
Concludiamo lasciando i codici degli algoritmi per l’open addressing. Abbiamo già anticipato precedentemente quello per la ricerca, ma adesso li raggruppiamo tutti in questa sezione:
--- RICERCA ---
Hash-Search(T, k):
i = 0
repeat:
j = h(k, i)
if T[j] == k
return j
i = i+1
until T[j] == NIL or i == m
return NIL
--- INSERIMENTO ---
Hash-Insert(T, k):
i = 0
repeat:
j = h(k, i)
if T[j] == NIL
T[j] = k
return j
else i = i+1
until i == m
error "hash table overflow"
--- ELIMINAZIONE ---
Hash-Delete(T, k):
i = 0
repeat:
j = h(k, i)
if T[j] == k
T[j].DEL = true
return j
else i = i+1
until T[j] == NIL or i == m