[HASHING-teoria] Indirizzamento aperto, come funziona?

[m0linas]

Ciao a tutti, spero di aver trovato la sezione giusta, anche se la mia non è una domanda su uno specifico linguaggio, ma su una struttura dati....Studiando le tabelle hash o trovato che ci sono 2 modi di gestire le collisioni, le liste di trabocco e l'indirizzamento aperto. Ora sulle prime nessuna difficoltà, ma non riesco a capire come funziona l'indirizzamento aperto....Ho cercato anche su google, ma ho trovato solo spiegazioni identiche a quelle del mio libro...Vi sarei grato se qualcuno potesse spiegarmelo in breve, magari facendo un esempio nel caso ho (buttiamola li) 5 chiavi K1=10 K2=7 K3=20 K4=3 k5=30 e la funzione hash sia hash(K)=k%10. In questo caso la funzione hash genera lo stesso risultato (0) su K1, K2 e K3. Come vengono memorizzati nell'array le chiavi?
Spero che qualcuno di voi abbia 5 minuti da dedicarmi, dato che questa schifosissima domanda mi ha fatto segare l'esame di algoritmi ieri

[m0linas]

Nessuno lo sa? Mi fareste un grosso favore...

[m0linas]

[gugoXX]

I dati relativi alle collisioni non vengono memorizzate in una lista privata per ogni chiave (come avviene per il separate Chaining), ma vengono posizionati direttamente dentro l'array, in celle alternative ma ben specifiche.
Un po' come dire
Scelta la funzione di hashing f(data)=key mappa ogni valore desiderato in una chiave ben precisa.
Se pero' la cella relativa alla chiave ben specifica e' gia' occupata, allora per questa, ma solo per questa, la funzione di hash diventa g(data)=new key.
Se anche la g(data) e' occupata, proviamo con la h(data).
e cosi' via.

Solitamente la funzione che trasforma da f(data) in g(data) (e poi in h(data) e cosi' via) e' una funziona ancora piu' semplice di quella di hashing. Viene chiamata funzione di Probing, e potrebbe essere banalmente = "Provo la cella successiva a quella restituita dalla funzione di hashing".

[m0linas]

Ok, grazie millemila
Immaginavo una cosa del genere, ma sul mio libro di testo è spiegato piuttosto male....
Grazie ancora, il mondo sarebbe migliore se ci fosse più gente come te

EDIT: ormai che ci sei mi potresti scrivere come risulterebbe l'array nell'esempio che avevo fatto io nel primo post? Ponendo come funzione di probing hash(data)=key + 1 se la posizione è già occupata dovrebbe venire una cosa del genere(null indica una posizione vuota):

indice 0----1---2---3----4----5----6----7----8..............
array [10] [20] [30] [3] [null] [null] [null] [7] [null.................]

Se a questo punto avessi k6=40....dato che 40%10=0, andrei a memorizzare 40 in array[4] dato che è il primo posto libero?

[gugoXX]

Originariamente inviato da m0linas

Se a questo punto avessi k6=40....dato che 40%10=0, andrei a memorizzare 40 in array[4] dato che è il primo posto libero?

Esattamente.
Questo e' il comportamento piu' semplice. (first wins, da usarsi quando le scritture sono pesanti, oppure quando si pensa che i primi dati siano quelli piu' richiesti)

Ci sono altri criteri che si possono adottare in caso di collisione.
Potresti decidere che vince l'ultimo inserito, e non quello che c'e', che e' quindi quello spostato. (last wins, da usarsi quando e' piu' probabile che siano i nuovi dati ad essere letti piuttosto che i vecchi)
Oppure potersti decidere che vince quello per cui sono necessarie meno "salti" in caso di ricerca. (least read effort)

Criteri analoghi sono applicabili anche nel caso di Separate Chaining.
Potresti decidere di appendere il nuovo arrivato in fondo, oppure di metterlo in testa. Oppure di tenere la lista ordinata. oppure boh?

Nel caso di ricerca invece, poni di aver inserito il valore 40, nella posizione 4.
Se successivamente ti dovessi chiedere: "Esiste il valore 40 nella mia hashtable"?
Allora procederai come segue:
Calcolo la hash di 40 = 0
Cominicio a scandire l'array a partire da questo indice.
Se trovo 40, restituisco true.
Se trovo NULL, restituisco false.
Altrimenti continuo a scandire.

[m0linas]

ok, grazie mille! Ciao