3 ms·
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.
by antirez 18y ago
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.
- mooism2 18y agoHmm, yes, I think you are right.
- damienkatz 18y agoUnfortunately, 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.
- antirez 18y agowith 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 ;)
- lacker 18y agoIf 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.