PDA

Visualizza la versione completa : Esercizio Tabelle Hash


Cicciudo
14-06-2013, 18:35
Salve a tutti,
premetto che non so se questa è la sezione adatta al post in questione, quindi se mi trovo in quella sbagliata, chiedo scusa in anticipo :)

sto preparando l'esame di algoritmi e strutture dati e sto facendo passo passo i vari esercizi che mi capitano davanti.

L'esercizio che ho ora sotto gli occhi è il seguente :
Dato l'insieme di chiavi K = 5,11,18,13,14,6,4 e sia m=7 inserire le chiavi in una tabella hash inizialmente vuota di dimensione m usando la funzione hash h(k)=k mod m e gestendo le collisioni con le liste di trabocco. Ripetere l'esercizio usando l'indirizzamento aperto con scansione lineare data da h(k,i) = (h(k)+i) mod m. Mostrare il contenuto della tabella alla fine dell'inserimento :

Allora, per la prima parte dell'esercizio credo di non avere problemi, ma per sicurezza vi mostro il ragionamento che sto adottando :

h0 = 5mod 7 = 5
h1 = 11 mod 7 = 4
h2 = 18 mod 7 = 4
h3 = 13 mod 7 = 6
h4 = 14 mod 7 = 0
h5 = 6 mod 7 = 6
h6 = 4mod 7 = 4
Quindi alla fine la mia tabella dovrebbe essere in questo modo :

Posizioni | Valori
0 h4
1 /
2 /
3 /
4 h1 -> h2 -> h6
5 h0
6 h5

Non so se è giusto il ragionamento, in caso sbaglio qualcosa, mi potete dire dov'è l'errore ?

Per quanto riguarda il secondo esercizio io so, a livello teorico che l'idea è quella di memorizzare tutte le chiavi in una stessa tabella dove ogni slot contiene una chiave o il valore NIL e nell'ispezione lineare la formula è :
H (k,i) = (H(k)+h⋅i) mod m
Nel mio esercizio ho : h(k,i) = (h(k)+i) mod m, quindi vorrei sapere da voi, come dovrei procedere :
dovrei fare per esempio
h(5,0) = (h(5)+0) mod 7
h(11,1) = (h(11)+1) mod 7 e cosi via ???
ma in questi casi, come li metto nella tabella ?

Cicciudo
17-06-2013, 17:29
Nessuno ?? :(

Cicciudo
19-06-2013, 17:56
Partendo dalla "base teorica" che nell'indirizzamento aperto tutti gli elementi sono memorizzati
nella tabella hash stessa. Cioè ogni elemento della tabella contiene o un elemento dell’insieme dinamico o NIL senza aver bisogno di puntatori ... E' giusto questo "modo di fare" per quanto riguarda la seconda parte del mio problema ?

h(5,0) = 5+0 mod 7 = 5
h(11,1)= 11+1 mod 7 = 5
h(18,2)=18+2 mod 7 = 6
h(13,3)=13+3 mod 7 = 2
h(14,4)= 14+4 mod 7 = 4
h(6,5)= 6+5 mod 7 = 4
h(4,6)=4+6 mod 7 = 3

Il ragionamento che ho fatto è il seguente :
il primo elemento va nella casella 5, l'11 ha valore uguale al primo, ma siccome la cella è occupata, lo vado ad inserire nella cella 6, il 18, va inserito nella cella 6, ma siccome è occupata lo vado ad inserire nella cella 0 e così via.
Quindi alla fine dovrei avere questa tabella hash con i valori così inseriti :

|18|6|13|4|14|5|11|

E' giusto come procedimento ???

MItaly
20-06-2013, 01:26
Per quanto riguarda la prima parte, credo che in

Posizioni | Valori
0 h4
1 /
2 /
3 /
4 h1 -> h2 -> h6
5 h0
6 h5

gli elementi sul 4 siano in ordine inverso: per questioni di efficienza gli inserimenti saranno in testa alla lista - è inutile stare a scorrere la lista tutte le volte, non c'è alcun vantaggio ad inserire i nuovi elementi in coda.

Quanto al secondo caso, il ragionamento mi pare corretto.

Cicciudo
25-06-2013, 16:46
Ah ok... ti ringrazio per l'aiuto MItaly e per la chiarezza :)

MItaly
25-06-2013, 23:35
:ciauz:

Loading