are you sure? I don't think so. See the new version of the pseudo code. Just select a new random index every time you reach an empty bucket and you are done.
Unfortunately, it's not guaranteed to return, ever. It's a psuedo-random generator, it can (though not real likely) get stuck in a cycle of buckets it checking, the worst case time complexity O(∞). Even if it uses a real random generator, I'm not sure it's guaranteed to return.
If you want to guarantee it returns, then after N failed operations, just convert the hash table to a list and pick something at random. That will take O(N) time, but since you've already spent O(N) time it amortizes out to no additional cost.
with an hash table 50% full the probability of it not returning after just 100 tries is: 0.0000000000000000000000000000007
I think we can sleep without problems about it ;)
