Tecnica dell'Hashing Doppio

L'hashing doppio fa parte dei tipi di funzione che possiamo usare per gestire una tabella hash con indirizzamento aperto..
Una delle tante tecniche di per gestire le collisioni in delle tabelle hash prevede l'utilizzo dell'indirizzamento aperto, che si basa su un'idea molto semplice: occupare i posti rimasti vuoti.  Mentre con le liste di collisione gestiamo le chiavi che mirano ad una stessa cella dell'array aggiungendole in una opportuna lista (di chiavi) corrispondete alla cella in questione, la tecnica dell'indirizzamento aperto mira a fare occupare una cella del nostro array non ancora occupata da un'altra chiave, anche se non è la cella che spetta alla chiave inserita. Il tutto non viene fatto in modo casuale, ma secondo un preciso algoritmo(presente nei metodi di inserimento e di ricerca) che fa spostare la destinazione della nostra chiave, in un'altra; se quest'altra è vuota allora la chiave viene memorizzata, altrimenti il processo reitera fin quando non si memorizza la chiave o si ispeziona tutto l'array, scoprendo che è pieno (per andare all'articolo dell'indirizzamento aperto clicca QUI)
Tra le varie tecniche dell'indirizzamento aperto vi è l'hashing doppio, che fa dipendere l'algoritmo che genera la nuova posizione della chiave da una funzione hash. Viene denominato hashing doppio dato che, se usiamo tabelle hash, si sottintende che stiamo usando una funzione hash per smistare la nostra chiave e dato che facciamo dipendere il riallocamento in caso di collisione da un'altra funzione hash, le funzioni diventano due.
Passiamo ad un esempio: h(f) è la nostra chiave hash applicata su f, una parola. Definiamo la funzione hash:

La funzione in pratica somma il valore ascii di ogni lettera che forma la parola f e poi ne fa il modulo m, dove m è la dimensione della tabella. Nella formula X sono le lettere che vanno dalla posizione 0 alla posizione dim-1 della nostra parola.
Ad esempio con m=11 e f = ANNA avremo:
A=65 +
N=78 +
N=78 +
A=65
= 286 = 0 (mod 11)

Questa funzione hash ha restituito 0 così potremo assegnare la voce "ANNA" nella posizione 0 della nostra tabella hash. Ora se volessimo inserire NANA, avremo lo stesso risultato. Se le collisioni vengono gestite mediante liste di collisione metteremo semplicemente NANA in coda nella lista presente nella tabella hash alla posizione 0.
Proviamo a gestire la collisione con l'indirizzamento aperto e in modo particolare con l'hashing doppio. Un doppio hashing è definito in genere da questa formula:

mod m

Ho indicato con H la funzione di hashing doppio che, come vedete, opera sia su f che sull'indice i. Essa è composta dalle due funzioni hash h1 e h2. In questo modo, se due chiavi collidono si andrà ad occupare un posto libero nella struttura, andando a scandirla. Ora definiamo le chiavi hash h1 e h2:

Cambiamo la dimensione a 21 o qualsiasi numero che preferite, proporzionato in modo opportuno alla quantità di dati da inserire, e facciamo dipendere la funzione hash h2 dalla prima, cambiando il modulo (da modulo m andiamo a modulo m-1) e addizionando 1 al risultato finale di questa funzione.

Inserendo la parola ANNA:

(286 = 13 mod 21)

Dato che all'inserimento di NANA, il posto è già occupato da ANNA, viene incrementato l'indice i della funzione hashing doppio che da 0 passa a 1 (controlla l'algoritmo dell'indirizzamento aperto QUI) avendo così:

h1=13 (286 = 13 (mod 21) );

h2=14 (13 (mod 20) + 1);

H=6 (13+14 = 27 = 6 (mod 21) );
nella chiamata di funzione con i che vale 1.

E' stato, così, assegnato un nuovo posto alla parola NANA, passando in rassegna le celle ancora disponibili risultanti dalla funzione Hashing Doppio.