Esericizio tabelle hash

[cicciudo]

Salve a tutti,
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]

Nessuno ???

[cicciudo]

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 ???

[ramy100689]

Per quanto riguarda la seconda parte, il testo non è molto chiaro quando dice "gestire le collisioni con le liste di trabocco". Una volta che hai questa soluzione:

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

Basterebbe dire che ogni indice della tabella hash contiene una lista, e gli elementi della lista linkata sono per esempio per l' indice 4 : h1,h2,h6.