4 ms·
It's missing because you can't get O(1) and have each key equally likely to be returned, right?
by mooism2 18y ago
It's missing because you can't get O(1) and have each key equally likely to be returned, right?
- antirez 18y agoare 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.