Re:A new fast hash table in response to Google’s new fast ha...
by utopcell on Tuesday May 29, 2018 @09:58AM
(#17179183)
If we were talking about the worst lookups, then even in the RAM model they would become slower as the map grows.
To be more specific, if you place n balls into n bins, on average each bin will contain 1 ball, but the largest one, with high probability, will contain O(log(n)/log(log(n))) of them.
To be more specific, if you place n balls into n bins, on average each bin will contain 1 ball, but the largest one, with high probability, will contain O(log(n)/log(log(n))) of them.