So each tame or wild thread, must jump, check for dp, if dp send to hashtable and then jump again, if no dp, jump again, rinse and repeat.
Yes !
In your test, you merely walked through 1 billion random points, correct?
1 billions points of random walk determined by the formula :
jD=[G,2*G,4*G...2^n-1*G]
tamePos[j+1] = tamePos[j] + jD[tamePos[j].x % n] (like in Jean-Luc Pons algorithm explanation) j
So you said you used 4 cores, how many "kangaroos" per core/thread were you running?