3 ms·
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,
by damienkatz 18y ago
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.
- 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.