hashtable Java vraag over code

[Tripwire999]

]Ik ben bezig met het besturderen van het boek Data structures and alghorithms. Hierin ben ik bij het hoofdstuk HashTables beland. Nou zitten er opdrachten in het boek die ik aan het maken ben. Maar ik kom bij een vraag er niet uit.
Het gaat om dit gedeelte:

http://imageshack.us/photo/my-images/341/hashtable.jpg/
(kan de img niet toevoegen doet het niet dan dus gewoon link dan maar)

De vraag is:
Wat is het resultaat van het volgende programma.

Ik weet dat het antwoord: 351931152723 is.

Als ik de stappen doorloop dan loop ik vast op het stukje v %= arraysize.
Stappen:

1. h.insert(15);
2. public int hashFunc(int key) -> return 15 % arraySize -> return 15 % 6 -> return 3
3. while(hashArray[3] > 0)
4. 3++;
5. 4 %= arraySize -> 4 %= 6

Wat gebeurt er nou precies bij stap 5? Zou iemand mij dit kunnen uitleggen?

[4VAlien]

Het is de modulo operator

in principe kunnen de regels zo herschreven worden:

code:

v %= arraysize;

v = v % arraysize;

while (v>=arraysize) {v = v - arraysize;}

[Tripwire999]

4VAlien schreef op maandag 09 januari 2012 @ 17:04:
Het is de modulo operator

in principe kunnen de regels zo herschreven worden:

code:

v %= arraysize;

v = v % arraysize;

while (v>arraysize) {v = v - arraysize;}

Dat het de modulo operator was wist ik maar ik begrijp nog steeds niet helemaal hoe ze op dat antwoord uitkomen.
Want while(v>arraysize)

v =! arraySize als ik 15 % 6 doe zegmaar in jouw voorbeeld

[4VAlien]

Blijkbaar gaat het al eerder fout, kun je deze code niet even invoeren en er doorheen steppen met een debugger?

Ik heb hem nog even met de hand gemaakt. In principe komt elk getal in eerste instantie op <getal> % 6 (want arraysize) tenzij deze plek al vol dan wordt er opgeschoven.

Hieronder zie je van links naar rechts waar elk getal in de array komt

code:

Start:  I_15   I_19  I_23    I_27    I_31   I_35 (overgebleven plek)
0                                             35
0                 19
0                                     31
0        15
0                             27
0                      23

[ Voor 73% gewijzigd door 4VAlien op 09-01-2012 17:19 ]

[Wmm]

Bij stap 5 wordt voorkomen dat de nieuwe index voorbij de maximale index van de array ligt. Dus als de nieuwe index 6 is geworden wordt hij weer 0 zodat er onderaan begonnen wordt.

[Tripwire999]

Wmm schreef op maandag 09 januari 2012 @ 17:17:
Bij stap 5 wordt voorkomen dat de nieuwe index voorbij de maximale index van de array ligt. Dus als de nieuwe index 6 is geworden wordt hij weer 0 zodat er onderaan begonnen wordt.

Dat is duidelijk . Maar dat verklaart nog steeds niet hoe je aan het antwoord komt helaas.

[4VAlien]

Er is geen 3++ naar 4

Immers de waarden in de hashtable zijn geinitialiseerd op nul. en er staat toch echt dat je hasharray[3] > 0 moet hebben, en DAT IS DUS NIET ZO.

[Tripwire999]

4VAlien schreef op maandag 09 januari 2012 @ 17:23:
Er is geen 3++ naar 4

Immers de waarden in de hashtable zijn geinitialiseerd op nul. en er staat toch echt dat je hasharray\[3] > 0 moet hebben, en DAT IS DUS NIET ZO.

Dus als ik het goed begrijp komt ie nooit in de while loop omdat de hashArray[3] altijd 0 is?

EDIT: AHA ik snap hem nu.

Als ik alle modulo's uitreken:
15 % 6 = 3
19 % 6 = 1
23 % 6 = 5
27 % 6 = 3
31 % 6 = 1
35 % 6 = 5

Als ik dan de array posities op schrijf:

op arraypositie 3 komt 15 te staan
op arraypositie 1 komt 19 te staan
op arraypositie 5 komt 23 te staan
omdat op positie 3 al 15 staat word 27 1 positie opgeschoven dus naar positie 4
omdat op positie 1 al 19 staat word 31 1 positie opgeschoven dus naar positie 2
omdat op positie 5 al 23 staat word 35 1 positie opgeschoven waardoor die op positie 0 komt te staan

[ Voor 62% gewijzigd door Tripwire999 op 09-01-2012 17:34 ]