[OT] Hash Table

[Lancill]

Ciao a tutti, oggi, prima dell'esame di Algoritmi e Strutture Dati, dopo una discussione (pacifica ) con un mio collega di università, un dubbio mi ha assalito e ancora adesso non sono sicuro della soluzione corretta! Praticamente se ho una TABELLLA HASH con indirizzamento aperto con la chiave Hash di questo tipo per esempio:
h(k, i) = (k + i) mod 19
dove il 19 sta per gli spazi disponibili nella tabella hash (quindi posizioni da 0 a 18); k è la chiave e i varia da 0 a m-1 (m sarebbe 19 in questo caso).

Ora se ho queste chiavi:
2, 5, 19, 6, 27, 36, 24, 22, 28, 31

le posizioni occupate nella tabella hash dalle rispettive chiavi quali sono?

Il mio dubbio è questo: 1a chiave - h (2, 0) = (2 + 0) mod 19
2 mod 19 teoricamente dovrebbe essere il resto della divisione di 2 / 19 che fa 0 con resto 2! Quindi la posizione occupata è la seconda (cioè nella tabella che parte da 0 la numero 1...) giusto?

per la chiave 5
h(5, 0) = (5 + 0) mod 19
che ha resto 5 e quindi va nella posizione 4 della tabella e così via... è così o sbaglio?

[alexmaz]

0 ha posizone 0, 1 ha posizione 1, 2 ha posizione 2, 19 ha posizione 0, 20 ha piszione 1 e via dicendo... credo

[Lancill]

bè su questo non c'è dubbio, il mio problema era sulla correttezza della posizione dopo aver calcolato la chiave hash! Cmq grazie per la risposta!

[alexmaz]

mi sa che non ho capito

la posizione varia a seconda della chiave, ma con lo stesso principio che dicevamo prima... o c'è qualcosa che mi sfugge?

[Zero-2]

Si è così e se due valori hanno la stessa chiave Hash vengono inseriti in una linked list associata a quella posizione.
Una cosa non ho capito :
Perchè il valore i di h(k,i) lo tieni sempre a 0 ??? :master: :master:

[Zero-2]

Originariamente inviato da alexmaz
0 ha posizone 0, 1 ha posizione 1, 2 ha posizione 2, 19 ha posizione 0, 20 ha piszione 1 e via dicendo... credo

Che io sappia non vengono inseriti in ordine.
Non è detto che la prima chiave venga inserita in pos 1 , può essere anche inserita nell'ultima posizione.
DIpende tutto dalla funzione di Hash.

[Lancill]

allora la tabella hash è ad indirizzamento aperto, senza liste linkate, quindi i resta 0 ad ogni inserimento... se la chiave hash indica una posizione già occupata i si incrementa e si ricalcola la chiave.

Esempio:chiave 2
1° tentativo di inserimento
h(k, i) = (k + i) mod 19
h(2, 0) = (2 + 0) mod 19

se la posizione risultante cioè la seconda (TABELLA[1] praticamente) è occupata la chiave diventa
h(2, 1) = (2 + 1) mod 19

ora però il mio problema era sull'operatore di modulo su cui è nata la discussione e che ormai sono convinto che ho ragione...

2 mod 19 fa 2 giusto?

[Zero-2]

Ah ok La mia risposta è dovuta alla consocenza delle HashMap di Java , che mi pare dovrebbero funzionare nel modo in cui ho detto.


Si Si 2 mod 19 fa 2

[alexmaz]

Originariamente inviato da Zero-2
Che io sappia non vengono inseriti in ordine.
Non è detto che la prima chiave venga inserita in pos 1 , può essere anche inserita nell'ultima posizione.
DIpende tutto dalla funzione di Hash.

si lo so, ho inteso i numeri come valore dato dalla funzione di hash...

[Zero-2]

Ah ok
:metallica :metallica